백준 - 11444번 피보나치 수 6 python 문제풀이 [Hellfer]

https://www.acmicpc.net/problem/11444

11444번: 피보나치 수 6

 

 

🔷 알고리즘 분류 - 분할 정복을 이용한 거듭제곱  난이도 - 골드 2

 

왜 문제를 행렬의 거듭제곱으로 풀어야 하는가??

 

행렬의 거듭제곱이 다른 방법보다 빠른 이유는 계산 효율성과 관련이 있습니다.

일반적으로 숫자의 거듭제곱을 계산할 때, 예를 들어 A^8을 계산한다고 하면, A를 8번 곱하는 방식으로 계산할 수 있습니다. 하지만 이 방식은 7번의 곱셈 연산이 필요합니다.

반면에 행렬의 거듭제곱을 사용하면, 계산을 더 효율적으로 할 수 있습니다. A^8의 경우, 먼저 A^2를 계산하고 이를 다시 제곱해서 A^4를 만든 후, A^4를 다시 제곱해서 A^8을 만들 수 있습니다. 이 방식을 사용하면 

곱셈 연산은 3번만 필요합니다.

이렇게 행렬의 거듭제곱을 사용하면, 계산해야 하는 거듭제곱의 횟수가 많아질수록 더 큰 시간 효율성을 가질 수 있습니다. 이는 분할 정복 알고리즘의 원리를 활용한 것으로, 큰 문제를 작은 문제로 나누어서 해결하는 방식입니다.

따라서 행렬의 거듭제곱을 이용하면, 특히 큰 숫자에 대한 거듭제곱을 계산해야 하는 경우에 계산 시간을 

크게 줄일 수 있습니다.

 

🔶 문제 풀이 - 분할 정복 알고리즘을 이용한 풀이

 

# 행렬 X와 Y를 곱하는 함수
def fibo(X, Y):
    result = [[0, 0], [0, 0]]  # 곱셈 결과를 저장할 행렬 초기화
    for i in range(2):
        for j in range(2):
            for k in range(2):
                result[i][j] += X[i][k] * Y[k][j]  # 행렬 곱셈 수행
    for i in range(2):
        for j in range(2):
            result[i][j] %= 1000000007  # 각 원소를 1,000,000,007로 나눈 나머지로 바꿈
    return result  # 결과 행렬 반환

