[Java+Python]11444번, 피보나치 수 6

목차

 

분할 정복 단계

 

[Java+Python]2630번, 색종이 만들기

[Java+Python]1992번, 쿼드 트리

[Java+Python]1780번, 종이의 개수

[Java+Python]1629번, 곱셈

[Java+Python]11401번, 이항 계수 3

[Java+Python]2740번, 행렬 곱셈

[Java+Python]10830번, 행렬 제곱

[Java+Python]6549번, 히스토그램에서 가장 큰 직사각형

 

문제

 

피보나치 수는 0과 1로 시작한다. 

0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 

그다음 2번째부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 $F_n = F_{n-1} + F_{n-2} (n ≥ 2)$가 된다.

$n=17$일 때까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

 

입력

 

첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다.

 

출력

 

첫째 줄에 n번째 피보나치 수를 1,000,000,007으로 나눈 나머지를 출력한다.

 

풀이

 

이전 단계에서 피보나치수열을 동적계획법을 이용해 푼 적이 있다.

 

[BackJoon]24416번, 피보나치 수 1

[BackJoon]24416번, 피보나치 수 1

[Python]24416번, 피보나치 수 1

[Python]24416번, 피보나치 수 1

 

가장 간단하게는 재귀호출을 이용해 푸는 방법이 있겠으나, 여기선 생략하겠다.

 

대신 지금부터 구현할 분할정복과 이전에 구현한 동적계획법, 그리고 재귀의 성능을 비교하고 넘어가자.

 

Divide and Conquer vs. Dynamic Programming vs. Recursion

 

	Time Complexity	Space Complexity
Divide and Conquer	$O(\log{n})$	$O(\log{n})$
Dynamic Programming	$O(n)$	$O(n)$
Recursion	$O(2^n)$	$O(n)$

 

재귀 함수와 비교하면 분할정복의 성능이 어마어마하게 좋은 것을 알 수 있다.

 

계속해서 풀이를 해 가자면, 이번 문제를 풀 때는 문제에서 제공한 피보나치수열의 정의

 

$$F_n = F_{n-1} + F_{n-2} (n ≥ 2)$$

 

를 행렬을 이용해 다른 방법으로 적어야 한다. 중간 과정을 생략하고 결과만 말하자면 피보나치수열은

 

$$\begin{pmatrix} F_n\\F_{n-1} \end{pmatrix} = \begin{pmatrix} 1&1 \\ 1&0 \\ \end{pmatrix} \begin{pmatrix} F_{n-1}\\F_{n-2} \end{pmatrix}, \hspace{1em}(n \geq 2)$$

 

로 표현할 수 있다. 이렇게 표현하고 나면 피보나치수열의 계산을 행렬의 거듭제곱을 이용해 계산할 수 있게 되는데,

 

예를 들어서 $F_4$를 구한다고 가정하면, 다음과 같이 계산하면 된다.

 

\begin{align*} \begin{pmatrix} F_4\\F_{3} \end{pmatrix} &= \begin{pmatrix} 1&1 \\ 1&0 \\ \end{pmatrix} \begin{pmatrix} F_{3}\\F_{2} \end{pmatrix} \\ &= \begin{pmatrix} 1&1 \\ 1&0 \\ \end{pmatrix} \begin{pmatrix} 1&1 \\ 1&0 \\ \end{pmatrix} \begin{pmatrix} F_{2}\\F_{1} \end{pmatrix} \\ &= \begin{pmatrix} 1&1 \\ 1&0 \\ \end{pmatrix} \begin{pmatrix} 1&1 \\ 1&0 \\ \end{pmatrix} \begin{pmatrix} 1&1 \\ 1&0 \\ \end{pmatrix} \begin{pmatrix} F_{1}\\F_{0} \end{pmatrix}\end{align*}

 

여기서 행렬은 결합법칙이 성립하기 때문에 아래와 같이 계산을 진행해 나갈 수 있으며,

 

