동적 계획법(Dynamic Programming)

Goal

• 동적 계획법에 대해 설명할 수 있다.

---

동적 계획법(Dynamic Programming)

복잡한 문제를 여러 개의 작은 문제로 나누어 푸는 방법을 말한다.

 

분할 정복과의 차이점

동적 계획법과 분할 정복의 가장 큰 차이점은 계산 결과의 재활용이다. (부분 문제를 각각 독립적으로 나눠지지 않음)

동적 계획법의 경우 두 번 이상 계산되는 중복되는 부분 문제(overlapping subproblems)의 계산 결과를 캐시에 저장함(재활용)으로써 여러번 계산되는 것을 막아 속도 향상을 꾀할 수 있다.

이때, 한번 계산된 결과같은 캐시에 저장하는 최적화 기법을 메모이제이션(momoization)이라고 한다.

 

구분 하자면 다음과 같다.

• 부분 문제를 비슷한 크기로 나누고, 각각을 독립적으로 나누어 푼다.
• 큰 문제를 작은 문제로 나누고, 중복 되는 문제에 대해 캐싱하여 최적화를 시킨다 => 다이나믹 프로그래밍

 

*메모이제이션과 캐싱

캐시 : 계산 결과 및 사용 가능성이 있는 값을 저장하는 저장 공간

 

메모이제이션 : 계산 결과를 캐시에 저장

캐싱 : 캐시 지역성(cache locality)에 따라 데이터를 캐시에 저장. (필요할 것 같은 값이나 계산 결과를 저장)

 

메모이제이션은 계산된 결과값을 저장하는 것에 한해 통용되는 최적화 기법이다.

반변 캐싱은, 계산 결과 뿐만 아니라 필요할 것 같은 데이터를 미리 가지고 있는 최적화 기법이다.

 

메모이제이션을 적용할 수 있는 경우

메모이제이션은 참조적 투명성이 보장되는 경우 적용할 수 있다.

• 참조적 투명성 : 결과값이 입력 값만으로 결정되는 경우를 참조적 투명성(referential transparency)이라고 한다.
• 참조적 투명 함수 : 입력이 고정되어 있을 때, 그 결과가 항상 같은 함수 (참조적 투명성이 보장되는 함수)

수학에서의 함수와는 다르게 프로그래밍에서의 함수는 입력값 이외에 외부적인 요소(전역 변수, 클래스 멤버 변수 등)에 영향을 받을 수 있기 때문에 동일한 입력값에 대해 항상 같은 결과 값을 반환한다고 보장할 수 없다.

당연한 얘기지만, 메모이제이션은 동일한 입력값에 대해 항상 같은 결과 값을 반환하는 즉, 참조적 투명 함수의 경우에만 적용할 수 있다.

 

메모이제이션 구현 패턴

1. 기저 사례(base case)에 대한 처리. ex) 입력이 범위를 벗어난 경우 등을 기저 사례로 처리
2. 참조형'&' 변수의 사용. => 다차원 배열을 사용할 때 유용. (인덱스 사용하지 않아도 되고 이름을 단축시킬 수 있음)

 

동적 계획법의 사용처

동적 계획법은 최적화 문제의 해답을 빨리 찾기 위해 노력하는 과정에서 고안되었다. 그래서 동적 계획법을 논할 때 최적화 과정을 가장 부각시켜 설명한다.

 

동적 계획법은 중복되는 부분 문제와 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다.

즉, 중복 부분 문제와 최적 부분 구조를 갖는 문제의 경우 동적 계획법을 적용할 수 있다는 뜻이다.

 

중복되는 부분 문제(overlapping subproblems)

나눠진 부분 문제가 중복되는 경우로, 메모이제이션 기법을 사용해 중복 계산을 없앤다.

 

최적 부분 구조(optimal substructure)

전체 문제의 최적해가 각 부분 문제들의 최적해로 이루어진 경우로,

이런 구조는 '최적 부분 구조를 갖는다.'고 할 수 있다.

 

반면, 각 부분 문제들의 최적해만으로 전체 문제의 최적해가 될 수 없는 경우,

해당 문제는 '최적 부분 구조가 존재하지 않는다.'고 할 수 있다.

 

동적 계획법 구현 방법 (풀이 관점의 차이)

