위의 링크에 나와있는 Baekjoon Online Judge Blog의 피보나치 수를 구하는 여러가지 방법에 대해 공부해 보겠다.
BOJ 2749 피보나치 수 3 부터 좀 어렵다.
수가 매우 크지만 다행히 피보나치 수를 M으로 나눈 나머지를 구하는 것인데, 왜 다행이냐면 피보나치 수의 특성 상 피보나치 수를 M으로 나눈 나머지들은 주기를 가지게 된다. 일정 주기로 똑같은 나머지가 반복된다는 것이다. 이 것을 피사노 주기(Pisano Period)라고 한다.
BOJ Blog의 백준님 설명을 보면 피사노 주기를 구하는 공식도 소개 되어있는데, 나는 한 번 직접 주기를 구해서 풀어보고자 한다. 음 근데 직접 주기를 어떻게 구할지 모르겠다...
일단 피사노 주기를 구하는 공식으로 풀어야 겠다. 그리고 BOJ 9471 피사노 주기 문제도 있는데 이 문제도 어려운 것 같다... 일단 BOJ 9471 피사노 주기 문제부터 공부해야겠다.
BOJ 9471을 통해서 피사노 주기 구하는 방법을 알아내고 따로 정리해 놨다.
이제 BOJ 2749 피보나치 수 3 을 풀어야 겠다.
좀 헷갈리는 부분이 이 문제에서 피보나치 수가 0, 1, .. 이렇게 시작한다는 것이고 0번째 피보나치 수부터 시작한다. 그렇기 때문에 n번째 피보나치 수를 구할 때 n을 주기로 나눈 값을 pp라고 하면 0번째 수 부터 시작해서 pp번째 뒤에 있는 수로 생각하면 될 것 같다...
아 그리고 이 문제는 행렬을 이용해서도 풀 수 있다고 한다. 나중에 풀어 봐야겠다.
다음 문제는 BOJ 11444 피보나치 수 6 이다.
이 문제는 앞의 문제와 달리 무려 10억7로 나머지 연산을 해야하는데, 이 경우 피사노 주기가 매우 커지니까 피사노 주기로는 시간 내에 풀기 힘들어 보인다.(현재 내 역량으로 보기에는 그렇다..) 백준님의 설명에는 행렬을 이용한 방법으로 풀어야 한다고 나와있다.
1629번 곱셈문제를 풀었다면,
바로 위의 식을 정리해 아래의 식으로만 나타낼 수 있으면 행렬 제곱을 빠르게 계산해서 풀 수 있다. 무려 O(logN)만에... 곱셈을 빠르게 하는 것도 엄청나지만 이 피보나치 수열을 이렇게 행렬로 나타낼 생각을 했다는 것도 대단한 것 같다.
근데 첫번째 식은 이해가 되는데..(그냥 피보나치 수열 식을 옮겨 놓은 것이므로) 그 식을 정리해 아래와 같이 나타낼 수 있는지 이해를 못했었다. 그래서
이 블로그를 좀 참조 했다. 저 블로그에 나와있는 그대로 한 것은 아니고 좀 보면서 도움을 받았는데, 나는 피보나치 수를 행렬로 나타낸 식을 정리해 아래와 같이 나타내는 것에 집중해서 위의 식을 1번식, 그 아래의 식을 2번식이라고 하면 1번식의 양변에 (1 1 1 0)의 역행렬을 곱해보는 방식으로 그 블로그의 2번식 유도 과정을 따라가다보니 정말 역행렬을 이리저리 잘 곱해주면서 조작해 보면 2번식이 나옴을 알 수 있다.
그리고 이제 이 문제의 핵심중 하나는 행렬 곱셈을 구현하는 것인데, 내가 생각한 건 아니지만 백준님의 코드를 보고 이해했다.
그리고 마지막으로 소개된 방법은 피보나치 수를 더 작은 피보나치 수의 합 또는 곱으로 구할 수 있음을 이용해서 memoization을 이용하는 방법이다.
근데 n이 매우 큰데, memoization할 배열을 할당할 때 메모리 초과가 나지 않을까? 라는 걱정이 드는데, 백준님의 코드를 보면 dp처럼 배열을 미리 잡는 것이 아니라, map을 이용해서 memoization을 구현하고 있다. map으로 구현한 것과, 메모리 초과가 나지 않는다고 할 때, 아마 n번째 피보나치 수를 구할 때, d[1]부터 d[n]까지 모두 필요한 것이 아닌 것 같다. 위의 식을 보면 짝수든 홀수든 간에 대략 자기 자신의 2분의 1에 해당하는 값들의 합 또는 곱으로 구할 수 있으므로, 대충 짐작해보면 d[n]을 알기 위해 d[n/2]가 필요한 셈이므로 시간 복잡도 뿐 아니라 memoization에 쓰이는 배열 역시 O(logN)만큼만 필요할 것이다.
그래서 map으로 구현한 것이고, 메모리 초과가 나지 않을 것이다.
참 멋진 풀이다. 그리고 map을 사용해서 memoization을 이렇게 재귀로 구현하므로서 필요한 것만 쓰게 되고 결국 시간과 메모리에서 문제 없이 된다는 것이 매우 멋지다.
일단 위의 식이 맞는지 이해한 후에 memoization으로 구현해 봐야겠다. 음 근데 위의 식이 왜 저렇게 나오는지.. 아니 맞는지조차 증명을 못하겠다... 검색해봐도 잘 나오지 않는 것 같고... 그래서 일단 구현만 해보고 나중에 정수론 같은 것도 공부해 봐야겠다.
참고 및 출처 :
백준 온라인 저지 블로그 - 피보나치 수를 구하는 여러가지 방법
어떤 수학(정수론)관련 블로그
댓글 없음:
댓글 쓰기