# 행렬 a를 b번 곱하는 함수
def power(a, b):
    if b == 1: return a  # b가 1이면 a 반환
    elif b == 2: return fibo(a, a)  # b가 2이면 a를 두 번 곱한 결과 반환
    elif b % 2 == 0: return power(fibo(a, a), b//2)  # b가 짝수면 a를 두 번 곱한 결과를 b/2만큼 곱한 결과 반환
    else: return fibo(power(fibo(a, a), b//2), a)  # b가 홀수면 a를 두 번 곱한 결과를 (b-1)/2만큼 곱한 후 a를 한 번 더 곱한 결과 반환

n = int(input())  # 입력받을 피보나치 수열의 항 번호
start = [[1, 1], [1, 0]]  # 피보나치 수열을 계산하는 데 사용되는 기본 행렬

if n == 1: print(1)  # n이 1이면 1 출력
else:
    answer = power(start, n-1)  # n이 1이 아니면 power 함수를 이용해 n-1번째 피보나치 수 계산
    print(answer[0][0] % 1000000007)  # 계산 결과를 1,000,000,007로 나눈 나머지 출력

 

 

🔶 코드풀이

# 행렬 a를 b번 곱하는 함수
def power(a, b):
    if b == 1: return a  # b가 1이면 a 반환
    elif b == 2: return fibo(a, a)  # b가 2이면 a를 두 번 곱한 결과 반환
    elif b % 2 == 0: return power(fibo(a, a), b//2)  # b가 짝수면 a를 두 번 곱한 결과를 b/2만큼 곱한 결과 반환
    else: return fibo(power(fibo(a, a), b//2), a)  # b가 홀수면 a를 두 번 곱한 결과를 (b-1)/2만큼 곱한 후 a를 한 번 더 곱한 결과 반환

 

 

우리가 계산하려는 행렬 'result'가 [[1, 2], [3, 4]]라고 가정해 봅시다. 그리고 이 행렬을 3 제곱하고 싶다고 

해봅시다.

1. 먼저 'b'가 1인지 확인합니다. 만약 1이라면 그냥 자기 자신인 'result'를 반환하면 됩니다. 하지만 여기서는 'b'가 3이므로 이 조건은 해당되지 않습니다.

2. 그다음으로 'b'가 2인지 확인합니다. 만약 2라면 ' result '를 자기 자신과 곱한 결과를 반환하면 됩니다.

하지만 여기서도 'b'가 3이므로 이 조건은 해당되지 않습니다.

3. 그다음으로 'b'가 짝수인지 확인합니다. 만약 짝수라면 ' result '를 자기 자신과 곱한 결과를 'b'를 2로

나눈 값만큼 다시 거듭제곱하면 됩니다. 하지만 여기서는 'b'가 3이므로 이 조건은 해당되지 않습니다.

4. 마지막으로 'b'가 홀수인 경우입니다. 'b'가 홀수라면 ' result '를 자기 자신과 곱한 결과를 'b'를 2로 나눈

값만큼 거듭제곱한 후에, 다시 ' result '를 곱하면 됩니다. 여기서는 'b'가 3이므로 이 조건에 해당됩니다.

 

즉, [[1, 2], [3, 4]]를 3 제곱하는 것은 [[1, 2], [3, 4]]를 자기 자신과 곱한 결과를 1 제곱한 후에,

다시 [[1, 2], [3, 4]]를 곱하는 것과 같습니다.

이 함수는 행렬의 거듭제곱을 효율적으로 계산하기 위해 분할 정복 알고리즘을 사용하고 있습니다. 'b'가 큰 경우에도 빠르게 계산할 수 있습니다.

 

for i in range(2):
        for j in range(2):
            for k in range(2):
                result[i][j] += X[i][k] * Y[k][j]  # 행렬 곱셈 수행

 

 

두 행렬 X와 Y가 다음과 같이 주어져 있다고 가정해 봅시다.

X = [[1, 2], [3, 4]]
Y = [[5, 6], [7, 8]]

result 행렬은 2x2 크기로 초기화되어 있으며, 모든 요소는 0입니다.

result = [[0, 0], [0, 0]]

이제 행렬 X와 Y의 곱셈을 수행합니다.

result [0][0] = X [0][0] Y [0][0] + X [0][1] Y [1][0] = 5 + 14 = 19
result [0][1] = X [0][0] Y [0][1] + X [0][1] Y [1][1] = 6 + 16 = 22
result [1][0] = X [1][0] Y [0][0] + X [1][1] Y [1][0] = 15 + 28 = 43
result [1][1] = X [1][0] Y [0][1] + X [1][1] Y [1][1] = 18 + 32 = 50

따라서, 행렬 X와 Y의 곱은 다음과 같습니다.

result = [[19, 22], [43, 50]]

 

if n == 1: print(1)  # n이 1이면 1 출력
else:
    answer = power(start, n-1)  # n이 1이 아니면 power 함수를 이용해 n-1번째 피보나치 수 계산
    print(answer[0][0] % 1000000007)  # 계산 결과를 1,000,000,007로 나눈 나머지 출력

 

 

이 코드는 피보나치수열의 n번째 항을 계산하는 코드입니다. 입력된 n에 대해 피보나치수열의 n번째 항을 계산하고, 그 결과를 1,000,000,007로 나눈 나머지를 출력합니다.

예를 들어, n이 7인 경우를 생각해 봅시다.

피보나치수열의 피보나치수열의 7번째 항은 13입니다. 따라서 이 코드를 실행하면, power 함수를 통해 계산된 피보나치수열의 7번째 항 (13)을 1,000,000,007로 나눈 나머지를 출력하게 됩니다. 1,000,000,007로 나눈 나머지는 13 자체가 됩니다.

따라서 이 경우, 출력 결과는 13이 됩니다.

이와 같이 이 코드는 피보나치수열의 n번째 항을 계산하고, 그 결과를 1,000,000,007로 나눈 나머지를 출력합니다. 이는 큰 수를 다루는 경우, 수를 작게 만들어주는 역할을 합니다. 특히, 이 방법은 프로그래밍에서 자주 사용되는 방법으로, 큰 수를 다룰 때 오버플로우를 방지하는 데 도움이 됩니다

 

 

🤗파이팅입니다~ 여러분!!🤗