DP(Dynamic Programming)

DP(Dynamic Programming, 동적 계획법)는 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법이다.

단순히 나누어 푸는 것에 그치지 않고, 한번 계산한 결과를 저장해 두었다가 재활용하는 것이 핵심이다.

DP 테이블 정의와 관계 찾기가 가장 중요!

핵심 원리

• 중복되는 부분 문제: 똑같은 계산이 반복될 때 이를 매번 다시 하지 않는다.
• 최적 부분 구조: 큰 문제의 답이 작은 문제의 답을 포함하고 있는 구조여야 한다.

핵심 방식 - 메모이제이션(Memoization)

이미 계산한 결과값을 배열이나 테이블에 저장해 두는 것을 말한다.

다음에 같은 계산이 필요할 때 저장된 값을 꺼내 쓰기만 하면 되므로 시간 복잡도를 획기적으로 줄일 수 있다.

구현 방식

1. Top-Down(하향식): 큰 문제를 해결하기 위해 작은 문제를 호출(재귀). 메모이제이션 기법 활용, 가독성이 좋으나 스택 오버플로우 주의.

2. Bottom-Up(상향식): 작은 문제부터 차근차근 답을 쌓아 올림(반복문). DP 테이블 활용, 일반적으로 더 권장되는 방식.

문제

백준 2579번 계단오르기

풀이

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        // 계단 점수를 저장할 배열 (1번 인덱스부터 사용)
        int[] s = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            s[i] = sc.nextInt();
        }

        // n이 1인 경우 예외 처리 (dp[2] 등에 접근하면 에러 발생 가능)
        if (n == 1) {
            System.out.println(s[1]);
            return;
        }

        // dp[i][0]: i번째 계단에 '1칸 점프'로 도착 (연속 2칸째 밟음)
        // dp[i][1]: i번째 계단에 '2칸 점프'로 도착 (현재 새로운 연속 시작)
        int[][] dp = new int[n + 1][2];

        // 1. 초기값 설정 (Base Case)
        dp[1][0] = s[1];
        dp[1][1] = s[1];

        // 2. DP 테이블 채우기 (Bottom-Up)
        for (int i = 2; i <= n; i++) {
            // 현재 계단에 1칸으로 온 경우
        	// i-1의 계단이 2칸으로 왔어야 연속 3칸이 안됨
            dp[i][0] = dp[i - 1][1] + s[i];

            // 현재 계단에 2칸으로 온 경우
            // i-1의 계단이 1칸으로 왔던 2칸으로 왔던 상관없으니(다시 연속 1칸부터 시작) 더 큰 값 저장
            dp[i][1] = Math.max(dp[i - 2][0], dp[i - 2][1]) + s[i];
        }

        // 3. 최종 결과 출력
        // 마지막 계단은 반드시 밟아야 하므로, 마지막 칸의 두 상태 중 최댓값 출력
        System.out.println(Math.max(dp[n][0], dp[n][1]));
    }
}