DP 알고리즘이란?

DP(Dynamic Programming, 동적 계획법)는 큰 문제를 작은 부분 문제로 나누고, 그 부분 문제들의 정답을 미리 저장해두었다가 재사용하여 전체 문제를 효율적으로 푸는 알고리즘 기법이다.

DP의 가장 큰 장점은 같은 계산을 여러 번 반복하는 상황에서 중복 계산을 제거해 시간 복잡도를 크게 줄일 수 있다는 점이다.

예를 들면 어떤 문제에서 i번째 상태의 정답을 구하기 위해 i-1번째 상태의 정답이 필요하다면, 매번마다 처음부터 다시 계산하지 않고 이전 결과를 저장해두고 가져다 쓰는 방식으로 시간복잡돌를 줄일 수 있다.

DP와 분할 정복의 비교

DP의 접근 방식은 기본적으로 분할 정복(Divide and Conquer) 알고리즘과 매우 유사하다.

두 기법 모두 하나의 큰 문제를 여러 개의 작은 부분 문제로 나누고, 각 부분 문제의 해를 이용해 원래 문제의 해를 구한다는 공통점을 가지지만 차이점 또한 존재한다.

분할정복 알고리즘은 문제를 서로 겹치지 않는 독립적인 부분 문제로 나누고 각 부분 문제를 재귀적으로 해결하고 그 결과를 합쳐 전체 문제를 해결한다.
이 경우 각 부분 문제는 한 번만 계산되며, 같은 부분 문제가 반복해서 등장하지 않는다.

하지만 DP는 문제를 나눌 때 부분 문제가 서로 겹치도록 나누는 것이 특징이다.
분할 정복과 다르게 같은 부분 문제가 여러 번 등장할 수 있다는게 큰 차이점이다.

따라서 DP는 중복 계산을 피하기 위해 부분 문제 정답을 한번만 계산하기 위해서 이전에 계산한 결과들을 배열에 보통 저장을 해서 저장된 값을 사용해 시간 복잡도를 줄이는 것이다.

DP의 기본 아이디어

DP는 보통 3단계로 정의가 된다.

1. 상태 정의(State)

dp[i] 또는 dp[i][j]처럼 i번째까지 고려했을 때의 최적값 같은 의미를 부여

2. 점화식(Transition) 도출

현재 상태가 이전 상태들로부터 어떻게 만들어지는지 규칙을 세움

3. 초기값(Base Case) 설정

dp가 시작되는 최초 상태를 직접 채움

DP의 구현 방식

DP는 크게 두 가지 방식으로 구현이 된다.

• Top-Down(재귀 + 메모이제이션): 필요할 때 계산하고 저장

• Bottom-Up(반복문): 작은 것부터 차례대로 채우기

DP 알고리즘의 적용 예시

https://www.acmicpc.net/problem/1149

public class boj_1149_S1 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());

        int[][] payment = new int[N][3];

        st = new StringTokenizer(br.readLine());

        payment[0][0] = Integer.parseInt(st.nextToken());
        payment[0][1] = Integer.parseInt(st.nextToken());
        payment[0][2] = Integer.parseInt(st.nextToken());

        for (int i = 1; i < N; i++) {
            st = new StringTokenizer(br.readLine());

            payment[i][0] = Integer.parseInt(st.nextToken()) + Math.min(payment[i-1][1], payment[i-1][2]);
            payment[i][1] = Integer.parseInt(st.nextToken()) + Math.min(payment[i-1][0], payment[i-1][2]);
            payment[i][2] = Integer.parseInt(st.nextToken()) + Math.min(payment[i-1][1], payment[i-1][0]);
        }

        System.out.println(Math.min(Math.min(payment[N-1][0], payment[N-1][1]), payment[N-1][2]));

        br.close();
    }
}

문제풀이

이 문제의 핵심은 현재 집 색 선택이 이전 집의 색 선택에 영향을 받는 다는 것이다.

앞에서 말한 DP 풀이 순서에 따라 정리해보면

1. DP 상태 정의

• payment[i][0] : i번째 집을 빨강으로 칠했을 때, 0~i까지 최소 비용

• payment[i][1] : i번째 집을 초록으로 칠했을 때, 0~i까지 최소 비용

• payment[i][2] : i번째 집을 파랑으로 칠했을 때, 0~i까지 최소 비용

2. 점화식

i번째 집을 특정 색으로 칠하려면 i-1번째 집은 다른 색이어야 한다.

• payment[i][0] = cost(i,R) + min(payment[i-1][1], payment[i-1][2])

• payment[i][1] = cost(i,G) + min(payment[i-1][0], payment[i-1][2])

• payment[i][2] = cost(i,B) + min(payment[i-1][0], payment[i-1][1])

3. 초기값

• payment[0][0] = cost(0,R)

• payment[0][1] = cost(0,G)

• payment[0][2] = cost(0,B)

cf) 이 문제를 그냥 탐색으로 푼다면 O(3^N)으로 시간초과가 발생하기에 DP를 적용해 O(N)으로 줄일 수 있게 된다.