이진트리란 자식 노드의 수가 0 ~ 2개인 트리를 말한다. 이를 재귀적으로 표현할 수 있는데, 단일 노드이거나 해당 노드의 자식 노드가 모두 이진 트리라면 해당 노드를 이진트리라고 부른다. 완전이진트리란 이진트리를 채워나갈 때 마지막 노드가 왼쪽부터 차례대로 채워진 트리의 형태이다. 위 그림에서 볼 수 있듯이, internal 노드의 수는 3, external 노드의 수는 3, 높이 h는 2이다. external 노드가 왼쪽부터 차례대로 채워졌으므로 위의 트리는 완전이진트리가 된다. 만약 왼쪽부터 채우다가 오른쪽 끝까지, 즉 external 노드의 수가 2^h개라면 이를 포화이진트리라고 부른다. internal 노드의 수는 3, external 노드의 수는 4, 높이 h는 2이다. external 노드가..
피보나치 수열을 M으로 나누었을 때, M으로 나눈 나머지가 일정한 주기를 이룬다는 것을 증명했다고 한다. 여기에는 여러가지 있는데, m > 2인 경우에 k(m)은 짝수이다. 임의의 짝수 정수 n > 2에 대해서, k(m) = n인 m이 항상 존재한다. k(m) ≤ m2 - 1 k(2^n) = 3×2(n-1) k(5^n) = 4×5n k(2×5^n) = 6n n > 2라면, k(10^n) = 15×10(n-1) 이는 아래 링크에서 자세히 볼 수 있다. https://www.acmicpc.net/problem/9471 이를 이용해 N번째 피보나치 수열을 계산할 수가 있는데, N번째 피보나치 수열의 주기를 구해주고 이를 P라고 하면, dp[N] == dp[N%P]와 같으므로 N%P번째 피보나치 수열의 값을 구..
CCW 알고리즘은 두 선분이 어떤 방향을 이루고 있는지, 더 나아가 두 선분이 교차하는지 판단하는데 주로 쓰이는 알고리즘이다. 두 선분이 어느 방향으로 꺾여 있는지는 외적의 값을 통해 알아낼 수 있다. 외적의 값이 양수면 반시계 방향으로, 음수면 시계방향으로 꺾여 있다는 것을 의미하는데, 이는 오른손 법칙을 통해 쉽게 생각할 수 있다. 외적의 값이 양수라는 것은 엄지손가락이 위로 향했을 때에는나머지 네 손가락이 감기는 모습이 반시계 방향이고, 음수라는 것은 엄지손가락이 아래로 향했을 때에는 나머지 네 손가락이 시계방향으로 감기는 모습이다. 이를 통해 선분이 시계방향, 혹은 반시계 방향으로 꺾여있는지 알 수 있다. 간혹 외적 값이 0이 나올 수가 있는데, 이는 두 선분이 같은 평면상에 위치한다는 것이고, ..
N개의 동전을 가지고 K원을 만드는 경우의 수를 구하는 방법 N = 3, K = 10이며, 1원, 2원, 5원을 무한히 가지고있을때 동전을 사용하여 10원을 만드는 경우의 수를 구하는 문제이다. 단, 중복되는 경우는 제외해야한다 예를 들어, 3원을 만들 때 1원 + 2원 == 2원 + 1원인 경우를 의미한다. 처음에는 2차원 배열을 통해 구현했다 dp[N][K] 에서 N은 각 동전까지 사용했을 때 얻을 수 있는 K원의 경우의 수를 의미한다. dp[0][0] = 1 0원을 만드는 경우의 수는 아무 동전도 사용하지 않을 때라고 생각하면 1가지이다. 또한, 1원까지 사용했을 때 만들 수 있는 K원의 개수 역시 1가지이다. 이를 표로 정리하면 아래와 같다. N | K (i | j) 0 1 2 3 4 5 6 7 ..
집합 N N = { 2, 3, 4 } N의 부분집합을 S라고 할 때, S의 모든 원소의 곱의 합을 구하는 방법 S = { 2 }, { 3 }, { 4 }, { 2, 3 }, { 2, 4 }, { 3, 4 }, { 2, 3, 4 } 1. 원소 개수가 1개인 경우 -> 2 + 3 + 4 = 9 2. 원소 개수가 2개인 경우 -> 2 * 3 + 2 * 4 + 3 * 4 = 26 3. 원소 개수가 3개인 경우 -> 2 * 3 * 4 = 24 모두 더하면 59가 된다 이를 간단히 구해보자 원소 2, 3, 4를 각각 X, Y, Z라고 하면 모든 원소의 곱의 합은 X + Y + Z + XY + XZ + YZ + XYZ가 된다 (곱하기 기호 생략) 즉, ( X + 1 ) * ( Y + 1 ) * ( Z + 1 ) - ..
