알고리즘 | 최적화 문제 | 다이나믹 프로그래밍(DP)

다이나믹 프로그래밍

다이나믹 프로그래밍(동적 계획법, 이하 DP)은 복잡한 문제를 작은 하위 문제로 나누어 해결하고, 이를 조합하여 원래의 문제를 해결하는 알고리즘 설계 기법이다. 핵심 아이디어 자체는 분할정복과 동일하다. 

 

1950년대에 리처드 벨먼이라는 응용수학자가 개발했으며, Dynamic 이라는 단어는 그저 멋있어서😂 붙인거고, Programming은 컴퓨터 코드가 아니라 테이블을 이용한 방법을 일컫는 거라고 한다. 

 

개인적으로 DP는 적용 상황을 판단하는 것도 쉽지 않고, 문제 풀이 단계에서 정확한 점화식을 도출하는 게 쉽지않은 것 같다. . 모두 연습만이 살길 !!

 

---

 

어떤 문제에 DP를 적용하는가?

목적을 따지자면, 일반적으로 최적화 문제(optimmization problem)에 DP를 적용한다.

• 최적화 문제: 다양한 해를 가질 수 있음. 각 해중에서 최적(최소 or 최대)의 값인 해를 찾는 문제. 최적의 값을 갖는 해는 여러 개 존재할 수 있음.
• 그 중에서도 최적 부분 구조, 중복 부분 문제 조건을 모두 만족하면 '최적화를 하기에 DP가 효율적이다'라고 할 수 있다. 
• 만일 최적화를 해야하는데 해당 문제가 다른 속성을 갖고 있다면 그리디 알고리즘 등 다른 알고리즘이 더 효율적일 수 있다. 

 

최적 부분 구조? 중복 부분 문제?

내가 이해한 바에 따르면, DP는 결국 n번째 항과 그걸 구하기 위해 필요한 x, y번째 항(x,y < n)의 관계에 대한 점화식을 세울 수 있다면,

즉, 'f(n) = a*f(x) + b*f(y) ..' 등의 점화식으로 설명 가능한 경우 최적 부분 구조를 만족한다고 할 수 있고, 

(뭔가 부분 문제들의 합으로 전체 문제를 해결할 수 있을 것 같은데? 싶으면 의심해보기)

 

그렇게 세운 점화식을 봤더니 f(n)을 구하기 위해 f(x)와 f(y)가 필요한건데, f(x)를 계산하는 과정에서 f(y)의 값이 필요하다든지.. 이렇게 부분 문제들간에도 중복된 관계가 성립될 경우 중복 부분 문제를 만족한다고 할 수 있다. 

(그 구조가 중복적인 부분 문제 호출이 발생하는 것 같으면 DP로 본격적 접근하기)

 

 

각 정의에 대한 자세한 설명은 다음과 같다:

1. 최적 부분 구조 (Optimal Substructure)
   • 전체 문제의 최적 해결책이 그 문제의 부분 문제들의 최적 해결책으로부터 구성될 수 있는 경우
   • (만일 특정 문제가 최적 부분 구조를 갖는지 엄밀히 증명하려면 다음 단계를 거친다.)
     1. 문제에 대한 해는 선택하는 과정으로 만들어짐을 보인다.
     2. 주어진 문제에 대해서 최적해에 이를 수 있는 선택이 주어졌다고 '가정'한다. 이런 선택을 어떻게 결정하는지는 아직 걱정하지 않는다.
     3. 해당 선택에 대해서 발생하는 부분 문제가 어떤 것인지를 정하고 그 부분 문제들의 범위를 가장 잘 표현할 수 있는 방법을 정한다.
     4. 한 개의 최적해에 사용된 부분 문제들의 해가 최적이어야 함을 '잘라 붙이는' 방법을 이용해 보인다. 각 부분 문제들의 해가 최적이 아니라고 가정하고 모순임을 보이면 된다. 각 부분 문제의 최적해가 아닌 부분을 '잘라내고', 거기에 최적해를 '붙이면' 원래의 해보다 좋은 해를 얻게 된다. 
   • 최적 부분 구조는 다음 기준에 따라 형성된다. (전체 문제 = 부분 문제 i * (i의 선택지) + 부분 문제 j * (j의 선택지) ..)
     1. 원래의 문제에 대한 최적해는 몇 개의 부분 문제를 사용하는가
     2. 원래 문제의 최적해에 사용할 부분 문제를 결정할 때 몇 가지 선택을 고려해야 하는가
   • 예시: 최단 경로 문제에서, 전체 경로의 최단 거리는 부분 경로들의 최단 거리로부터 구성된다.
