백준1003🐨피보나치 함수.py - DP, MEMO + 분할 정복

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은 미리 해결해서 주어져 있습니다. 뒤에서는 이 값을 이용해 다음 문제를 풀어가는 식으로 재귀 대신 반복문으로 빠르게 해결합니다.

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

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

Bottom up 상향식 Top down 하향식

for로 구현	재귀함수로 구현
작은 문제를 모아 큰 문제 해결	큰 문제를 해결하기 위해 작은 재귀 함수 호출
점화식 필요	점화식 필요
메모이제이션 없음	메모이제이션 = 캐싱결과 저장용 리스트나 사전을 DP 테이블이라 함.
오버헤드를 줄일 수 있다. 일반적으로 성능이 더 좋다.	오버헤드 가능성이 있다.
(아마도 1,4,5,7,10처럼 해결할 때를 말하는 것 같습니다.)

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

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

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

메모이제이션(Memoization)은 이전에 계산된 결과를 캐시하고 동일한 계산이 다시 필요할 때 캐시된 결과를 반환하는 최적화 기술을 설명하는 용어입니다.

동적 프로그래밍은 재귀적 성격의 문제를 반복적으로 해결하는 기술이며 하위 문제의 계산이 겹칠 때 적용 가능합니다.

동적 프로그래밍은 일반적으로 표를 사용하여 구현되지만 메모이제이션을 사용하여 구현할 수도 있습니다. 보시다시피 어느 쪽도 다른 쪽의 "하위 집합"이 아닙니다.

---

합리적인 후속 질문은 다음과 같습니다. 표 작성(일반적인 동적 프로그래밍 기술)과 메모의 차이점은 무엇입니까?

표 작성을 사용하여 동적 프로그래밍 문제를 해결할 때 문제는 " 상향식 "으로 해결됩니다. 즉, 관련된 모든 하위 문제를 먼저 해결하고 일반적으로 n 차원 테이블 을 채워서 문제를 해결합니다 . 그런 다음 표의 결과를 기반으로 "상위"/원래 문제에 대한 솔루션이 계산됩니다.

문제를 해결하기 위해 메모이제이션을 사용하는 경우 이미 해결된 하위 문제의 지도를 유지함으로써 문제를 해결할 수 있습니다. " 상위 " 문제를 먼저 해결한다는 의미에서 "하향식" 을 수행합니다 (일반적으로 하위 문제를 해결하기 위해 하향식으로 반복됨).

여기 에서 좋은 슬라이드를 볼 수 있습니다 (링크는 이제 사라졌지만 슬라이드는 여전히 좋습니다).

모든 하위 문제를 한 번 이상 해결해야 하는 경우 상향식 동적 프로그래밍 알고리즘은 일반적으로 상수 요소로 하향식 메모 알고리즘보다 성능이 뛰어납니다.재귀에 대한 오버헤드가 없고 테이블 유지에 대한 오버헤드가 적습니다.동적 프로그래밍 알고리즘에서 테이블 액세스의 규칙적인 패턴을 활용하여 시간이나 공간 요구 사항을 더욱 줄일 수 있는 몇 가지 문제가 있습니다.하위 문제 공간의 일부 하위 문제가 전혀 해결될 필요가 없는 경우, 메모된 솔루션은 확실히 필요한 하위 문제만 해결할 수 있는 장점이 있습니다.

<원문: https://stackoverflow.com/questions/6184869/what-is-the-difference-between-memoization-and-dynamic-programming>

그러니까 표를 먼저 다 채우고 시작하면 dp 테이블이라는 것 같습니다.

부분 지도를 모아가는게 메모이제이션이라는 말인 것 같습니다. 😇

분할 정복

재귀를 쓰지 않고 피보나치를 해결하기 위해 행렬연산을 사용할 수 있습니다. 아주 오래 전 샀지만 c를 못 짤 때 사서 못 읽은 <뇌를 자극하는 알고리즘>이라는 책에서 방법을 찾았습니다.

거의 5~6년 전에 샀지만 그때는 C를 잘 못 이해해서 활용하지 못한 책입니다. 찾아보니 피보나치 이야기가 나옵니다. 행렬로 풀 수 있네요. 행렬 연산을 할 일이 거의 없어서 잘 모르는데(문과입니다…) 최근 CV, 딥 러닝 공부할 때 방심하면 가끔 나와서 당황스럽습니다.

책의 내용을 정리하면 아래와 같습니다. 분할 정복 알고리즘이라고 합니다. 문제를 쪼개서 해결하는 방식입니다.

 

$$ \left[ {F_{2}\atop F_{1}} {F_1\atop F_0} \right]=\left[ {1\atop 1} {1\atop 0} \right]라고 하면, $$

$$ n번째는 \left[ {F_{n+1}\atop F_{n}} {F_{n}\atop F_{n-1}} \right]=\left[ {1\atop 1} {1\atop 0} \right]^n $$

$$ 정사각 행렬 A^{nm}=A^nA^m 이므로, $$

$$ n이 홀수면,\left[ {1\atop 1} {1\atop 0} \right]^n=\left[ {1\atop 1} {1\atop 0} \right]^{(n-1)/2}\left[ {1\atop 1} {1\atop 0} \right]^{(n-1)/2}\left[ {1\atop 1} {1\atop 0} \right] $$

