[알고리즘] 다이나믹 프로그래밍 (feat. Leetcode)

다이나믹 프로그래밍이란?

---

큰 문제를 작은 문제로 나누어 풀고, 작은 문제의 답을 재활용하는 기법을 의미한다.

메모리 비용을 활용하여 시간적 비용을 줄이는 방식이다.

 

👉 조건

1. 부분 반복 문제: 작은 문제가 반복되는 경우
2. 최적 부분 구조: 같은 문제는 구할 때마다 정답이 같을 경우

작은 문제가 반복되고 그 문제의 답이 같기 때문에, 굳이 작은 문제에 대한 계산을 반복하지 않고 이를 메모리에 저장하여 활용하는 것이다.

 

 

Fibonacci 수열

---

DP를 설명할 때 가장 기본적으로 예를 들 수 있는 것이 Fibonacci 수열이다. 이는 f(n) = f(n-1) + f(n-2)의 점화식을 가진다. 

아래 Leetcode 문제를 재귀 함수를 이용하는 방법과 동적 프로그래밍을 사용하는 방법으로 풀어볼 것이다. 

https://leetcode.com/problems/fibonacci-number/

Fibonacci Number - LeetCode

 

1️⃣ 재귀함수 사용

def fib(self, n):
    def fibo(n):
        if n == 1:
            return 1
        elif n == 2:
            return 1
        else:
            return fibo(n-1) + fibo(n-2)

    return fibo(n)

위 코드를 도식화한 이미지

 

재귀 함수로 풀게 되면 간단하게 풀 수 있지만, 위의 그림에서 확인할 수 있듯이 호출되는 함수의 수가 기하급수적으로 증가한다.

해당 코드를 제출하게 되면 아래와 같이 Runtime Error가 나타난다. 😥 

 

 

2️⃣ 동적 프로그래밍 사용

💡 이 문제를 DP로 풀 수 있지 않을까? 위의 조건을 생각해보자

1. 부분 반복 문제
   fib(7)을 구하기 위해서는 fib(6)와 fib(5)가 필요하다. 그리고 fib(6)을 구하기 위해서는 fib(5)와 fib(6)이 필요하다. 이 경우 살펴보면 fib(7)과 fib(6)에서 fib(5)가 반복된다. 즉, 작은 문제가 반복되는 구조라고 볼 수 있다.
   
   
2. 최적 부분 구조
   fibo 수열의 경우 1번째/2번째 수는 각각 1로 고정되어 있으며 3번째 수열은 언제나 결과가 2이다. 그 이후로도 이전의 두 개의 값을 더하여 계산함으로 fibo 수열에서 어떤 수를 구할 때나 수열의 값이 같다.

 

방법

1. 모든 작은 문제들은 한번만 푼다. 이를 위해 정답을 구한 작은 문제의 결과는 어딘가 저장한다.
2. 다시 그보다 큰 문제를 풀어나갈 때 똑같은 문제가 나타나면 앞서 저장한 결과 값을 이용한다.

 

def fib(self, n):
    fibo = [None,1,1]

    if n < 3:
        return fibo[n]

    for i in range(3, n+1):
        fibo.append(fibo[i-1] + fibo[i-2])

    return fibo[n]

성공!

 

 

Bottom-up과 Top-down

---

1. Bottom-up
   • 작은 문제부터 차근차근 구해나가는 방법이다.
   • 소스의 가독성이 저하될 수 있다.
     
     
2. Top-down
   • 큰 문제를 풀다가 작은 문제가 아직 풀리지 않았다면 그때 작은 문제를 해결한다. 재귀 함수로 구현하는 경우 대부분 Top-down이다.
   • 소스의 가독성이 증가하지만, 작성이 조금 어렵다.

 

 

 

참고
https://galid1.tistory.com/507
https://kyun2da.github.io/2020/01/19/DynamicProgramming/