2. 중복 부분 문제 (Overlapping Subproblems)
   • 동일한 부분 문제가 반복해서 발생하는 경우
   • 예시: 피보나치 수열에서, n번째 항을 구하기 위해 (n-1)번째 항과 (n-2)번째 항을 계산해야 하며, 이러한 계산이 반복됨.

 

DP vs 분할정복

중복 부분 문제가 있는 경우, 분할정복은 공유되는 문제를 반복적으로 해결하여 필요 이상의 리소스를 낭비하게 된다.
대표적인 예시가 피보나치 수열을 구하는 문제이다. 이러한 경우 DP의 방식(이전 단계의 해답을 테이블에 저장)이 월등하게 효율적이다.

- 분할정복: 문제를 서로 겹치지 않는(disjoint, non-overlap) 부분 문제로 분할하고 -> 해당 부분 문제를 재귀적으로 해결 -> 해결 결과를 결합하여 원래의 문제를 해결

- DP: 부분 문제가 서로 중복될 때(non-disjoint, overlap), 즉 부분 문제가 다시 자신의 부분 문제를 공유할 때 적용할 수 있다

 

DP를 구현하는 핵심 개념

DP를 적용하기 전에 이해해야 할 핵심 개념은 다음 3가지이다: 1) 점화식, 2) 메모이제이션, 3) 타뷸레이션

 

1. 점화식 (Recurrence Relation: 재귀 관계)
   • 문제를 부분 문제로 나누고, 이 부분 문제들의 관계를 수학적으로 표현한 식
   • 예시: 피보나치 수열의 점화식은 f(n) = f(n-1) + f(n-2)로 표현할 수 있다.
2. 메모이제이션 (Memoization) <- Top-down
   • 메모이제이션은 이전에 계산한 결과를 메모리에 저장하여 중복 계산을 방지하는 기법
   • 예시: 피보나치 수열에서 n번째 항을 구할 때, 이전에 계산한 항들의 값을 저장하여 중복 계산을 피한다.
3. 테이블 방식 (Tabulation, 타뷸레이션) <- Bottom-up
   1. 테이블 방식은 작은 부분 문제부터 해결하며 테이블을 채워나가는 기법
   2. 반복문을 사용하여 부분 문제의 해결책을 테이블에 저장하며, 이후의 더 큰 부분 문제를 해결할 때 이 테이블을 참조
   3. 예시: 피보나치 수열에서 n번째 항을 구할 때, 0번째 항과 1번째 항부터 시작하여 n번째 항까지 테이블을 채워나간다.

 

문제 접근 방식

DP 알고리즘을 개발할 때는 위 핵심 개념을 활용하며, 다음 4단계를 따른다.

1. 최적해의 구조의 특징 찾기
   1. 주어진 문제가 '최적 부분 구조'를 갖는지, 또 '중복 부분 문제'인지를 판단한다. (DP 적용 여부 판단)
   2. 그렇다면 최적해를 찾기 위해 문제를 어떻게 분해할지를 고민한다.
2. 최적해의 값을 재귀적으로 정의
   1. '점화식'을 통해 문제와 부분 문제들 간의 관계를 수학적으로 표현한다. 
   2. 이는 DP 알고리즘의 기본적인 구조가 된다. 
3. 최적해의 값을 bottom-up(일반적) 또는 top-down으로 계산
   1. '테이블 방식(bottom-up)' 혹은 '메모이제이션 방식(top-down)'을 활용하여 계산을 수행한다.
4. 계산된 정보들로부터 최적해를 구성

 

1-2번 단계를 거치며 구조에 대한 분석과 점화식 설계가 끝났다면, 3번에 해당하는 실제 계산 코드 구현을 해야한다.

1-3 단계가 DP 해를 구하는 기초가 되고, 4단계는 해의 값만 필요로 하는 경우 생략 가능하다.

 

 

코드로 이해하기

3단계(계산) 코드를 어떻게 구현할까? 우선 피보나치 수열에 대해 바텀 업(테이블 방식)과 탑 다운(메모이제이션) 각각으로 해결한 코드를 이해해보자. 

 

바텀 업 (Bottom-up)