$$ n이 짝수면,\\\left[ {1\atop 1} {1\atop 0} \right]^n=\left[ {1\atop 1} {1\atop 0} \right]^{n/2}\left[ {1\atop 1} {1\atop 0} \right]^{n/2} $$

if문이 많은 것을 싫어해서 한 줄로 만들어 봤어요. 홀수 짝수일 때 둘 다 적용되는 수식을 만들어 봤습니다.

$$ \left[ {F_{2}\atop F_{1}} {F_1\atop F_0} \right]=\left[ {1\atop 1} {1\atop 0} \right], \left[ {F_{n+1}\atop F_{n}} {F_{n}\atop F_{n-1}} \right]=\left[ {1\atop 1} {1\atop 0} \right]^n=\left[ {1\atop 1} {1\atop 0} \right]^{[n/2]}\left[ {1\atop 1} {1\atop 0} \right]^{[n/2]}\left[ {1\atop 1} {1\atop 0} \right]^{n \bmod 2} $$

def matrix_multiply(a, b):
    return [[a[0][0]*b[0][0] + a[0][1]*b[1][0], a[0][0]*b[0][1] + a[0][1]*b[1][1]],
            [a[1][0]*b[0][0] + a[1][1]*b[1][0], a[1][0]*b[0][1] + a[1][1]*b[1][1]]]

def matrix_power(matrix, n):
    if n == 1:
        return matrix
    half_power = matrix_power(matrix, n // 2)
    full_power = matrix_multiply(half_power, half_power)
    return matrix_multiply(full_power, [[[1, 0], [0, 1]],matrix][n%2])

def fibonacci_with_count(n):
    if n == 0:
        return (1, 0)
    elif n == 1:
        return (0, 1)
    else:
        result_matrix = matrix_power([[1, 1], [1, 0]], n)
        return (result_matrix[1][1], result_matrix[1][0])

nums = [int(input().strip()) for _ in range(int(input()))]
for n in nums:
    print(*fibonacci_with_count(n))

• 계산이 한 번에 이루어지는 것이 아니라 시간 차를 두고 추가적인 숫자(이전보다 큰 수)가 주어진다면 하향식 접근이 더 빠를 것으로 예상됩니다.

상향식에서 추가로 더 큰 수가 주어질 때 속도를 개선하는 방법을 생각해 보면, 아래와 같이 계산한 적이 없는 부분만 추가로 계산하는 코드로 변형할 수 있습니다.(아이디어가 떠올라서 안 만들 수 없었는데, 당연히 검증되지는 않은 코드입니다.)

아래 경우는…. 상향식일까요 하향식일까요? 🫣 여전히 상향식이겠죠? 작은 문제부터 푸니까요.

하지만 메모이제이션은 쓰인 것 같은데;;; 개념이 어질어질

import sys
nums = [int(n.rstrip()) for n in sys.stdin.readlines()[1:]]
max_num = max(nums)

def update_dp(start, end, dp):
	for i in range(start, end):
        dp.append((dp[i-1][0] + dp[i-2][0], dp[i-1][1] + dp[i-2][1]))

dp = [(1, 0),(0, 1)]

if max_num>len(dp)-1:
    update_dp(len(dp), 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])

#2차 입력값이 주어졌을 때(1차보다 큰 수라고 합시다.)
nums = [int(n.rstrip()) for n in sys.stdin.readlines()[1:]]
max_num = max(nums)

if max_num>len(dp)-1:#이전 dp에 없는 문제가 포함되어서 나오면
    update_dp(len(dp), max_num+1):#이전 dp의 끝부터 씁니다.
        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])

단일 입력값으로 단순화하면 이걸로도 작동하는 코드를 만들 수 있을 것 같습니다. 시간 차 입력이 있을 때(인간입력) 오버헤드를 감수하고 쓸 수 있겠어요.

동적 프로그래밍을 이용하려면 아래 두 조건을 만족해야 합니다.

• 작은 문제가 반복됨
• 같은 문제의 답이 변하지 않음

References

DP(Dynamic Programming) 백준 알고리즘 1003번

동적 프로그래밍(Dynamic Programming) - DP

다이내믹 프로그래밍(Dynamic Programming)이란?

DP : Dynamic Programming : 동적 계획법 : 동적 프로그래밍 : 다이나믹 프로그래밍개념 정리/template/상향

What is the difference between memoization and dynamic programming?

---

예산 프로그램을 만들 때, chat-GPT에게 만든 코드를 주고 성능 향상 방법이나 추천 알고리즘을 물어본 적이 있는데 동적 프로그래밍을 활용하라는 답변을 들은 적이 있습니다. 뭔지 몰라서 적용할 생각을 못 했습니다. 그런데 알고 보니 적용 방법이 어렴풋이 떠오르기는 합니다. 그런데…

예산을 계산하는 과정에서 특정 잔액이 발생했을 때 조합 가능한 경우를 기억하여 한 번에 조합하는 식으로 활용 가능할 수도 있지만 재귀를 쓰지 않았기 때문에 코드가 아주 복잡해 질 것 같습니다. 😱