[코테] 피보나치 수 (lv.2)

1. 문제 핵심 요약

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/12945?language=java

핵심 요구사항: N번째 피보나치 수를 1234567로 나눈 값을 리턴

제한 조건: $2 \le N \le 100,000$

2. 접근 방식

0, 1번 배열 값을 적어두면 그 이후로는 f(N) = f(N-1) + f(N-2)로 N번 배열에 저장하고 꺼내오면 된다고 생각했다. 추가로 범위가 10만까지라서 int의 범위로는 불가능할 것 같아 long으로 진행하려고 구상했다.

3. 장단점 및 복잡도 분석

접근 방식	장점	단점	시간 복잡도	공간 복잡도
배열 사용	구현이 직관적임	N이 크면 메모리 낭비가 심함	$O(N)$	$O(N)$
변수 swap 사용	메모리를 절약할 수 있음	과거의 값이 남지 않음	$O(N)$	$O(1)$
재귀와 메모이제이션	수학적 점화식을 코드로 표현 가능	N이 만 단위로 커지면 SOF 발생할 위험 있음	$O(N)$	$O(N)$
행렬 분할 정복	N이 커도 계산 빠름	구현 난이도가 높음, N이 작을 때 느릴 수 있음	$O(\log N)$	$O(1)$

4. 구현 중 발생한 문제 및 해결

❌ 문제 발생

현상: 7번 테스트 케이스부터 실패 발생했다.

원인 분석: long으로 변경했음에도 피보나치 수열은 기하급수적으로 증가해서 N = 93 이후로는 long의 최대 범위를 초과하기 때문이라고 한다.

⭕ 해결 방법

기존에는 1234567 나누기 연산을 리턴에서 진행하여 배열에 자료형 범위보다 큰 값을 저장하려 해서 오버플로우가 발생했다. 그래서 생각을 바꿔 배열에 피보나치 수를 저장할때부터 1234567로 나눈 나머지를 저장하도록 변경하고 자료형도 int로 변경했다.

5. 최종 소스 코드

// 배열을 사용한 피보나치 수
class Solution {
    public int solution(int N) {
        int[] arr = new int[N+1];
			arr[0] = 0;
			arr[1] = 1;

			for(int i = 2; i <= N; i++) {
				arr[i] = (arr[i - 1] + arr[i - 2]) % 1234567;
			}
            
        return arr[N];
    }
}

6. 다른 방식 구현

행렬 분할 정복 방식을 사용한 피보나치 수열 계산이 궁금해서 직접 해봤다.

// 행렬 분할 정복 방식을 사용한 피보나치 수
class Solution {
    // 1. 초기 행렬 설정
				// res = 단위 행렬 항등원
				long r00 = 1, r01 = 0;
				long r10 = 0, r11 = 1;

				// base = 피보나치 기본 행렬 [[1, 1], [1, 0]]
				long b00 = 1, b01 = 1;
				long b10 = 1, b11 = 0;

				// N번째 피보나치 수를 구하기 위해 행렬을 (N - 1)번 거듭제곱해야 함
				int exp = N - 1;

				// 2. 분할 정복을 이용한 행렬 거듭제곱 루프 (Matrix Exponentiation)
				while (exp > 0) {
					// 지수가 홀수라면 현재까지의 base 행렬을 res 행렬에 곱함 (res = res * base)
					if (exp % 2 == 1) {
						long nextR00 = (r00 * b00 + r01 * b10) % MOD;
						long nextR01 = (r00 * b01 + r01 * b11) % MOD;
						long nextR10 = (r10 * b00 + r11 * b10) % MOD;
						long nextR11 = (r10 * b01 + r11 * b11) % MOD;

						r00 = nextR00;
						r01 = nextR01;
						r10 = nextR10;
						r11 = nextR11;
					}

					// base 행렬을 제곱함 (base = base * base)
					long nextB00 = (b00 * b00 + b01 * b10) % MOD;
					long nextB01 = (b00 * b01 + b01 * b11) % MOD;
					long nextB10 = (b10 * b00 + b11 * b10) % MOD;
					long nextB11 = (b10 * b01 + b11 * b11) % MOD;

					b00 = nextB00;
					b01 = nextB01;
					b10 = nextB10;
					b11 = nextB11;

					// 지수를 절반으로 줄임
					exp /= 2;
				}
}

피보나치 행렬

진짜 2x2 행렬 N 제곱하니 좌상단부터 우하단까지 N+1, N, N, N-1 의 피보나치 수열이 나온다.

행렬 분할 정복 - 항등원 (14를 예시로 해봤다.)

행렬 분할 방식을 사용하니 1 -> 4 -> 8 순서로 계산된다.

7. 회고 및 배운 점

기존에는 한 가지의 방법으로만 구현하고 다른 방법은 생각해보지 않았는데 장단점을 정리하여 작성하고, 다른 방식들도 구현해보니 다른 방식과의 장단점을 잘 이해할 수 있었다.