피보나치 수열을 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번째 피보나치 수열의 값을 구..
Study/Algorithm
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 ) - ..
위와 같은 그림을 얻기 위한 코드를 짜보았다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 #include using namespace std; int main() { for (int i = 0; i
