피보나치 - 행렬 거듭제곱으로 O(log N) 풀기
문제 조건에서 N은 1,000,000,000,000,000,000까지 주어진다. 즉, int는 물론이고 일반적인 선형 DP로도 감당하기 어려운 크기다. 게다가 결과는 1,000,000,007로 나눈 값을 출력해야 한다.
처음 이 문제를 봤을 때는 익숙한 피보나치 문제처럼 보였지만, 입력 범위를 보는 순간 평소 방식으로는 안 되겠다고 생각했다. 이 문제를 풀기까지 어떤 가설을 세웠고, 왜 그 접근이 막히는지부터 정리해본다.
DP(Bottom-up) 풀이를 먼저 떠올린 이유
피보나치 수열 문제를 보면 가장 먼저 DP를 떠올리게 된다. 점화식 자체가 너무 익숙하기 때문이다.
\[F(n) = F(n-1) + F(n-2)\]처음에는 재귀 기반 Top-down 풀이를 생각했지만, N의 크기를 보면 재귀 호출이 너무 깊어지고, 메모리나 호출 스택 측면에서도 부담이 클 것이라고 판단했다. 그래서 자연스럽게 Bottom-up 방식으로 접근하려고 했다. 즉, F(0)부터 시작해서 F(n)까지 차례대로 채워 나가는 방식이다.
하지만 이 방법도 결국 시간 초과를 피할 수 없다. 이유는 간단하다. Bottom-up은 한 칸씩 끝까지 올라가야 하므로 시간복잡도가 O(N)인데, 이 문제에서 N은 최대 10^18 수준이다. 아무리 연산이 단순하더라도 이런 크기는 1초 안에 처리할 수 없다. 즉, 점화식은 맞지만, 그 점화식을 계산하는 방식이 틀린 것이다.
분할 정복 풀이가 된다고 하는데 왜 감이 안 왔는가
이후 풀이를 찾아보니 대부분 분할 정복을 사용하고 있었다. 그런데 처음에는 이 부분이 잘 와닿지 않았다.
예전에 분할 정복으로 풀었던 문제들은 보통 A^N처럼 무언가를 N제곱하는 문제였다. 그럴 때는
혹은
\[A^{9} = A^4 \times A^4 \times A\]처럼 지수를 절반씩 줄여가는 방식이 자연스럽다.
그런데 이 문제는 피보나치 수를 구하는 문제다. 겉으로 보기에는 “거듭제곱을 계산하라”는 문제가 아니기 때문에, 도대체 여기서 무엇을 반으로 줄여야 하는지 감이 잘 오지 않았다. 즉, 분할 정복이 가능한 형태로 문제가 아직 보이지 않았던 것이다.
정답은 행렬에 있었다
이 문제의 핵심은 피보나치 점화식을 숫자끼리의 덧셈으로만 보지 않고, 행렬의 곱셈 형태로 바꿔서 보는 것이다.
피보나치 수열은 다음과 같이 표현할 수 있다.
\[\begin{bmatrix} F(n+1) \\ F(n) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F(n) \\ F(n-1) \end{bmatrix}\]이 식이 의미하는 것은 단순하다. 피보나치의 “다음 상태”가, 어떤 고정된 2×2 행렬 하나를 곱하는 것으로 표현된다는 뜻이다.
여기서 핵심 행렬을 다음과 같이 두자.
\[A= \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}\]그러면 피보나치 수열의 진행은 결국 이 행렬을 반복해서 곱하는 과정으로 바뀐다. 그리고 이 행렬은 다음과 같은 매우 중요한 성질을 가진다.
\[A^n = \begin{bmatrix} F(n+1) & F(n) \\ F(n) & F(n-1) \end{bmatrix}\]이제야 비로소 분할 정복을 쓸 수 있게 된다. 문제를 “피보나치를 구하는 문제”가 아니라, 행렬 (A)의 거듭제곱을 빠르게 구하는 문제로 바꿔볼 수 있기 때문이다.
왜 왼쪽 위 값이 답이 되는가
위 성질을 그대로 사용하면,
\[A^{n-1} = \begin{bmatrix} F(n) & F(n-1) \\ F(n-1) & F(n-2) \end{bmatrix}\]가 된다. 즉, A^(n-1)만 구할 수 있다면 그 행렬의 왼쪽 위 값 [0][0]이 바로 F(n)이다. 그래서 코드에서는 최종적으로 다음 값을 출력한다.
1
System.out.println(pow(A, n - 1)[0][0]);
처음 보면 왜 [0][0]인지 낯설 수 있지만, 행렬의 거듭제곱 결과가 피보나치 수를 직접 담고 있기 때문에 가능한 방식이다.
행렬 곱셈은 어떻게 이루어지는가
행렬 거듭제곱을 쓰려면 먼저 행렬 곱셈을 알아야 한다. 2×2 행렬
\[A= \begin{bmatrix} a & b \\ c & d \end{bmatrix}, \quad B= \begin{bmatrix} e & f \\ g & h \end{bmatrix}\]를 곱하면 결과는 다음과 같다.
\[A \times B = \begin{bmatrix} ae+bg & af+bh \\ ce+dg & cf+dh \end{bmatrix}\]즉, 결과 행렬의 각 칸은 “왼쪽 행렬의 행”과 “오른쪽 행렬의 열”을 곱해서 더한 값이다.
행렬 곱셈 예시 1
피보나치 문제에서 사용하는 기본 행렬은
\[\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}\]이므로, 먼저 자기 자신과 한 번 곱해보자.
\[\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \times \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 2 & 1 \\ 1 & 1 \end{bmatrix}\]직접 계산하면,
- (0,0) : (1 × 1 + 1 × 1 = 2)
- (0,1) : (1 × 1 + 1 × 0 = 1)
- (1,0) : (1 × 1 + 0 × 1 = 1)
- (1,1) : (1 × 1 + 0 × 0 = 1)
이 결과는 실제로
\[A^2 = \begin{bmatrix} F(3) & F(2) \\ F(2) & F(1) \end{bmatrix} = \begin{bmatrix} 2 & 1 \\ 1 & 1 \end{bmatrix}\]와 정확히 일치한다. 즉, 정말로 행렬 안에 피보나치 수가 들어가고 있다는 것을 확인할 수 있다.
행렬 곱셈 예시 2
이번에는 방금 구한 (A^2)에 다시 (A)를 곱해보자.
\[\begin{bmatrix} 2 & 1 \\ 1 & 1 \end{bmatrix} \times \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} = \begin{bmatrix} 3 & 2 \\ 2 & 1 \end{bmatrix}\]직접 계산하면,
- (0,0) : (2 × 1 + 1 × 1 = 3)
- (0,1) : (2 × 1 + 1 × 0 = 2)
- (1,0) : (1 × 1 + 1 × 1 = 2)
- (1,1) : (1 × 1 + 1 × 0 = 1)
즉,
\[A^3 = \begin{bmatrix} F(4) & F(3) \\ F(3) & F(2) \end{bmatrix} = \begin{bmatrix} 3 & 2 \\ 2 & 1 \end{bmatrix}\]가 된다. 이 과정을 보면 행렬을 한 번 곱할 때마다 피보나치 수열이 한 단계씩 진행된다는 느낌으로 이해할 수 있다.
이제 분할 정복이 왜 가능한지 보인다
여기까지 오면 문제는 완전히 달라진다. 이제 우리가 구해야 하는 것은 F(n) 자체가 아니라, 사실상 A^(n-1)이다. 그리고 거듭제곱은 분할 정복이 가능하다.
지수가 짝수라면
\[A^8 = A^4 \times A^4\]홀수라면
\[A^9 = A^4 \times A^4 \times A\]처럼 계산할 수 있다. 즉, 매번 지수를 절반으로 줄여 가며 계산할 수 있으므로 시간복잡도는 O(log n)이 된다. 처음에는 피보나치 문제에 분할 정복을 어떻게 쓰는지 감이 안 왔지만, 행렬로 바꾸고 나면 사실상 “행렬 거듭제곱 문제”가 되어버리는 것이다.
코드에서 각 함수가 하는 일
실제 구현에서 핵심은 두 함수다.
1) multiply(a, b) — 두 2×2 행렬을 곱한다.
1
2
3
4
5
6
7
8
9
10
11
12
static long[][] multiply(long[][] a, long[][] b){
long[][] ret = new long[2][2];
for(int k = 0; k < 2; k++){
for(int i = 0; i < 2; i++){
for(int j = 0; j < 2; j++){
ret[i][j] += a[i][k] * b[k][j];
ret[i][j] %= MOD;
}
}
}
return ret;
}
행렬 곱셈 공식 ret[i][j] += a[i][k] * b[k][j]를 그대로 코드로 옮긴 것이다.
2) pow(base, exp) — 행렬의 거듭제곱을 분할 정복으로 계산한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
static long[][] pow(long[][] base, long exp){
if(exp == 0){
return new long[][]{{1, 0}, {0, 1}}; // 단위행렬
}
if(exp == 1){
return base;
}
long[][] ret = pow(base, exp / 2);
ret = multiply(ret, ret);
if(exp % 2 == 1){
ret = multiply(ret, base);
}
return ret;
}
흐름을 정리하면 다음과 같다.
exp / 2를 먼저 계산한다.- 그 결과를 자기 자신과 곱해 제곱한다.
exp가 홀수라면 마지막에A를 한 번 더 곱한다.
즉, 한 번 계산할 때마다 지수가 절반으로 줄어든다.
예를 들어 n = 5라면 피보나치 수열은 1, 1, 2, 3, 5이므로 F(5) = 5이다. 행렬 관점에서 보면
가 되고, 이때 왼쪽 위 값이 바로 정답이다. 즉, pow(A, 4)[0][0]이 5를 반환하게 된다.
왜 중간중간 mod 연산을 해야 하는가
문제는 답을 1,000,000,007로 나눈 값을 요구한다. 그런데 피보나치 수는 매우 빠르게 커지기 때문에 끝까지 계산한 뒤 마지막에만 나머지를 취하는 방식은 위험하다. 계산 중간에 숫자가 너무 커져 long 범위를 넘어갈 수 있기 때문이다. 그래서 행렬 곱셈을 할 때마다 ret[i][j] %= MOD;를 수행해 주어야 한다. 이렇게 하면 값의 크기를 계속 제한하면서 안전하게 계산할 수 있다.
시간복잡도는 왜 O(log N)인가
행렬 하나를 곱하는 비용은 2×2 고정 크기이므로 사실상 상수 시간이다. 중요한 것은 몇 번 곱하느냐인데, 분할 정복 거듭제곱은 지수를 절반씩 줄여 나가므로 전체 호출 횟수는 O(log n)이다. 따라서 이 문제는 매우 큰 N에 대해서도 충분히 빠르게 풀 수 있다.
구현에서 주의할 점
현재 코드에는 한 가지 주의할 부분이 있다. if(exp == 1 || exp == 0) return base;처럼 작성하면 exp == 0일 때도 base를 반환하게 되는데, 수학적으로는 A^0은 단위행렬이어야 한다. 위 구현처럼 0일 때는 단위행렬을 반환하도록 분기하는 편이 맞다.
또한 n = 0이 들어오는 경우도 별도로 처리해 주는 것이 안전하다.
1
2
3
4
5
if(n == 0){
System.out.println(0);
return;
}
System.out.println(pow(A, n - 1)[0][0]);
정리
이 문제를 처음 보면 피보나치 문제이므로 DP부터 떠올리기 쉽다. 하지만 입력 범위가 너무 크기 때문에 O(N) 방식은 통하지 않는다. 처음에는 “피보나치 문제에 분할 정복을 어떻게 쓰지?”라는 생각이 들 수 있지만, 핵심은 피보나치 점화식을 행렬 형태로 바꾸는 데 있다.
피보나치를 행렬로 표현하면 문제는 결국 행렬 거듭제곱 문제가 되고, 이때는 지수를 절반씩 줄이는 분할 정복을 그대로 적용할 수 있다. 즉, 이 문제의 핵심은 다음 한 줄로 정리할 수 있다.
피보나치 수열을 행렬로 표현한 뒤, 행렬 거듭제곱을 분할 정복으로 계산하여
O(log n)에 답을 구한다.