Dynamic Programming이 하는 일은? 도달경로의 경우의 수 찾기. 피보나치 예시(2/3)

아래 포스팅에서 이어서 작성하였습니다.

https://blog.naver.com/devramyun/223997724675

Devramyun's blog : 네이버 블로그 매 순간 기대되는 장소와 방향을 바라보며, 그 곳에 가는 동안 겪는 시행착오와 배움의 과정을 꾸준히 기록하는 블로그 입니다. https://github.com/southglory https://blessflow.com https://quirkagames.com https://kualkafoundry.com 매 순간 기대되는 장소와 방향을 바라보며, 그 곳에 가는 동안 겪는 시행착오와 배움의 과정을 꾸준히 기록하는 블로그 입니다. https://github.com/southglory https://blessflow.com https://quirkagames.com https://kualkafoundry.com

---

DP를 소개하는데 피보나치를 예로 드는 이유는 다음과 같습니다.

피보나치도 DP가 푸는 점화식으로 바꿀 수 있습니다.

좀 더 일반화된 형태는 개구리 점프 문제였습니다. 이전 포스팅에서 소개드렸죠. 아래를 보시면 개구리 점프 문제 안에 피보나치 수열 문제가 포함됩니다.

그럼 이제 간단한 피보나치 문제를 풀면서 DP방식을 소개해드리겠습니다.

피보나치를 푸는 3가지 방법

순수 재귀 vs 재귀+메모이제이션(탑다운dp) vs 테이블채우기(바텀업dp)

• 순수 재귀

def fib(n):
    if n == 0: return 0
    if n == 1: return 1
    return fib(n-1) + fib(n-2)

1. 재귀+메모(탑다운방식dp)

def fib_memo(n, memo={}):
    if n in memo:
        return memo[n]
    if n == 0: return 0
    if n == 1: return 1
    memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
    return memo[n]

메모장 클래스 만들어놓고 메모장 읽고 쓰기 구현해놓으면 더 직관적이고 재밌겠네요.ㅎㅎ

1. 테이블채우기(바텀업방식dp)

바텀업 DP는 테이블을 완성해나가는 게 핵심입니다. 아래에서부터 위로 차근차근 점화식을 따라 계산이죠.

def fib_dp(n):
    dp = [0] * (n+1)
    dp[0] = 0
    dp[1] = 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

print(fib_dp(10))  # 55

바텀업 방식은 미리 dp테이블을 n+1만큼 만들어놓습니다. n이 아니고 n+1개인 이유는, 맨 처음 초기 위치를 기준점으로 0으로 항상 저장해두기 위함입니다. 나머지 n개도 0으로 초기화 해놓기는 합니다. 한 번 개구리 문제처럼 더 일반화된 코드로 풀어볼까요?

def fib_with_frog_style(n):
    S = [1, 2]  # 개구리 점프 가능한 거리
    dp = [0] * (n+1)
    dp[0] = 0
    dp[1] = 1
    for j in range(2, n+1):
        for s in S:
            if j - s >= 0:
                dp[j] += dp[j - s]
    return dp[n]

print(fib_with_frog_style(10))  # 55

이렇게 정리해두고 보니 Dynamic programming을 좀 더 잘 알게 된 것 같긴 한데, 코드를 작성할 때 구현이 잘 생각나려면 연습이 필요하겠네요.

#DP, #다이나믹프로그래밍, #탑다운, #바텀업, #메모이제이션, #DP테이블채우기, #피보나치, #점화식, #재귀, #재귀함수, #알고리즘