https://www.acmicpc.net/problem/2749 피보나치 수를 구하는 재미있는 방법을 알게 되어 공유한다. 알고리즘 분류분할 정복다이나믹 프로그래밍 문제설명  문제는 아주 간단하다. 다만, n이 1e18이다. 일단 n은 long long으로 받아야 한다. 그리고 MOD값은 1e6이므로, 결과값 역시 안전하게 long long으로 받아주자. 문제접근 우선 피보나치 수열의 점화식은 다음과 같다. 이 방법으로 f(n)을 구할 수 있지만, n이 1억을 넘어가기 때문에 시간 초과에 해당한다. 즉 O(logN)으로 풀어야 한다. 그러면 어떻게풀어야할까? O(logN)으로 해결할 수 있는 알고리즘은 많지 않다. 분할 정복 말고는 풀이를 찾기 어려울 것이다. 따라서 이 문제를 분할 정복으로 풀어보자...

https://www.acmicpc.net/problem/11401  이항 계수 3이라는 문제를 풀었는데, 여기서 사용된 수학 개념과 테크닉은 향후 유용하겠다 싶어서 정리한다. 사용되는 기법유클리드 호제법페르마의 소정리O(logN) 거듭제곱 모듈로 계산(분할 정복)다이나믹 프로그래밍 문제의 접근문제는 매우 간단하다. 이항 계수를 1e9+7로 나눈 나머지를 구하면 된다. 일반적으로 이항 계수를 구하는 방법은 다음과 같이 팩토리얼을 이용한다. 여기서 MOD 연산이추가되어야 할 것이다. 최대 400만 팩토리얼을 구해야 하기 때문에 MOD를 통해 줄여야 한다.  우선 여기까진 당연히 맞다. 그러면 계산을 다음과 같이 해야할까? 아니다. 뭔가 이상하다. modulo 연산은 다음과 같이 덧셈(=뺄셈)과 곱셈에만 적..