동적 계획법(DP) 알고리즘에 대해 공부 후 정리하였습니다.

동적 계획법(DP: Dynamic Programming)

1️⃣ DP란?

큰 문제를 작은 문제로 나누고, 중복되는 작은 문제를 한 번만 풀어서
그 결과를 저장해두고 재사용하여 전체 문제를 해결하는 기법입니다.

2️⃣ DP의 핵심 조건 (2가지)

중복 부분 문제 (Overlapping Subproblems) : 같은 계산을 여러 번 반복하는 문제
최적 부분 구조 (Optimal Substructure) : 큰 문제의 최적해가 작은 문제의 최적해로 구성됨

3️⃣ DP의 시간 복잡도

DP의 시간 복잡도는 일반적으로 O(상태 개수 × 상태 전이 계산 시간) 으로 계산됩니다.

피보나치 (Top-down / Bottom-up): 상태 개수 = n, 전이 시간 = O(1) → O(n)
LCS (Longest Common Subsequence): 상태 개수 = n × m, 전이 시간 = O(1) → O(nm)
배낭 문제: 상태 개수 = n × W, 전이 시간 = O(1) → O(nW)

✅ DP 시간 복잡도 계산 팁

배열 크기 = 상태 개수
한 상태에서 다음 상태로 가는 경우의 수 = 전이 계산 시간
곱하면 총 시간 복잡도

4️⃣ DP 유형 분류

시간 복잡도는 동일함

유형	설명	실제 실행 시간	효과적인 예시	예시
Top-Down	재귀 + 메모이제이션	느림	테이블의 일부만 채워야 할 때, 테이블을 채우는 순서가 복잡할 때	`f(n) = f(n-1) + f(n-2)`
Bottom-Up	반복문 + 배열	빠름	테이블을 채우는 순서가 직관적으로 보일 때	`dp[i] = dp[i-1] + dp[i-2]`

5️⃣ DP 문제 풀이 팁

테이블 정하기 (ex: dp[i] = i를 1로 만드는 최소 연산 횟수)
점화식 구하기 (ex: dp[i] = dp[i-1] + dp[i-2])
초기값 정하기 (ex: dp[0], dp[1])
메모이제이션 or 반복문 선택
- 재귀(Top-down): 간단한 구조, but 느릴 수 있음
- 반복문(Bottom-up): 빠르고 안전, but 구현이 복잡할 수 있음
작은 입력부터 차례로 채우기 (ex: dp[2], dp[3], …, dp[n] 순서로)

Prefix Sum (누적 합)

1️⃣ 개념

배열의 부분합을 빠르게 구하기 위해, 미리 합을 구해놓은 배열을 만드는 기법
구간 합 쿼리를 O(1)에 처리 가능

2️⃣ 특징

배열 변경이 없는 경우 매우 효율적 (변경이 있으면 Fenwick Tree, Segment Tree 고려)
1D, 2D, 3D 등 다차원 배열에도 적용 가능

3️⃣ 시간 복잡도

전처리: O(n)
구간합 질의: O(1)

4️⃣ 구현 방법

prefix[i] = arr[0] ~ arr[i] 합
구간합 (l, r) = prefix[r] - prefix[l-1]

5️⃣ 예시 코드 (1D)

  
public class PrefixSumExample {
    public static void main(String[] args) {
        int[] arr = {2, 4, 5, 7, 1};
        int n = arr.length;
        int[] prefix = new int[n + 1]; // 1-based indexing

        // 전처리
        for (int i = 1; i <= n; i++) {
            prefix[i] = prefix[i - 1] + arr[i - 1];
        }

        // 구간합 예시: arr[1..3] (0-indexed: 4+5+7)
        int l = 2, r = 4; // 1-based index
        int sum = prefix[r] - prefix[l - 1];
        System.out.println("구간합: " + sum); // 출력: 13
    }
}

[알고리즘] 동적 계획법(DP: Dynamic Programming)