[알고리즘] 백준1003 피보나치 함수 - 파이썬

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

1003번: 피보나치 함수

 

 

[풀이 코드]

t = int(input())
dp = [0] * 41
dp[0] = (1, 0)
dp[1] = (0, 1)

for i in range(2, len(dp)):
    dp[i] = (dp[i - 1][0] + dp[i - 2][0], dp[i - 1][1] + dp[i - 2][1])

for _ in range(t):
    print(*dp[int(input())])

 

1. 동적 프로그래밍 풀이로 해결한 문제로 dp배열은 '메모 이제이 션'개념을 활용했다.

 

메모 이제이 션(Memoization): 다이내믹 프로그래밍을 구현하는 방법 중 하나입니다.
- 한 번 계산한 결과를 메모리 공간에 메모하는 기법입니다.
- 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져옵니다.
- 값을 기록해 놓는다는 점에서 캐싱(Cashing)이라고도 합니다.

 

 

2. 보텀업 방식으로 상향식으로 차곡차곡 답을 해결해가는 방식으로 해결했습니다.

 

- 입력되는 수가 0과 1일 때 0과 1의 개수를 초기화해줍니다. 예를 들어 0일 때 출력되는 0의 개수는 1, 1의 갯수는 0이기에 dp[0] = (1, 0) 으로 1일 때 출력되는 0의 갯수는 0, 1의 갯수는 1이기에 dp [1] = (0, 1)입니다.

 

- 첫 번째 반복문안에서 dp [2] = dp[2 - 2] + dp [2- 1]처럼 순서대로 저장이 되게끔 구현하였습니다. 이렇게 dp배열을 미리 선언해두고 구현한 이유는 피보나치 함수는 중복되는 부분을 해결하기 위해 재귀로 구현하면 시간이 더 오래 걸립니다. 그래서 나중에 미리 저장했던 값을 통해 재귀로 구현하지 않기 위함입니다.