DP 개념 — 테이블, 점화식, 초기값부터 생각하기

개요

다이나믹 프로그래밍 (Dynamic Programming, DP)

여러 개의 하위 문제를 먼저 푼 후, 그 결과를 쌓아 올려 주어진 문제를 해결하는 알고리즘

쉽게 말하면, 문제를 해결하기 위한 점화식을 찾고, 점화식의 항을 밑에서부터 차례대로 구해나가서 답을 알아내는 형태의 알고리즘이다.

예시 ) 피보나치

• 재귀 피보나치는 fibo(n)을 여러 번 중복 연산했다. 그 이유는 fibo(3)이 3임을 계산은 했지만 저장해두지 않았기 때문이다.

• DP에서는 계산 결과를 배열에 저장해두는 방식을 사용한다.
• 0번째 인덱스부터 하나씩 채워가며 인덱스 N까지 총 N+1개의 값을 채워 답에 도달한다.
  • 즉 O(N)에 답을 알 수 있다.
  • 중간 결과를 저장해서 이용하는 방식이다.

1) DP 구현 방법

코테 난이도의 DP 문제는 일단 점화식만 찾고 나면 그 뒤는 초기 값을 채워 넣은 후에 반복문을 돌며 배열을 채우면 끝이어서 구현이 쉽다.

1. 테이블 정의하기

D[i]가 무엇을 뜻하는지 한 문장으로 적는다. 예를 들어 피보나치라면 i번째 값을 저장한다. 이후 선택에 영향을 주는 조건이 더 있다면 상태도 함께 저장해야 한다.

2. 점화식 찾기

현재 상태를 어떤 이전 상태에서 만들 수 있는지 찾는다. 최솟값을 구하는 문제인지, 경우의 수를 세는 문제인지에 따라 비교하거나 더하는 방식이 달라진다.

3. 초기값 정의하기

점화식만으로 계산할 수 없는 가장 작은 상태를 직접 채운다. 그다음 필요한 이전 값이 준비되는 순서대로 테이블을 채운다.

피보나치에서 확인하기

위 강의 그림은 F(0) = F(1) = 1로 시작하는 정의를 사용한다. 따라서 F(3) = 3이다. F(0) = 0, F(1) = 1로 시작하는 정의와 초기값을 섞지 않도록 주의한다.

function fibonacci(n) {
    const D = Array(n + 1).fill(0);
    D[0] = 1;
    if (n >= 1) D[1] = 1;
    for (let i = 2; i <= n; i++) {
        D[i] = D[i - 1] + D[i - 2];
    }
    return D[n];
}

이 코드는 작은 n에서 계산 흐름을 확인하기 위한 예제다. 아주 큰 정수에는 JavaScript Number의 정밀도 한계도 고려해야 한다.

시간 복잡도는 O(N), 테이블의 공간 복잡도는 **O(N)**이다. 재귀를 쓰면서 계산 결과를 저장하는 메모이제이션도 가능하지만, 여기서는 작은 상태부터 반복문으로 채우는 방식을 다룬다.

핵심은 배열을 쓰는 것 자체보다, 어떤 중간 결과를 저장하고 다시 사용할지 정하는 것이다.

참고 자료

바킹독의 실전 알고리즘 0x10강 — 다이나믹 프로그래밍을 학습하며 작성한 메모를 바탕으로 정리했다. 포함된 이미지는 원본 학습 메모의 캡처다.