\begin{align*} \begin{pmatrix} F_4\\F_{3} \end{pmatrix} &= \begin{pmatrix} 1&1 \\ 1&0 \\ \end{pmatrix} \begin{pmatrix} 1&1 \\ 1&0 \\ \end{pmatrix} \begin{pmatrix} 1&1 \\ 1&0 \\ \end{pmatrix} \begin{pmatrix} F_{1}\\F_{0} \end{pmatrix} \\ &= \begin{pmatrix} 2&1 \\ 1&1 \\ \end{pmatrix} \begin{pmatrix} 1&1 \\ 1&0 \\ \end{pmatrix} \begin{pmatrix} F_{1}\\F_{0} \end{pmatrix} \\ &= \begin{pmatrix} 3&2 \\ 2&1 \\ \end{pmatrix} \begin{pmatrix} F_{1}\\F_{0} \end{pmatrix} \end{align*}

 

여기서 $F_1 = 0,\hspace{0.5em} F_0 = 0$이기 때문에 마지막 정사각행렬의 [0, 0] 인덱스의 값이 원하는 피보나치 수임을 확인할 수 있다.

 

여기까지 이해했다면 그다음은 이전 문제들과 동일하게 분할 정복을 이용한 행렬의 고속 거듭제곱을 구현하면 된다.

 

간략하게 알고리즘을 정리하면 아래와 같다.

 

1. 주어진 숫자 n을 long으로 입력받는다. 나머지 연산을 할 p 역시 1000000007로 초기화해 준다.
2. 우리의 식은 n이 2 이상일 경우이지만 문제에선 1 이상의 자연수를 주기 때문에 n == 1 일 경우의 예외처리를 해준다.
3. 정사각행렬 $matrix = \begin{pmatrix} 1&1 \\ 1&0 \\ \end{pmatrix}$을 생성한다.
4. 고속 거듭제곱을 위한 pow() 메서드를 호출한다. 이 메서드는 아래와 같이 동작한다.
   
   
   1. exponent가 1이면 A를 그대로 반환한다.
   2. pow() 메서드를 재귀호출해 A를 (exp / 2)번 거듭제곱한 결과를 구한다.
   3. 이 과정에서 행렬 곱셈을 위한 메서드 multiply() 메서드를 호출하는데,
      해당 메서드는 행렬 곱셈을 진행하며 값을 p로 나눈 나머지를 저장한다.
5. pow() 메서드의 결과인 result[][] 배열(리스트)의 [0, 0] 인덱스의 값을 출력한다.

 

Java

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Prob11444 {

	static final long p = 1000000007;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		long n = Long.parseLong(br.readLine());

		if (n == 1) {
			System.out.println(1);
			System.exit(0);
		}

		long[][] matrix = {{1, 1}, {1, 0}};
		long[][] result = power(matrix, n - 1);

		System.out.println(result[0][0]);
	}

	public static long[][] power(long[][] matrix, long exp) {

		if (exp == 1) {
			return matrix;
		}

		long[][] temp = power(matrix, exp / 2);
		long[][] result = multiply(temp, temp);

		if (exp % 2 == 1) {
			result = multiply(result, matrix);
		}

		return result;
	}

	private static long[][] multiply(long[][] a, long[][] b) {

		int x = a.length;
		int y = b[0].length;
		int z = b.length;

		long[][] result = new long[x][y];

		for (int i = 0; i < x; i++) {
			for (int j = 0; j < y; j++) {
				for (int k = 0; k < z; k++) {
					result[i][j] += (a[i][k] * b[k][j]) % p;
					result[i][k] %= p;
				}
			}
		}

		return result;
	}
}

 

Python

 

import sys

n = int(sys.stdin.readline().rstrip())
p = 1000000007

if n == 1:
    print(1)
    exit()

matrix = [[1, 1], [1, 0]]


def multiply(a, b):
    global p

    x = len(a)
    y = len(b[0])
    z = len(b)

    result = [[0 for _ in range(y)] for _ in range(x)]

    for i in range(x):
        for j in range(y):
            for k in range(z):
                result[i][j] += (a[i][k] * b[k][j]) % p
                result[i][j] %= p

    return result


def power(matrix, exp):
    if exp == 1:
        return matrix

    temp = power(matrix, exp // 2)
    result = multiply(temp, temp)

    if exp % 2 == 1:
        result = multiply(result, matrix)

    return result


result = power(matrix, n - 1)

print(result[0][0])

 

Performance