[자료구조&알고리즘 | WEEK04] 다이나믹 프로그래밍(dynamic programming, DP)

다이나믹 프로그래밍(dynamic programming, DP)이란?

---

다이나믹 프로그래밍은(DP) 특정 범위까지의 값을 구하기 위해 그것과 다른 범위까지의 값을 이용하여 효율적으로 구하는 알고리즘 설계 기법이다. 앞에서 구했던 답을 뒤에서도 이용하고, 또 그 뒤에서도 이용할 수 있다. 쉽게 말해서는 답을 재활용하는 것이고, 같은 말로 프로그래밍 영역에서는 메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법이다. DP는 구체적인 알고리즘이라기 보다는 문제해결 패러다임에 가깝다.
DP는 아래와 같은 특징이 있다.

• 이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함
• DP의 구현은 일반적으로 두 가지(탑다운 - 하향식, 바텀업 - 상향식) 방식으로 구현함

 

'동적'이라는 오해

다이나믹 프로그래밍은 동적 계획법이라고도 불린다.

 

💡

동적계획법이란

"어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용"

하는 방식의 알고리즘을 총칭한다.

 

일반적인 프로그래밍 분야에서 동적(Dynamic)이란 어떤 의미일까?

자료구조에서 동적 할당(Dynamic Allocation)은 '프로그램이 실행되는 도중에 실행에 필요한 메모리를 할당하는 기법'을 의미한다. 아래는 C언어 기준으로 동적 할당의 장점과 단점이다.

• 장점: 상황에 따라 원하는 크기만큼의 메모리가 할당되고 이미 할당된 메모리라도 언제든 크기 조정이 가능
• 단점: 더 이상 사용하지 않을 때 명시적으로 메모리를 해제해 주어야한다.

반면 다이나믹 프로그래밍에서 '다이나믹'은 별다른 의미 없이 사용된 단어이다.(이름이 멋있어보여서 )

 

(중요!) 다이나믹 프로그램의 조건

다이나믹 프로그래밍은 문제가 다음의 조건을 만족할 때 사용할 수 있다.

최적 부분 구조(Optimal Substructure)

• 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아 큰 문제를 해결할 수 있다.

중복되는 부분 문제(Overlapping Subproblem)

• 동일한 작은 문제를 반복적으로 해결해야한다.

 

피보나치 수열과 같은 문제가 위에서 언급한 다이나믹 프로그램의 조건에 부합한다.

 

 

위의 이미지처럼 각각의 피보나치 수는 앞의 있는 두 수의 합으로 구성된다는 사실을 알 수 있는데,
이처럼 각각의 항이 인접한 다른 항들 간의 관계식을 수학적으로 나타내는 것이 점화식이다.

꼭 인접한 다른 항들 간의 관계식을 나타낸 것이 점화식이 아니라, 어떤 문제를 해결할 때 관계식을 표현할 수 있다면 그게 점화식이 된다.
위의 피보나치 수열 이미지는 아래와 같은 점화식으로 나타낼 수 있다.

$$
f(n) = f(n - 1) + f(n-2)
$$

 

위와 같은 점화식을 그대로 코딩에 적용할 순 있다.
바로 재귀적으로 표현하면 되는 것인데 아래와 같이 표현할 수 있다.

def fivo(n):
    if n == 1 or n == 2:
        return 1
    return fivo(n - 1) + fivo(n - 2)

# n: 10
# answer: 55

 

메모이제이션(Memoization)

---

하지만 위와 같이 연산을 수행하게 되면 불필요한 연산을 수행하게 된다.
아래 이미지는 위에서 재귀적으로 코딩한 부분을 시각적으로 나타낸 것인데, 얼핏 보기에도 새로운 값을 구하기 위해 이전에 이미 계산했던 값들을(같은 색끼리) 여러 번 계산하고 있는 것을 알 수 있다.

 

 

DP와 재귀의 가장 큰 차이점은 일반적인 재귀를 사용 시 동일한 작은 문제들이 여러 번 반복되어 비효율적인 계산을 이룬다는 점이고, DP를 사용할 시 이미 계산했던 부분은 계산하지 않고, 재활용하는 것이다.

바로 메모이제이션이 이런 재활용의 역활을 가능하게 해준다. 명칭부터 '메모'라는 표현이 있는데 이전의 값들을 메모한다는 개념으로 쓰이는 것 같다. 따라서 메모제이션을 정의하자면 '한 번 계산한 결과를 메모리 공간에 메모'하는 기법이라고 표현할 수 있다.
메모이제이션은 아래와 같은 특징이 있다.

