1003번: 피보나치 함수

와 피보나치다! CPP 코드도 줬네? 전역변수 써서 더하면 되잖아 하고 풀다가 뭔가 이상함을 감지했습니다. 게다가 라이브러리 문제로 컴파일 에러도 났습니다. 나중에 의도대로 수정해 보니 역시 시간초과입니다.

#include <iostream>
int zeros, ones;

int fibonacci(int n) {
    if (n == 0) { zeros++;return 0;}
    else if (n == 1) {ones++;return 1;}
    else {return fibonacci(n - 1) + fibonacci(n - 2);}}

int main() {
    int numberOfLines; std::cin >> numberOfLines;

    for (int i = 0; i < numberOfLines; ++i) {
        int number;
        std::cin >> number;
        zeros = 0;ones = 0;
        fibonacci(number);
        std::cout << zeros << " " << ones << std::endl;}
    return 0;}

Dynamic Programming, Memoization

스터디에서 동적 프로그래밍을 활용해서 풀어야 한다는 것을 듣고 나서야 문제를 이해했고,

반복되는 계산에서 이미 구한 값은 저장해서 사용하는 것으로 이해했습니다.

그리고 파이썬으로 바꾸었습니다.

import sys
nums = [int(n.rstrip()) for n in sys.stdin.readlines()[1:]]#입력 읽기(데이터 수 버림)
max_num = max(nums) #입력된 수 중 최대값 찾기

dp = [(1, 0),(0, 1)] # f(1)과 f(2)에 대한 기본값 저장
if max_num>1: # 최대값이 기본값 이상이면 해당 값까지 수열(0과 1의 등장 횟수 수열) 추가
    for i in range(2, max_num+1):
        dp.append((dp[i-1][0] + dp[i-2][0], dp[i-1][1] + dp[i-2][1]))
for n in nums: # 생성된 값을 꺼내 쓴다.
    print(dp[n][0], dp[n][1])

이 문제에서는 계산할 숫자가 한꺼번에 주어지는 점을 이용해서 한 번에 입력을 받고

최댓값을 찾은 뒤 최댓값에 대해 연산하면서 dp 변수에 연산 결과를 저장하고

그것을 꺼내어 쓰는 식으로 해결했습니다.

이런 동적 프로그래밍에는 상향식과 하향식이 있습니다.

• 상향식(Bottom-Up): 가장 작은 하위 문제부터 시작하여 점차 큰 문제로 확장해 나가며, 각 단계의 결과를 저장합니다. 아래에서 case 0과 case1은 미리 해결해서 주어져 있습니다. 뒤에서는 이 값을 이용해 다음 문제를 풀어가는 식으로 재귀 대신 반복문으로 빠르게 해결합니다.

  dp = [(1, 0),(0, 1)] #초기의 간단한 문제로 출발

      for i in range(2, max_num+1):
          dp.append((dp[i-1][0] + dp[i-2][0], dp[i-1][1] + dp[i-2][1]))
  

  위 부분에서는 해결된 기본 문제를 바탕으로 점점 큰 문제를 해결합니다. 재귀로 푸는 대신 점화식에 의한 반복문으로 점점 복잡한 답을 구하고 그 과정에서 dp표가 완성됩니다. 4를 예로 들면, 아래처럼 문제를 차례로 풀며 수열이 생성됩니다.

  dp[2] = (dp[1][0] + dp[0][0], dp[1][1] + dp[0][1]) = (1+0,0+1) = (1, 1)
  dp[3] = (dp[2][0] + dp[1][0], dp[2][1] + dp[1][1]) = (1+1,1+1) = (1, 2) 
  dp[4] = (dp[3][0] + dp[2][0], dp[3][1] + dp[2][1]) = (1+1,2+1) = (2, 3)
  

• 하향식 접근 : 먼저 문제를 풀면서 메모하고, 그 과정에서 생성된 부분 문제의 결과를 이용하는 것이 하향식 접근입니다.

  def fibonacci(n, dp):
      if n in dp:
          return dp[n]
      if n == 0:
          dp[n] = (1, 0)
          return dp[n]
      elif n == 1:
          dp[n] = (0, 1)
          return dp[n]
      else:
          a, b = fibonacci(n-1, dp)
          c, d = fibonacci(n-2, dp)
          dp[n] = (a + c, b + d)
          return dp[n]
  
  nums = [int(input().strip()) for _ in range(int(input()))]
  dp = {}
  
  for n in nums:
      print(*fibonacci(n, dp))
  

  메모이제이션(Memoization):

  • 메모이제이션은 동적 프로그래밍의 하향식 접근법에서 사용되는 기법입니다. 계산 결과를 저장하여, 동일한 계산이 재차 필요할 때 이미 저장된 값을 재사용함으로써 계산 시간을 줄입니다.
  • 메모이제이션은 일반적으로 재귀 함수를 사용하는 동적 프로그래밍 문제에 적용되며, 결과를 저장하기 위해 데이터 구조(예: 배열, 딕셔너리)가 필요합니다.
  • 이 기법은 동적 프로그래밍의 전반적인 접근 방식의 일부로 사용되기도 하지만, 다른 문맥에서도 사용될 수 있습니다.
  • 위 코드를 살펴보면 기본적인 피보나치 재귀함수가 그대로 사용되고 있습니다. 대신 해결 과정에서 메모를 하는 것을 볼 수 있습니다.
  • 대신 재귀를 이미 해결한 수준의 문제가 나올 때 까지만 계산하고 딕셔너리에 있는 문제가 나오면 이전 결과를 반환해 줍니다.

DP와 메모이제이션의 차이를 챗지피티한테 물으니 비슷한데 다르다고 해서 검색을 해 봤습니다.

<표 원문 출처: https://chae52.tistory.com/206> 일부 수정

표를 보다보니 그럼 dp 테이블과 메모이제이션은 같은건가? 하는 생각이 들어 에게 물어보니 또 다르답니다. 미심쩍어서 찾아보니 스택 오버플로에 관련 주제가 (당연히) 있습니다.

메모이제이션과 동적 프로그래밍의 차이점은 무엇입니까?