바텀 업은 반복문을 사용해서 작은 문제부터 순차적으로 올라오는 방식이다. 

이 방식에서는 부분 문제의 해결책을 테이블에 저장하고, 이를 사용하여 큰 부분 문제의 해결책을 도출한다. 

 

# 바텀 업
def fibonacci(n):
    dp = [0, 1] + [0] * (n - 1)
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

# 피보나치 수열의 10번째 항 구하기
result = fibonacci(10)
print(result)  # 55

 

for문이 돌아감에 따라 dp 배열은 다음과 같이 채워져간다.

 

[0 1 0 0 0 0 0 0 0 0 0] -> [0 1 1 0 0 0 0 0 0 0 0] -> [0 1 1 2 0 0 0 0 0 0 0] -> [0 1 1 2 4 0 0 0 0 0 0] ... 

 

미리 세팅한 0, 1번 인덱스를 제외하면, 2번 인덱스부터 순차적으로 값을 완성시키며 올라가는 방식이다. 

 

 

탑 다운 (Top-down)

탑 다운은 재귀를 사용하여 부분 문제를 해결한다.

그리고 각 부분 문제의 답을 배열(리스트) 혹은 해시테이블(딕셔너리)에 저장하여 중복계산을 방지한다(메모이제이션).

 

리스트가 유리한 경우

• 점화식을 세워봤더니 연속적인 부분 문제(예: f(n-1), f(n-2), f(n-3) ...)를 해결해야 하는 경우
• 리스트는 연속적으로 메모리 공간을 채워넣기 때문에, 문제 크기가 n이면 리스트 크기도 n 정도가 된다. 
• 이 경우, 공간복잡도 시간복잡도 측면에서도 그렇고, 해시 충돌이 없다는 면에서도 딕셔너리를 사용할 이유가 딱히 없다. 

 

딕셔너리가 유리한 경우

• 점화식을 세워봤더니 불연속적인 부분 문제(ex: f(2n), f(3n), f(4n) ...)를 해결해야 하는 경우
• 이 경우 리스트를 활용하면 불필요한 배열 공간이 많이 낭비된다.
• 딕셔너리는 키를 활용하기 때문에 불연속적인 값에 빠르게 접근할 수 있다.

 

나는 딕셔너리로 구현하는 법을 연습하기로 했다. 그 이유는: 

1. 리스트를 사용하는 게 유리한 경우는 애초에 바텀 업으로 접근하는 게 더 수월한 것 같다.

2. 일반적인 상황에서는 해시 충돌을 크게 걱정할 일이 없다. 

3. 같은 탑 다운에서도 케이스를 나누느니, 연속적인 문제 뿐 아니라 불연속적 문제에도 일괄적으로 적용가능한 딕셔너리가 단순하다.

 

따라서, 딕셔너리를 활용한 탑 다운 방식으로 피보나치를 구현하면 아래와 같다. 

# 탑 다운 (dict)
def fibonacci(n, memo={}):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
    return memo[n]

# 피보나치 수열의 10번째 항 구하기
result = fibonacci(10)
print(result)  # 55

 

 

fibonacci(10)을 먼저 요구받고, 이를 해결하기 위해 fibonacci(9)와 fibonacci(8)의 답을 요구하고.. 다시 이들을 해결하기 위해 하위 부분 집합의 답을 요구하고 ..의 재귀적 반복이다. 

 

memo 라고 이름붙인 딕셔너리에 각 i번째 시도의 결과값을 저장해놓고, 만일 상위 문제에서 fibonacci(i)의 답을 요구한다면 memo[i]를 리턴한다. 이를 통해 i에 대한 계산은 한번으로 끝내고, 그 이후에는 딕셔너리에 접근하는 O(1)의 시간복잡도만으로 해결할 수 있게 된다. 

(해시충돌이 극한으로 발생한다면 체이닝을 통해 결국 연결 리스트를 타고 접근하게 되기 때문에 최악의 경우 O(n)이지만, 사실상 이론적으로만 가능한 상황이다.)

 

탑 다운 방식은 재귀를 사용하는 방식 때문에 작동 구조가 분할정복과 더욱 유사해보인다. 그러나 중복 부분 문제 여부와 이를 해결하기 위해 메모이제이션을 활용하는지 여부가 가장 핵심적인 차이점이다. 그 외에도 최적 부분 구조 개념이 분할정복에서는 중요치 않다는 차이점도 있다.