백준 알고리즘 1003 (피보나치 함수) - C++, Python

[문제] 백준 알고리즘 1003 (피보나치 함수) - C++, Python

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

1003번: 피보나치 함수

0이 호출되는 횟수와 1이 호출되는 횟수를 공백으로 구분해서 출력해야한다.

피보나치 함수를 동적계획법(=DP, 다이나믹 프로그래밍)으로 작성하는 문제이다.

메모이제이션(Memoization)을 활용하는데, 이는 동일한 계산을 반복할 때 이전 값을 메모리에 저장하여

반복 수행을 제거하여 실행 속도를 빠르게 하는 기술이고, 동적계획법의 핵심이다.

 

[문제 해결]

1. 메모이제이션을 활용할 dp[41]을 생성, 테스트 케이스 T와 숫자 num을 받는다.

    - 최종적으로 dp[num-1], dp[num]을 출력하기 위함

        → 0번째와 1번째의 호출 수는 피보나치 수를 따라감

        → num이 0이면, dp[num-1]을 출력할 수 없으므로, "1 0"을 출력하며 예외처리

        → num=3일 때는 0 1 [1 2] 3 5 8 ...  num = 4일 때는 0 1 1 2 [3 5] 8 ...

2. 피보나치 함수에서, n이 0 또는 1일 때는, dp[n] = n으로 기록한다.

3. dp[n]이 0이면(=기록이 되지 않았다면), 피보나치 재귀를 실행

    - dp[n]에 값이 있는 경우, 반복 수행을 하지 않게 된다 → 속도 증가

4. dp[n]을 return

5. 피보나치 함수가 끝나면 dp[num-1], dp[num]을 출력

 

[C++]

#include <cstdio>
#include <cstring>
using namespace std;

int dp[41];

int fibonacci(int n) {
	if (n == 0 || n == 1) { 
		dp[n] = n; // memoization
		return n;
	}
	// dp[n]이 0이면 memoization
	if (!dp[n]) dp[n] = fibonacci(n - 1) + fibonacci(n - 2);
	return dp[n];
}

int main() {
	memset(dp, 0, sizeof(dp));
	int t;
	scanf("%d", &t);
	for (int i = 0; i < t; i++) {
		int num;
		scanf("%d", &num);
		if (!num) printf("1 0\n");
		else {
			fibonacci(num);
			printf("%d %d\n", dp[num - 1], dp[num]);
		}
	}
	return 0;
}

 

[Python]

import sys
input = sys.stdin.readline
dp = [0 for _ in range(41)]

def fibonacci(n):
    if n == 0 or n == 1:
        dp[n] = n
        return n
    if not dp[n]:
        dp[n] = fibonacci(n - 1) + fibonacci(n - 2)
    return dp[n]

T = int(input())
for _ in range(T):
    num = int(input())
    if not num:
        print('1 0')
    else:
        fibonacci(num)
        print(dp[num-1], dp[num])