관심이 가는 개발 보물창고

조합은 순서를 고려하지 않습니다. 순서는 고려하지 않고 다양하게 몇 개를 뽑을 지에 집중합니다. 조합을 구현하는 테크닉은 3가지가 있습니다. 중첩 반복문 n명 중 r개를 선택하는 방법일 때, r의 수가 3개 이하라면 반복문으로 빠르고 쉽게 구현할 수 있습니다. for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = j + 1; k < n; k++) { } } } next_permutation 을 이용하자. 순열의 특징을 가져와 1은 애들이 선택됐다고 보면 되고, 0은 선택받지 못한 애들이 됩니다. 즉 5C2 라면 chk 배열을 {0, 0, 0, 1, 1}이라고 두고, 1일 때에만 출력하면 됩니다. int main() { v..

자연수 N과 K가 주어졌을 때, 이항 계수 nCk 를 구하는 문제입니다. 해당 숫자를 10,007로 나누는 의미는 대부분 큰 숫자인 경우에 해당 숫자로 나누는 테크닉이 필요합니다. 이항 계수는 중요한 성질을 가지고 있습니다. n과 k가 같을 때 혹은 k가 0일 때는 1입니다. 이를 통해 base condition 을 만족할 수 있고, 파스칼 법칙에 의하면 nCr = n-1Cr-1 + n-1Cr 을 만족하게 됩니다. 이러한 법칙을 하나씩 하다 보면 반복되는 구간이 생기게 됩니다. 반복되는 것을 계속해서 계산하는 것은 낭비입니다. 따라서 한 번 구한 답을 캐시에 저장하면, 이후에 꺼내다 쓰면 됩니다. 이것을 메모리제이션이라고 합니다. 위에서 base condition도 만족하지 않고, 메모도 하지 않았다면 ..

오랜만에 파라메트릭 서치 문제를 풀었습니다. 파라메트릭 서치 문제는 최적화 문제를 결정 문제로 바꾸어 푸는 문제입니다. 주어진 문제는 여러 개의 랜선의 길이가 주어졌을 때, 각 랜선들을 mid로 자르면 나눠지는 랜선의 개수가 N개 이상을 만들면 되는데, 이때 mid의 길이를 가능한 최대로 뽑고 싶다는 것이 이 문제의 핵심입니다. 예시에서는 200m로 잘랐을 때 11개를 만들 수 있으며 나올 수 있는 최대 길이라고 합니다. 어떻게 11개가 나왔을까요. 802 / 200 = 4 743 / 200 = 3 457 / 200 = 2 539 / 200 = 2 4 + 3 + 2 + 2 = 11개가 됩니다. 정리하면 어떻게 자르든 11개 이상만 나오면 조건을 만족하며, 그때 자른 길이 중 최대를 저장하면 됩니다. 만약..

객체지향 프로그래밍을 해봤다면 지문 이해가 쉬웠을 것 같습니다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라고 합니다. 간단히 말하자면 M으로 인해 N이 생겨났으니, 주체인 M이 N의 생성자라고 생각하면 됩니다. 그랬을 때 문제에서 N이 입력으로 주어지면 우리는 M을 구해야 합니다. 그중에서도 가장 작은 M을 구하려면 M을 1부터 검사하면서 N을 만들 수 있는 생성자를 찾아가면 됩니다. 언제까지 찾으면 될까요? 확실한 건 M은 N보다 클 수 없습니다. 생성자니까요. 따라서 N보다 작을 때까지만 루프를 돌면 됩니다. calc함수는 어떤 자연수의 각 숫자의 합을 리턴하는 함수입니다. 문자열로 쪼개서 계산해도 되지만, 이러한 방식이 오히려 더 편할 수 있습니다. #include #include ..

[문제풀이] 오랜만에 트리 문제를 풀어봤는데,,, 너무 쩔쩔매던 문제였습니다... (개념은 알고 있는데 구현을 못하니..) 주말에 다시 풀어봐야겠습니다. 여튼 문제에서는 트리를 구성하고 전위 순회, 중위 순회, 후위 순회를 그대로 출력하면 됩니다. 전위 순회는 parent, leftChild, rightChild 중위 순회는 leftChild, parent, rightChild 후위 순회는 leftChild, rightChild, parent Tree의 구성은 node 들도 구성되어 있습니다. node의 구성은 데이터를 저장할 char와 자식 노드를 가리킬 2개의 포인터를 구성하면 됩니다. struct Node { char data; Node* leftChild; Node* rightChild; }; 순..

[문제풀이] 문자열 A와 문자열 B가 주어졌을 때, 항상 A의 길이는 B의 길이보다 작거나 같은 조건에서 입력으로 주어졌을 때 A와 B의 길이가 같으면서도, A와 B의 차이를 최소가 되도록 하는 방법을 구하는 문제입니다. 채워 넣을 때는 아무거나 알파벳을 넣되 앞에서 넣나 뒤에서 넣나 최선의 방법으로 넣어야 우리는 최소의 경우를 구할 수 있습니다. 최선의 경우가 아니면 더 많은 방법으로 돌아가겠죠. 간단하게 주어진 입력에 대해서 비교를 하면 쉽습니다. 어처피 채워 넣는 건 최선의 방법으로 채워 넣기 때문에 기존에 입력된 부분의 차이만 구하면 그 차이가 바로 최소의 차이이기 때문입니다. A : adaabc B : aababbc 어릴 때 모양이 여러 조각 난 판이 있을 때 그 모양에 끼워넣기 위해서 이리저리..

문제 풀이 기존의 에라토스테네스의 체에서 약간 변형의 문제입니다. 보통은 소수를 제외하고 그 소수의 배수를 모두 지우는 형태가 에라토스테네스의 체 구현이지만, 이 문제에서 요구하는 건 소수를 찾았을 때도 제거하고 그의 배수들도 모두 제거하면서 지나갑니다. N = 7, K = 3이면 제거하는 순서를 나열하면 다음과 같습니다. 2 4 6 (2의 배수) 3 (3의 배수) 5 (5의 배수) 7 (7의 배수) 따라서 3번째 제거된 수는 6입니다. 중복되는 수를 제거 방지를 위해서 prime변수를 선언해서 제거했더라면 false로 시키고 카운팅 합니다. 카운팅 횟수가 K번째와 같게 된다면 그때가 바로 K번째로 제거된 수입니다. #include #include #include using namespace std; i..

문제 풀이 덩치를 정하는 방법은 (a1, b1) (a2, b2)가 있을 때 a1 > a2 이면서 b1 > b2 이면 앞에 있는 사람이 뒤에 있는 사람보다 덩치가 크다는 의미입니다. 그런데 덩치를 정할 수 없는 순간이 있다면 등수는 모두 같은 것으로 치고, 자신보다 앞에 있는 덩치가 N명이라면 자신의 등수는 N+1로 설정하면 됩니다. N의 크기가 엄청 작기 때문에 완전 탐색으로 모든 경우의 수를 돌려 자신보다 덩치가 큰 녀석들만 카운트합니다. 최종적으로 자신의 등수는 카운트 + 1로 설정합니다. 자신보다 더 큰 덩치가 없다면 자신이 제일 크기 때문에 1등으로 처리해야 되기 때문이죠. #include #include using namespace std; int main() { ios_base::sync_wi..

문제 풀이 빙글빙글 돌면서 K번째 사람을 퇴출하는 방식으로 뽑아내면 되는 문제입니다. N = 7, K = 3이면 1, 2, 3, 4, 5, 6, 7 사람 중에서 3번째 사람을 뽑는 방식으로 진행합니다. 아래의 빨간 표시는 퇴출하는 사람의 순서입니다. 퇴출하고 나서 다음부터 다시 카운트를 시작합니다. 1 2 3 4 5 6 7

문제 풀이 알고 보면 쉬운 문제이지만, 생각보다 오래 걸렸습니다. 3개의 점이 주어졌을 때, 좌표 상에서 직사각형을 만들기 위해 남은 나머지 점을 출력하는 문제입니다. 처음에는 각 점 사이의 거리를 구해서 두 개의 거리를 이용해 좌표를 찾으려고 했지만 너무 많은 계산이 들어가서 다시 생각해봤습니다. 연관점을 찾다 보니 x좌표, y좌표마다 2개씩 같고, 1개씩은 따로 노는 점을 발견했습니다. 1개씩 짝이 없는 좌표가 바로 우리가 찾는 네 번째 점이라는 점을 착안하여 map을 이용해서 짝의 개수를 카운트했고, 짝이 없는 좌표만 저장해서 출력하는 방법으로 풀었습니다. 이후에 다른 풀이를 봤는데, 더 간단한 방법이 있었습니다. x1, x2, x3 y1, y2, y3 이렇게 주어졌을 때 x1 == x2 이면, x..