[코딩테스트] 6. 초기값과 탐색 순서

상태 정의와 점화식을 세웠으면 두 가지가 남았다. 초기값과 탐색 순서다. 이 두 가지를 빠뜨리면 점화식이 맞아도 틀린 답이 나온다.

초기값 (Base Case)

점화식은 이전 상태를 참조해서 현재 상태를 계산한다. 그런데 "이전 상태"가 없는 가장 작은 경우는 어떻게 할까. 이것을 직접 값으로 채워주는 게 초기값이다.

피보나치에서 dp[1] = 1, dp[2] = 1이 초기값이었다. 이걸 정해주지 않으면 dp[3] = dp[2] + dp[1]을 계산할 수 없다.

동전 교환 문제에서:

• dp[0] = 0 : 0원을 만드는 데 동전 0개 필요
• dp[i] = INF (i > 0) : 아직 계산 전, 만들 수 없음을 표시

초기값 타입별 정리

• 최솟값을 구하는 문제 → INF로 초기화 (Integer.MAX_VALUE 또는 큰 숫자)
• 최댓값을 구하는 문제 → -INF로 초기화 (Integer.MIN_VALUE 또는 0)
• 경우의 수를 구하는 문제 → 0으로 초기화 후 base case에서 1 설정

탐색 순서

Bottom-up DP는 반복문으로 dp 배열을 채운다. 채우는 순서가 중요한데, 규칙은 하나다. dp[i]를 계산할 때 참조하는 값이 이미 채워져 있어야 한다.

점화식에서 의존 방향을 파악하면 순서를 결정할 수 있다.

• 동전 문제 : dp[i]는 dp[i-c]에 의존. i-c < i이므로 → 오름차순
• 배낭 1D 최적화 : dp[j]는 dp[j-w]에 의존하되 같은 물건 중복 금지 → 역순(내림차순)

2D DP의 탐색 순서

2차원 배열에서 dp[i][j]가 dp[i-1][j]와 dp[i][j-1]에 의존한다면, i와 j 모두 오름차순으로 채우면 된다.

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
        dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + grid[i][j];
    }
}

i행을 처리할 때 i-1행은 이미 완성된 상태. 같은 행에서 j를 채울 때 j-1은 이미 채워진 상태.

다음 시리즈에서는 이 설계 방법을 실전 유형에 적용해보자.

→ 다음 시리즈 : DP 유형별 패턴

---