[백준] 1003 - 피보나치 함수

문제

백준 1003번 피보나치 함수

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

 

알고리즘

동적 계획법(Dynamic Programming, DP) 

DP는 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 동적 계획법을 적용하기 위해서는 2가지 조건을 만족하는지 확인해야 한다.

 

조건 1. Overlapping Subproblems (겹치는 소문제)

DP는 현재 문제를 작은 문제로 나누고, 그 작은 문제의 결과를 사용하여 원하는 결과를 도출하는 과정이다. 문제를 해결하는 과정에서 동일한 하위 문제가 반복적으로 등장해야 한다. 이를 통해 한 번 계산한 결과를 저장(메모이제이션)하여 중복 계산을 줄일 수 있는 것이 DP의 핵심 특징이다.

 

조건 2. Optimal Substructure (최적 부분 구조)

최적 부분 구조는, 작은 문제들의 최적 결과 값을 사용했을 때 큰 문제의 결과 값을 최적으로 도출해낼 수 있다는 보장이 있어야 한다는 것이다. 큰 문제가 작은 문제들의 결과값을 통해서만 해결할 수 있을 때 최적 부분 구조를 만족한다고 할 수 있다. 

 

DP를 적용하는 방법은 다음과 같다.

 

1. 겹치는 소문제와 최적 부분 구조 조건을 충족하는지 확인하여 DP 알고리즘으로 풀 수 있는 문제인지 파악한다.
2. 큰 문제를 소문제로 나누는 기준 변수를 정한다.
3. 반복 적용되는 점화식을 찾는다.
4. 초기 조건을 찾는다.
5. 메모이제이션을 구축한다.
6. Bottom - up 혹은 Top - down 방식으로 반복문을 사용해 DP를 수행한다.

내용 출처 : https://dense.tistory.com/entry/dp

[동적 계획법 - Dynamic Programing] DP란?

 

문제 풀이

이 문제의 목적은 다음과 같은 피보나치 수열을 계산하는 함수가 있을 때, 입력값 n에 대해  0과 1이 각각 몇 번 출력되는지를 구하는 문제이다. 0이 출력되는 경우는 fibonacci(0) 이 호출되었을 때, 1이 출력되는 경우는 fibonacci(1)이 호출되었을 때이다. fibonacci(n)을 실행했을 때 fibonacci(0)과 fibonacci(1)이 호출되는 횟수를 구하기 위해서는, n-1일 때와 n-2일 때의  fibonacci(0)과 fibonacci(1) 호출 횟수를 각각 더하여 구할 수 있다. 이때, n-1일 때는 다시 n-2일 때와 n-3일 때의 횟수를 더하여 그 값을 구할 수 있고, n-2일 때는 n-3일 때와 n-4일 때 호출 횟수를 더하여 구할 수 있다. 이때 n-2, n-3 이라는 소문제가 서로 다른 두 분기에서 겹치므로, DP가 성립하기 위한 요건 중 하나인 '겹치는 소문제'를 만족한다고 볼 수 있다.

fibonacci(n)의 fibonacci(0)과 fibonacci(1)이 호출값은 반드시 n-1과 n-2일 때의 값을 더해서만 구할 수 있기 때문에, n-1일 때와 n-2일 때의 최적의 값은 n의 최적의 값을 도출할 수 있다는 것이 보장되므로, 다른 요건 중 하나인 '최적 부분 구조' 또한 만족한다. 

이러한 두 조건을 만족할 뿐만 아니라, 주어진 시간이 0.25초로 매우 짧다. 시간을 우선순위로 둘 때, 피보나치 수열을 DP로 계산할 경우에 시간복잡도가 O(n)이므로 DP를 사용하여 문제를 해결할 수 있다.

 

DP를 적용하는 과정을 따라 문제를 해결하였다.

1. 겹치는 소문제와 최적 부분 구조 조건을 충족하는지 확인하여 DP 알고리즘으로 풀 수 있는 문제인지 파악한다. : 윗 설명 참고
2. 큰 문제를 소문제로 나누는 기준 변수를 정한다. : 기준 변수는 N, 반복문에서 2부터 N까지의 변수 i 이다.
3. 반복 적용되는 점화식을 찾는다. : dp[n] = dp[n-1] + dp[n-2]
4. 초기 조건을 찾는다. : n-2>=0 이므로 n이 1일 때와 n이 0일 때의 초기값을 설정해야 한다.
5. 메모이제이션을 구축한다. 
6. Bottom - up 방식으로 반복문을 사용해 DP를 수행한다. 

 

코드

import sys

input = sys.stdin.readline

t = int(input())

for _ in range(t):
  # 문제를 나누는 기준 찾기 
  # 소문제를 나누는 기준은 n 값이다. 
  n=int(input())
  
  # 점화식 찾기
  # 각 0과 1에 대해, 피보나치 정의에 따라 dp[n]=dp[n-1]+dp[n-2] 값이 점화식이다.
  dp0=[0 for _ in range(n+1)]
  dp1=[0 for _ in range(n+1)]
  
  # 초기화 하기
  # 이때, 점화식에 따라 n이 1일 때와 0일 때는 음수가 아닌 정수 값을 가지는 dp 값이 없으므로 초기화 대상이다.
  if n==0:
    print(1,0)
    continue
  elif n==1:
    print(0,1)
    continue
  
  dp0[0], dp0[1] = 1,0
  dp1[0], dp1[1] = 0,1
  
  # 점화식을 사용하여 반복문으로 bottom-up 방식을 사용해 dp0[n] 값과 dp1[n] 값을 계산한다.
  for i in range(2,n+1):
    dp0[i]=dp0[i-1]+dp0[i-2]
    dp1[i]=dp1[i-1]+dp1[i-2]
  
  print(dp0[n], dp1[n])