• 같은 문제를 다시 호출하면 메모했던 결과를 그대로 가져온다.
• 값을 기록해 놓는다는 점에서 캐싱(Caching)이라고도 한다.

실제로 다이나믹 프로그래밍을 이용하여 문제를 해결할 때 변수명을 dp, memo, table 등으로 변수명을 설정한다.

 

탑다운(하향식) vs 보텀업(상향식)

• 탑다운(메모이제이션) 방식은 하향식이라고도 하며 보텀업 방식은 상향식이라고도 한다.
  • 탑다운 방식은 큰 문제를 해결하기 위하여 작은 문제를 재귀적으로 호출하여 그 작은 문제가 모두 해결되었을 때 실제로 큰 문제의 답까지 얻을 수 있도록 하는 방식
  • 보텀업 방식은 아랫쪽에서 작은 문제를 하나씩 해결해나가면서 먼저 계산했던 문제들의 값을 확인 후 그 다음의 문제까지 해결한다는 특징이 있다. 따라서 보텀업 방식의 구현은 프로그래밍 언어에서 for문으로 구현하게 된다.
• 다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식이다.
  • 결과 저장용 리스트는 DP 테이블이라고 부른다.
• 엄밀히 말하면 메모이제이션은 이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미한다.
  • 따라서 메모이제이션은 다이나믹 프로그래밍에 국한된 개념은 아니다. 예를 들어 이전에 계산한 결과를 다시 사용하게 되면 "우리는 메모이제이션 기법을 사용했다, 캐시를 사용했다" 으로 표현할 수 있다.
  • 즉, 한 번 계산된 결과를 담아 놓기만 하고 다이나믹 프로그래밍을 위해 활용하지 않을 수 있다.

 

그럼 재귀적으로 불필요한 연산까지 수행하면서 풀었던 위의 코드를 아래와 같이 코드로 나타낼 수 있다.

아래의 방식은 탑다운인 하향식의 표현이다.

# 탑다운(하향식) 표현
memoization = [0] * (N + 1)

def sol(n):
    if n == 1 or n == 2:
        return 1

    if memoization[n] != 0:
        return memoization[n]

    memoization[n] = sol(n - 1) + sol(n - 2)
    return memoization[n]

print(sol(N))

같은 재귀적인 방법이지만, 두 번째 if문으로 인해 이미 계산된 값은 더 이상 재귀적으로 들어가지 않고, 바로 값을 불러내는 방식이다. 이로 인해 N의 값이 커질수록 연산 수를 대폭 줄일 수 있다.

 

다음은 보텀업 방식인 상향식의 표현이다.

N = int(input())

dp = [0] * (N + 1)
dp[1] = 1
dp[2] = 1

for i in range(3, N + 1):
    dp[i] = dp[i - 1] + dp[i - 2]

print(dp[N])

작은 문제를 먼저 해결해 놓은 다음에, 먼저 해결해 놓았던 값을 이용하여 큰 문제를 해결하였다.(상향식)

 

 

다이나믹 프로그래밍 VS 분할 정복 - 공통점과 차이점

---

공통점

다이나믹 프로그래밍과 분할 정복은 모두 최적 부분 구조를 가질 때 사용할 수 있다.

즉, 큰 문제를 작은 문제로 나눌 수 있으며, 작은 문제의 답을 모아서 큰 문제를 해결할 수 있는 상황

차이점

다이나믹 프로그래밍과 분할 정복의 차이점은 부분 문제의 중복이다.

다이나믹 프로그래밍 문제에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복된다.

예를 들어 위와 같은 피보나치 수열의 문제다. 각 n번 째의 값을 구하기 위해 이전의 값이 필요했고, 효율적인 계산을 위해 다이나믹 프로그래밍을 이용했다.

하지만 분할 정복 문제에서는 동일한 부분 문제가 반복적으로 계산되지 않는다. 예를 들어 이전 포스트에서도 언급한 병합 정렬에서도 분할 정복이 사용되는데, 하나의 통으로 되어있는 배열 자체를 나눌 수 없을 때까지 쪼개고 쪼개서 작은 문제로 만들었고(분할), 잘게 쪼개어진 원소들 간의 정렬을 이루었다(정복). 그리고 이러한 해결된 문제들을 합쳐(조합) 큰 문제를 해결하였다. 이때 문제를 잘게 쪼개어 원소들 간의 정렬을 이루면, 그 다음에는 이전에 해결했던 작은 문제를 다시 반복적으로 계산하지 않는다.

 

 

 

 

 

---

Ref

나무위키 - 동적계획법
유튜브 - 이코테
파이썬 알고리즘 인터뷰