• Top-down : 큰 문제부터 시작해서 작은 문제로 분할해 가면서 풀어 나가는 방식. 위에서 아래로 진행
• Bottom-up : 작은 문제들을 쌓아 올려 큰 문제를 풀어 나가는 방식. 아래에서 위로 진행

 

Top-down 방식

• 큰 문제를 작은 문제로 나눈다. => 큰 문제를 작은 문제로 분할해 가면서 풀이
• 작은 문제를 푼다.
• 작은 문제를 풀었으니 큰 문제를 풀 수 있다.

Top-down방식은 재귀 함수를 사용해서 구현할 수 있다.

메모이제이션 기법 사용

 

Bottom-up 방식 

• 문제 크기가 작은 문제부터 푼다.
• 문제 크기를 점점 키워나가면서 푼다. (작은 문제를 풀면서 왔기 때문에 큰 문제는 항상 풀 수 있다)
• 반복하다 보면 가장 큰 문제를 풀 수 있다.

Bottom-up 방식은 반복문 형태로 구현할 수 있다.

tabulation 또는 sliding window 기법 사용

 

참고) memoization, tabulation, sliding window

*memoization : 계산이 필요한 순간 계산해서 저장

*tabulation : 미리 값을 다 구해놓는 방식

 

memoization vs sliding window

메모이제이션(memoization) 기법 : 부분 문제 계산 순서가 일정하지 않음. 공간 복잡도가 큼.

슬라이딩 윈도우(sliding window) 기법 : 부분 문제 계산 순서가 일정, 공간 복잡도를 O(1)로 사용할 수 있음

 

*투 포인터, 슬라이딩 윈도우

 

참고) 재귀적 동적 계획법과 반복적 동적 계획법 비교

1. 재귀적 동적 계획법의 장단점

장점

• 좀 더 직관적인 코드를 짤 수 있다.
• 부분 문제 간의 의존 관계나 계산 순서에 대해 고민할 필요가 없다.
• 전체 부분 문제 중 일부의 답만 필요할 경우 더 빠르게 동작한다.

단점

• 슬라이딩 윈도 기법을 쓸 수 없다.
• 스택 오버 플로우를 조심해야 한다.

 

2. 반복적 동적 계획법의 장단점

장점

• 구현이 대게 더 짧다.
• 재귀 호출에 필요한 부하가 없기 떄문에 더 빠르게 동작한다.
• 슬라이딩 윈도 기법을 쓸 수 있다.

단점

• 구현이 좀더 비직관적이다.
• 부분 문제 간의 의존 관계를 고려해 계산되는 순서를 고민해야 한다.

---

피보나치 수열로 알아보는 동적 계획법

수식으로의 표현 (피보나치 수열의 점화식 표현)

1. $F_{0}=0$
2. $F_{1}=1$
3. $F_{n} = F_{n-1} + F_{n-2}$ (n >= 2)

*점화식(recurrence : 재귀적으로 정의되는 수학적 함수

 

문제 풀이

1. 중복되는 부분 문제, 최적 부분 문제가 있는지 확인. => 동적 계획법 적용
2. 기저 사례 설정 : n <= 1 인경우, return n
3. 부분 문제 설정 : $F_{n} = F_{n-1} + F_{n-2}$
4. 구현 방식 설정
   1. Top-down(메모이제이션 적용) : 재귀 함수 사용. O(n)의 공간 복잡도
   2. Bottom-up(슬라이딩 윈도우 적용) : 반복 구문 사용. O(1)의 공간 복잡도

 

Case 1. Top-down 형식으로 구현 (메모이제이션 적용)

// Top-down
int memo[100]; // 메모이제이션 

int fibonacci(int n)
{
    if (n <= 1)
        return n;

    if (0 < memo[n])
        return memo[n];

    memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
    return memo[n];
}

 

Case 2. Bottom-up 형식으로 구현 (슬라이딩 윈도우 기법 적용)

int fibonacci(int n)
{
    if (n <= 1)
        return n;

    // Bottom-up
    int seq[3]; // 슬라이딩 윈도우 기법 : O(1)의 공간 복잡도

    seq[0] = 0;
    seq[1] = 1;

    for (int i = 2; i <= n; ++i)
    {
        seq[i % 3] = seq[(i - 1) % 3] + seq[(i - 2) % 3];
    }

    return seq[n % 3];
}

 

References

https://doorbw.tistory.com/53