문제 설명
피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.
예를들어
- F(2) = F(0) + F(1) = 0 + 1 = 1
- F(3) = F(1) + F(2) = 1 + 1 = 2
- F(4) = F(2) + F(3) = 1 + 2 = 3
- F(5) = F(3) + F(4) = 2 + 3 = 5
와 같이 이어집니다.
2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.
제한 사항
- n은 2 이상 100,000 이하인 자연수입니다.
입출력 예
| n | return |
|---|---|
| 3 | 2 |
| 5 | 5 |
내 코드
def solution(n):
answer = 0
f_list = [0, 1] # f[0], f[1]
for i in range(n):
f_list.append(f_list[i] + f_list[i+1])
return f_list[n] % 1234567대표적인 DP 입문 시, 접하는 피보나치 수열 알고리즘이다.
해당 코드는 반복문을 활용한 메모이제이션(보텀업) 방식으로 해결한 코드이다.
메모이제이션은 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식을 의미한다. 이는 일반적인 재귀함수로 풀어가는 알고리즘의 단점 중, 연산수가 많다는 점을 보완한 방식이다.
즉 여기서 f_list는 이전에 계산된 결과 를 일시적으로 담았기때문에 메모이제이션 방법과 DP가 활용됐다고 볼 수 있다.
