[BaekJoon] 10425번 : 피보나치 인버스 (Python) (feat. ChatGPT)

코딩 1일 1문제! 오늘의 문제는 백준의 피보나치 인버스 입니다.

10425번: 피보나치 인버스

👨🏻‍💻 문제 풀이

피보나치 수열을 만드는데

내가 현재 입력 받은 수 중에서 가장 큰 수 보다 더 큰 수가 만들어지면 수열 생성을 종료하였습니다.

이렇게 만들어진 피보나치 수열을 활용하여

각 피보나치 수열의 숫자 값을 Key 로 해당 숫자가 피보나치 수열에서 몇번째 값인지 나타내는 값을 Value 로 하는

fibo_dict 를 만들어주었습니다.

 

이렇게 미리 피보나치 수열을 구해둔 이유는 매숫자 입력 요청마다 피보나치 수열을 다시 구하게 되면 

너무 비용이 큰 것 같아서 미리 피보나치 수열을 구해서 저장해두도록 하였습니다.

 

마지막으로 입력 받은 각 숫자를 key 값으로 아까 만들어 둔 fibo_dict 에서 값을 하나씩 꺼내오면 끝!

이렇게 푸니 792ms 의 시간을 사용했습니다.

👨🏻‍💻 코드 ( Solution ) - SOMJANG

def fibo_nums(max_n):
    fibo_dict = {}
    fibo = [0, 1, 1]
    
    idx = 3
    while True:
        fibo_num = fibo[idx-1] + fibo[idx-2]
        
        if fibo_num > max_n:
            break
        
        fibo.append(fibo_num)
        idx += 1
    
    for v, k in enumerate(fibo):
        fibo_dict[k] = v
        
        
    return fibo_dict


def fibo_inverse(fibo_dict, n):
    return fibo_dict[n]


if __name__ == "__main__":
    fibo_dict = fibo_nums(max_n=pow(10, 21000))
    
    for _ in range(int(input())):
        fibo_num = int(input())
        
        print(fibo_inverse(fibo_dict=fibo_dict, n=fibo_num))

👨🏻‍💻 문제 풀이 - ChatGPT - 1회차 - 그냥 풀어줘

그제까지는 영어로 영어문제를 풀어달라고 했으면 이번에는 한글로 한글 문제를 풀어달라고 요청해보았습니다.

 

ChatGPT 의 풀이와 코드는 아래와 같습니다.

 

해당 문제는 주어진 피보나치 수열에서 n을 찾는 문제이다. 이를 해결하기 위해서는 각 피보나치 수열을 계산해가면서 n과 일치하는 경우 해당 인덱스를 출력하면 된다.

먼저 피보나치 수열을 계산하는 함수를 구현해보자.

