[알고리즘] 08. 동적 계획법(Dynamic Programming)

동적 계획법(DP, Dynamic Programming)이란?

큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘 기법이다.

💡 퀵 정렬 (분할 정복)과 차이는?
다이나믹 프로그래밍은 문제들이 서로 영향을 미치고 있음
즉, 한 번 해결했던 문제를 다시금 해결한다는 점이 특징임

다이나믹 프로그래밍으로 해결할 수 있는 대표적인 예시로는 피보나치 수열이 있다.
프로그래밍에서 수학적 점화식을 표현하려면 재귀 함수를 사용하면 된다.
f(n) = f(n-1) + f(n-2)
하지만 n이 커지면 수행 시간이 기하급수적으로 늘어날 수 있다

public class Main {

    public static int fibo(int x) {
        if (x == 1 || x == 2) {
            return 1;
        }
        return fibo(x - 1) + fibo(x - 2);
    }

    public static void main(String[] args) {
        System.out.println(fibo(4));
    }

}

 

그림을 보면 동일한 함수가 반복적으로 호출되는 것을 알 수 있다.즉, f(n)에서 n이 커지며 커질수록 반복해서 호출하는 수가 많아진다.이처럼 피보나치 수열의 점화식을 재귀 함수를 사용해 만들 수 있지만 비효율적일 수 있음

다음 두 성질이 있는 문제에 대해 적절한 저장방법으로 중복 호출의 비효율을 제거한 것은 다이나믹 프로그래밍이라고 한다.

• 최적 부분 구조를 이룬다. (문제의 해답을 구하기 위해 더 작은 문제의 해답을 이용하는 것)
• 재귀적으로 구현했을 때 중복 호출로 심각한 비효율이 발생한다.

 

다이나믹 프로그래밍(DP) 사용 조건

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

 

메모이제이션 기법

다이나믹 프로그래밍을 구현하는 방법 중 한 종류로 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다.
메모제이션은 값을 저장하는 방법이므로 캐싱(Cashing)이라고도 한다.

• 메모이제이션을 이용하는 경우 피보나치 수열 함수의 시간 복잡도는 O(N) 이다

- 탑다운 방식(재귀함수) : 큰 문제를 해결하기 위해 작은 문제를 호출

import java.util.*;

public class Main {

    // 한 번 계산된 결과를 메모이제이션(Memoization)하기 위한 배열 초기화
    public static long[] d = new long[100];

    // 피보나치 함수(Fibonacci Function)를 재귀함수로 구현 (탑다운 다이나믹 프로그래밍)
    public static long fibo(int x) {
        // 종료 조건(1 혹은 2일 때 1을 반환)
        if (x == 1 || x == 2) {
            return 1;
        }
        // 이미 계산한 적 있는 문제라면 그대로 반환
        if (d[x] != 0) {
            return d[x];
        }
        // 아직 계산하지 않은 문제라면 점화식에 따라서 피보나치 결과 반환
        d[x] = fibo(x - 1) + fibo(x - 2);
        return d[x];
    }

    public static void main(String[] args) {
        System.out.println(fibo(50));
    }
}

- 보텀업 방식(반복문) : 작은 문제부터 차근차근 답을 도출

import java.util.*;

public class Main {

    public static long[] d = new long[100];

    public static void main(String[] args) {
        // 첫 번째 피보나치 수와 두 번째 피보나치 수는 1
        d[1] = 1;
        d[2] = 1;
        int n = 50; // 50번째 피보나치 수를 계산

        // 피보나치 함수(Fibonacci Function) 반복문으로 구현(보텀업 다이나믹 프로그래밍)
        for (int i = 3; i <= n; i++) {
            d[i] = d[i - 1] + d[i - 2];
        }
        System.out.println(d[n]);
    }
}

 

다이나믹 프로그래밍 예)

행렬 경로 문제

n x n 행렬이 주어졌을 때, 행렬의 왼쪽 위에서 시작해 한 칸씩 이동해 오른쪽 아래까지 도달한다. (오른쪽이나 아래쪽으로만 이동 가능)

이 과정에서 방문한 칸에 있는 수들을 더한 값이 이 경로의 합일 때, (1, 1)에서 (n, n)으로 이동하는 모든 경로의 점수 중 가장 높은 점수를 구하시오.

 

1. 최적 부분 구조의 존재를 확인해보자.

원소 (i, j)에 도달하기 직전에 방문할 수 있는 원소는 (i-1, j)와 (i, j-1) 단 두 개로 (i-1, j)까지 도달하는 최고 점수와 (i, j-1)까지 도달하는 최고 점수 중 큰 것에 원소 (i, j)의 점수를 더하면 원소 (i, j)까지 도달하는 최고 점수가 된다.

다르게 말하면 (i, j)의 최적해는 (i-1, j)의 최적해와 (i, j-1)의 최적해로 설명된다. 즉, 자신의 부분 문제에 대한 최적해를 자신의 최적해를 구성하는 데 사용한다.

 

2. 최적 부분 구조를 재귀적 관계로 나타내보자.

• i=0이거나 j=0이면 이 행렬에는 존재하지 않는 자리에 이르는 최고 점수이므로 값 0을 갖는다.
• 이 경우가 아니면 원소 (i, j)의 바로 왼쪽 원소에 이르는 최고 점수와 위쪽 원소에 이르는 최고 점수 중 큰 것에 원소 (i, j)의 값을 더한 것이 원소 (i, j)의 최고 점수이다.

코딩 테스트에서 다이나믹 프로그래밍 문제는 대체로 간단한 형태로 출제된다.
근데 주어진 문제가 다이나믹 프로그래밍 유형임을 어떻게 파악할 수 있는지..? 🤔
> 특정한 문제를 완전 탐색 알고리즘으로 접근했을 때 시간이 매우 오래 걸리면 DP를 적용할 수 있는지 중복 여부 체크해보자
가능하다면 재귀 함수를 이용하는 탑다운 방식보다는 보텀업 방식을 권장함
(시스템상 재귀 함수의 스택 크기가 한정되어 있을 수 있기 때문)