[Algorhtim] 동적 계획법(Dymanic Programmning)

1. 동적 계획법이란?

동적 계획법

 

동적 계획법(Dynamic Programming)은 주어진 문제를 작은 부분 문제로 분할하고, 그 결과를 저장하여 중복 계산을 방지하는 알고리즘 기법이다. 특히 부분 문제의 수가 기하급수적으로 증가할 때 유용하다. 분할 정복법과는 달리, 중복되는 부분 문제의 결과를 재활용하여 속도를 높인다.

• 각 부분 문제가 서로 독립적일 때: 분할 정복법 사용.
• 부분 문제가 중복될 때: 동적 계획법 사용.

2. 메모이제이션이란?

메모이제이션(Memoization)은 계산 결과를 저장해두고, 동일한 계산이 다시 필요할 때 저장된 값을 사용하는 최적화 기법이다. 이를 통해 중복 계산을 방지하고 속도를 향상시킬 수 있다. 메모리를 사용해 계산 시간을 줄이는 방식이다.

3 - 1. 메모이제이션의 활용: 이항 계수 계산

1) 메모이제이션을 사용하지 않았을 때의 문제점

이항 계수 계산은 재귀적으로 계산될 수 있다. 하지만 이 경우, 같은 부분 문제를 반복해서 계산하게 되어 시간이 많이 걸린다. 예를 들어, 아래 코드에서 bino(n, r)는 bino(n-1, r-1)과 bino(n-1, r)를 계산하기 위해 다시 재귀 호출을 수행하고, 이렇게 호출된 함수들이 다시 중복된 계산을 계속 반복하게 된다.

재귀 호출을 통한 이항 계수 계산 (메모이제이션 사용 전)

int bino(int n, int r) {

    if (r == 0 || n == r) return 1; // 기저 사례: 끝에 도달한 경우

    return bino(n - 1, r - 1) + bino(n - 1, r); // 두 가지 경로로 분할하여 계산

}

문제점
- 중복된 계산이 많이 발생한다. 예를 들어, bino(n-1, r-1)과 bino(n-1, r)는 이미 계산된 값을 다시 계산하게 된다.
- 결과적으로 재귀 호출의 깊이가 깊어질수록 계산 시간이 기하급수적으로 증가하며, O(2^n)의 시간 복잡도를 가진다.

2) 메모이제이션을 사용하여 최적화

메모이제이션을 적용하면, 이전에 계산된 결과를 저장하고 재사용하기 때문에 중복된 계산을 방지할 수 있다. 이를 통해 시간 복잡도를 O(n*r)로 줄일 수 있다.

메모이제이션을 적용한 이항 계수 계산

int cache[30][30]; // -1로 초기화

int bino2(int n, int r) {

    if (r == 0 || n == r) return 1; // 기저 사례

    if (cache[n][r] != -1) return cache[n][r]; // 이미 계산된 값이 있다면 그 값을 반환

    return cache[n][r] = bino2(n - 1, r - 1) + bino2(n - 1, r); // 새로 계산된 값을 캐시에 저장

}

개선점
- 중복 계산을 하지 않으므로, 시간 복잡도가 크게 줄어든다.
- 한 번 계산된 값은 캐시에 저장되므로, 같은 값이 필요할 때 즉시 반환 가능하다.

---

3 - 2. 달팽이 문제: 메모이제이션을 통한 경로 계산

1) 문제 설명

달팽이 문제는 climb 함수가 특정한 날에 특정한 높이만큼 올라갔을 때, 목표 높이 n 이상에 도달할 수 있는 경우의 수를 구하는 문제이다. 달팽이는 하루에 1칸 또는 2칸씩 올라갈 수 있다.

2) 메모이제이션을 사용하지 않았을 때의 문제점

int climb(int days, int climbed) {

    if (days == m) return climbed >= n ? 1 : 0; // 목표 높이 도달 여부 확인

    return climb(days + 1, climbed + 1) + climb(days + 1, climbed + 2); // 재귀적으로 다음 경로 탐색

}

문제점
- 중복 계산 발생. 예를 들어, climb(days + 1, climbed + 1)과 climb(days + 1, climbed + 2)는 여러 경로에서 중복되어 호출된다.
- 결과적으로 O(2^m)의 시간 복잡도를 가진다.

2) 메모이제이션을 사용하여 최적화

int cache[MAX_N][2 * MAX_N + 1]; // -1로 초기화된 캐시 배열

int climb(int days, int climbed) {

    if (days == m) return climbed >= n ? 1 : 0; // 기저 사례: 목표 높이 도달 여부 확인

    int& ret = cache[days][climbed]; // 캐시 값 참조

    if (ret != -1) return ret; // 이미 계산된 값이 있다면 그 값을 반환

    return ret = climb(days + 1, climbed + 1) + climb(days + 1, climbed + 2); // 캐시에 값 저장

}

개선점
- 중복 계산을 방지하고, 경로 탐색 속도를 크게 향상시킨다.
- 메모이제이션 덕분에 각 경우의 수를 한 번만 계산하므로 O(m*n)의 시간 복잡도를 갖는다.