def fibonacci(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

위 함수는 재귀적으로 피보나치 수열을 계산하는 함수이다. 그러나 이 함수는 입력 범위가 크기 때문에 시간 복잡도가 매우 크다. 따라서 더 효율적인 방법을 찾아야 한다.

 

피보나치 수열의 각 항은 이전 두 항의 합이므로, 현재 항을 계산하기 위해서는 이전 두 항의 값을 알고 있어야 한다. 따라서 이전 두 항의 값을 저장하고 있으면서 계산해나가는 방법이 더 효율적이다. 이를 위해 리스트를 사용할 수 있다.

def fibonacci(n):
    fib_list = [0, 1]  # 초기값 설정
    while True:
        # 리스트에 저장된 마지막 두 항의 합을 계산하여 리스트에 추가
        next_fib = fib_list[-1] + fib_list[-2]
        if next_fib > n:  # 찾고자 하는 값보다 크면 종료
            break
        fib_list.append(next_fib)
    return len(fib_list) - 1  # 인덱스는 0부터 시작하므로 1을 빼줌

위 함수는 입력으로 주어진 값보다 작거나 같은 피보나치 수열을 계산하면서 리스트에 추가하다가, 주어진 값보다 커지면 종료하고 리스트의 길이에서 1을 빼서 인덱스를 출력한다

 

이제 주어진 입력에 대해서 위 함수를 적용하여 출력하면 된다.

t = int(input())  # 테스트케이스 개수 입력
for _ in range(t):
    n = int(input())  # 피보나치 수열 값 입력
    print(fibonacci(n))

👨🏻‍💻 코드 ( Solution ) - ChatGPT - 1회차 - 그냥 풀어줘

def fibonacci(n):
    fib_list = [0, 1]  # 초기값 설정
    while True:
        # 리스트에 저장된 마지막 두 항의 합을 계산하여 리스트에 추가
        next_fib = fib_list[-1] + fib_list[-2]
        if next_fib > n:  # 찾고자 하는 값보다 크면 종료
            break
        fib_list.append(next_fib)
    return len(fib_list) - 1  # 인덱스는 0부터 시작하므로 1을 빼줌

if __name__ == "__main__":    
    for _ in range(int(input())):
        fibo_num = int(input())
        
        print(fibonacci(n=fibo_num))

이 방법은 입력 받은 수가 있을때마다 피보나치 수열을 다시 구하므로 소요되는 시간이 훨씬 더 길었습니다.

제가 풀었을때는 792ms -> ChatGPT 의 첫번째 풀이는 1464ms!

👨🏻‍💻 문제 풀이 - ChatGPT - 2회차 - 더 효율적인 코드 부탁해

위에서 제시한 함수는 간단하지만, 입력 범위가 커질수록 계산 속도가 느려질 수 있다는 단점이 있습니다. 더 효율적인 알고리즘으로는 "행렬 거듭제곱"을 이용하는 방법이 있습니다.

피보나치 수열을 다음과 같이 행렬로 나타낼 수 있습니다.

[F_n  ]    [1 1]^n-1   [F_1  ]
[F_n-1]  = [1 0]    x  [F_0  ]

위 행렬식에서 n 번째 피보나치 수열 값을 구하기 위해서는 n-1 번 거듭제곱을 구한 후

F_1 과 F_0 값을 행렬에 곱하면 됩니다. 이를 행렬 거듭제곱 알고리즘을 이용하여 빠르게 게산할 수 있습니다.

import numpy as np

def fibonacci(n):
    # 피보나치 수열의 초기값을 행렬로 나타냄
    fib_matrix = np.array([[1, 1], [1, 0]])

    # (n-1)번 거듭제곱을 구함
    fib_matrix_n = np.linalg.matrix_power(fib_matrix, n-1)

    # 결과값을 계산하여 반환
    fib_n = fib_matrix_n[0][0]
    return fib_n

위 코드에서 numpy 모듈의 array 와 linalg.matrix_power 함수를 사용하여 행렬 거듭제곱을 구합니다.

linalg.matrix_power 함수는 행렬과 거듭제곱 횟수를 입력으로 받아 행렬 거듭제곱 값을 반환합니다.

👨🏻‍💻 코드 ( Solution ) - ChatGPT - 2회차 - 더 효율적인 코드 부탁해

import numpy as np

def fibonacci(n):
    # 피보나치 수열의 초기값을 행렬로 나타냄
    fib_matrix = np.array([[1, 1], [1, 0]])

    # (n-1)번 거듭제곱을 구함
    fib_matrix_n = np.linalg.matrix_power(fib_matrix, n-1)

    # 결과값을 계산하여 반환
    fib_n = fib_matrix_n[0][0]
    return fib_n


if __name__ == "__main__":    
    for _ in range(int(input())):
        fibo_num = int(input())
        
        print(fibonacci(n=fibo_num))

이렇게 numpy 와 행렬 곱을 활용하여 문제를 풀어주었습니다.

하지만 백준이 numpy 와 같은 라이브러리가 존재하는 코드는 처리가 불가하므로

이 코드가 문제안에 존재하는 모든 케이스를 만족할 수 있는지 체크할 수는 없었습니다.

GitHub - SOMJANG/CODINGTEST_PRACTICE: 1일 1문제 since 2020.02.07