4. 최적 부분 구조란?

최적 부분 구조란 문제의 최적해가 그 하위 문제들의 최적해로부터 구해질 수 있는 구조를 말한다. 동적 계획법이 적용되기 위해서는 문제를 하위 문제로 나누고, 그 하위 문제의 최적해를 이용해 전체 문제의 최적해를 얻는 것이 가능해야 한다.

1) 최적 부분 구조를 사용하지 않은 예시

최단 경로 문제에서, 시작점에서 끝점까지의 최단 경로를 구하는 함수를 생각해보자. 이 함수는 경유할 중간 지점들을 일일이 비교하지 않고, 모든 가능한 경로를 하나하나 탐색하는 방식으로 구현되어 있다. 이 경우, 중복된 경로를 여러 번 탐색하게 된다.

최적 구조를 사용하지 않은 코드 (모든 경로 탐색)

const int INF = 1e9;  // 매우 큰 값 (무한대)

int dist[MAX_N][MAX_N];  // 도시 간의 거리

bool visited[MAX_N];     // 방문 여부

int findShortestPath(int start, int end) {

    if (start == end) return 0;  // 시작점과 끝점이 같으면 경로 길이는 0

    int ret = INF;  // 최단 경로를 저장할 변수, 처음엔 무한대로 설정

    visited[start] = true;  // 현재 도시 방문 처리

    for (int i = 0; i < N; ++i) {

        if (!visited[i] && dist[start][i] != INF) {  // 방문하지 않은 도시와 연결된 도시만 탐색

            ret = min(ret, dist[start][i] + findShortestPath(i, end));  // 모든 경로 중 최단 경로 찾기

        }

    }

    visited[start] = false;  // 방문 상태 초기화

    return ret;

}

문제점
- 중복된 경로를 계속 탐색하게 된다. 예를 들어, findShortestPath(A, B)가 A에서 B까지의 경로를 구할 때, A -> C -> B라는 경로가 여러 경로에서 중복될 수 있다.
- 모든 가능한 경로를 탐색하므로, 비효율적이며 시간이 많이 소요된다. 시간 복잡도는 O(N!)에 가까워질 수 있다.

2) 최적 구조를 사용하여 개선한 코드 (메모이제이션 적용)

최적 부분 구조를 적용하면, 이미 계산한 하위 문제(경유지 간의 최단 경로)를 저장하고 재사용할 수 있다. 이렇게 하면 같은 경로를 여러 번 탐색하지 않으므로 성능이 크게 향상된다.

최적 구조를 적용한 코드 (메모이제이션 사용)

const int INF = 1e9;  // 매우 큰 값 (무한대)

int dist[MAX_N][MAX_N];  // 도시 간의 거리

int cache[MAX_N][MAX_N];  // 최단 경로 캐시 배열

int findShortestPathMemo(int start, int end) {

    if (start == end) return 0;  // 시작점과 끝점이 같으면 경로 길이는 0

    if (cache[start][end] != -1) return cache[start][end];  // 이미 계산된 값이 있다면 캐시에서 반환

    int ret = INF;  // 최단 경로를 저장할 변수, 처음엔 무한대로 설정

    for (int i = 0; i < N; ++i) {

        if (dist[start][i] != INF) {  // 연결된 도시만 탐색

            ret = min(ret, dist[start][i] + findShortestPathMemo(i, end));  // 최단 경로 계산

        }

    }

    return cache[start][end] = ret;  // 계산한 최단 경로를 캐시에 저장

}

개선점
- 중복 계산을 방지함으로써 성능이 크게 향상된다.
- 시간 복잡도가 개선되며, 캐시를 사용해 탐색 시간을 O(N^2)로 줄일 수 있다.
- 모든 경로를 처음부터 다시 탐색하는 비효율성을 제거하고, 각 경로를 한 번만 계산하게 된다.

---

마무리하며

동적 계획법은 복잡한 문제를 해결할 때 매우 중요한 알고리즘 기법이다. 이 기법은 문제를 작은 부분 문제로 나누고, 중복된 계산을 방지하기 위해 메모이제이션을 사용하는 방식으로 시간 복잡도를 획기적으로 줄인다. 특히, 최적 부분 구조가 성립하는 문제에서는 동적 계획법이 효율적으로 적용될 수 있으며, 하위 문제의 결과를 재사용하는 방식으로 문제를 빠르게 해결할 수 있다.

다양한 최적화 문제에서 동적 계획법은 필수적인 도구로 사용되며, 이를 활용하여 복잡한 문제를 효율적으로 풀어낼 수 있다. 메모이제이션을 통해 중복된 계산을 방지하고, 성능을 크게 개선할 수 있다는 점에서 동적 계획법은 매우 중요한 알고리즘 전략 중 하나다.

참고 자료

• 구종만, 프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략
• 나무위키: 메모이제이션
• SSMinji의 블로그: The Cake Thief