1차원/2차원 DP 대표 문제군과 차원 선택

DP에서 가장 어려운 첫 선택은 상태 차원을 몇 개로 잡을지 결정하는 일입니다. 상태를 너무 크게 잡으면 메모리와 코드가 무거워지고, 너무 작게 잡으면 정보가 부족해 오답이 납니다. 그래서 차원 선택은 취향이 아니라 정확도와 성능을 함께 결정하는 설계 문제입니다.

아래에서는 1차원/2차원 DP를 대표 문제로 나눠 비교합니다. 문제를 읽을 때 어떤 정보를 독립 상태로 기억해야 하는지 우선 정리하는 습관을 강조합니다. 차원 적용 관점을 바로 적용할 수 있도록 단계별로 설명합니다.

1차원/2차원 DP 차원 선택 개념도

핵심 원리 청사진

차원 선택은 DP 구현의 난도를 결정하는 핵심 설계입니다. 문제를 읽고 정답을 결정하려면 독립 정보가 몇 개인지 우선 세어 보세요.

상태 차원은 정답 계산에 필요한 독립 변수 개수입니다. DP 인덱스 튜플 길이가 곧 상태 차원이 되고, 이 차원이 메모리/시간 비용을 크게 좌우합니다. LIS는 위치 인덱스 하나로 충분해서 1차원 DP로 해결할 수 있습니다.

1차원 DP는 한 축 상태를 따라 값을 갱신하는 구조입니다. 단일 인덱스 상태에서 선형 또는 이중 루프 전이로 최적해를 갱신할 때 사용합니다. 동전 조합 수 문제에서 dp[sum] 하나만으로 목표 금액까지 누적하는 방식이 대표적입니다.

2차원 DP는 두 축 정보를 동시에 기억해야 할 때 선택합니다. (i,j)처럼 두 독립 변수를 인덱스로 두고 위/왼쪽/대각선 등 다중 방향 전이를 처리합니다. LCS는 문자열 A 위치와 B 위치 두 정보가 모두 필요하므로 dp[i][j] 모델이 자연스럽습니다.

차원 선택이 운영 성능에 미치는 영향

차원을 과하게 잡으면 메모리와 구현 복잡도가 급증합니다. 반대로 차원을 과소평가하면 전이가 누락되어 오답이 나옵니다. 예를 들어 LIS를 2차원으로 잡으면 불필요하게 복잡해지고, LCS를 1차원으로 바로 압축하려 하면 초기 구현이 흔들리기 쉽습니다.

정확한 차원 선택은 성능뿐 아니라 디버깅 비용을 크게 줄입니다.

차원 전개 디버깅 시나리오

여기서는 오답 -> 디버깅 -> 교정 -> 검증 흐름으로 추적해, 어디서 불변식이 깨지는지 단계별로 확인합니다.

2차원 DP 표를 작은 문자열로 직접 채워 봅니다.

문자열 A: "ab"
문자열 B: "ac"
목표: LCS 길이

dp[i][j]를 A[0..i), B[0..j)의 LCS 길이로 정의합니다.
문자가 같으면 dp[i-1][j-1]+1, 다르면 max(dp[i-1][j], dp[i][j-1])를 사용합니다.
표를 채우면 최종값 dp[n][m]이 답이 됩니다.
초기 행/열(0행, 0열) 설정이 누락되면 전이가 전부 오염됩니다.

차원 확장 상태 설계 적용 관점

차원 선택 전 아래 질문을 확인합니다.

현재 최적값이 단일 인덱스에만 의존하는가?
두 개의 진행 포인터를 동시에 기억해야 하는가?
상태 전이에서 위/왼쪽/대각선처럼 다중 방향 참조가 필요한가?
경로 복원이 필요한가?

필요 정보보다 많은 축을 잡지 않는 것이 기본 원칙입니다.

DP 차원: 1차원 DP(LIS `O(N^2)`)

문제 의도: LIS를 1차원 상태로 모델링해 기본 DP 전이를 학습합니다.
입력 예시: nums=[10,9,2,5,3,7,101,18]
출력 예시: 4

main.cpp

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int lisLength(const vector<int>& nums) {
    int n = (int)nums.size();
    if (n == 0) return 0;
    vector<int> dp(n, 1);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (nums[j] < nums[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    return *max_element(dp.begin(), dp.end());
}

int main() {
    vector<int> arr = {10, 9, 2, 5, 3, 7, 101, 18};
    cout << lisLength(arr) << "\n";
    return 0;
}

Main.java

import java.util.Arrays;

public class Main {
    static int lisLength(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        int ans = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            ans = Math.max(ans, dp[i]);
        }
        return ans;
    }

    public static void main(String[] args) {
        int[] arr = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println(lisLength(arr));
    }
}

main.py

def lis_length(nums):
    n = len(nums)
    if n == 0:
        return 0

    # dp[i]: i에서 끝나는 LIS 길이
    dp = [1] * n

    for i in range(n):
        for j in range(i):
            if nums[j] < nums[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)

arr = [10, 9, 2, 5, 3, 7, 101, 18]
print(lis_length(arr))
# 출력: 4

main.rs

fn lis_length(nums: &[i32]) -> i32 {
    let n = nums.len();
    if n == 0 {
        return 0;
    }
    let mut dp = vec![1_i32; n];
    let mut ans = 1_i32;
    for i in 0..n {
        for j in 0..i {
            if nums[j] < nums[i] {
                dp[i] = dp[i].max(dp[j] + 1);
            }
        }
        ans = ans.max(dp[i]);
    }
    ans
}

fn main() {
    let arr = [10, 9, 2, 5, 3, 7, 101, 18];
    println!("{}", lis_length(&arr));
}

증가 부분수열 상태 상태 정의 조건 체크

LIS는 마지막 원소 위치 하나만 알면 상태를 정의할 수 있어 1차원으로 충분합니다. 전이는 이전 인덱스를 순회하며 증가 조건을 만족할 때 길이를 갱신합니다. 문제 구조가 선형 축 하나라는 점이 차원 선택 결정 배경입니다.

평균 시간복잡도: O(N^2)
최악 시간복잡도: O(N^2)
공간복잡도: O(N)

DP 차원: 2차원 DP(LCS)

문제 의도: 두 문자열 동시 진행이 필요한 대표 2차원 DP를 구현합니다.
입력 예시: a="ABCBDAB", b="BDCABA"
출력 예시: 4

main.cpp

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int lcsLength(const string& a, const string& b) {
    int n = (int)a.size(), m = (int)b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (a[i - 1] == b[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[n][m];
}

int main() {
    cout << lcsLength("ABCBDAB", "BDCABA") << "\n";
    return 0;
}

Main.java

public class Main {
    static int lcsLength(String a, String b) {
        int n = a.length(), m = b.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[n][m];
    }

    public static void main(String[] args) {
        System.out.println(lcsLength("ABCBDAB", "BDCABA"));
    }
}

main.py

def lcs_length(a, b):
    n, m = len(a), len(b)
    # dp[i][j]: a 앞 i개, b 앞 j개의 LCS 길이
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1] + 1
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[n][m]

print(lcs_length("ABCBDAB", "BDCABA"))
# 출력: 4

main.rs

fn lcs_length(a: &str, b: &str) -> usize {
    let mut aa: Vec<char> = Vec::new();
    for ch in a.chars() {
        aa.push(ch);
    }
    let mut bb: Vec<char> = Vec::new();
    for ch in b.chars() {
        bb.push(ch);
    }
    let n = aa.len();
    let m = bb.len();
    let mut dp = vec![vec![0usize; m + 1]; n + 1];

    for i in 1..=n {
        for j in 1..=m {
            if aa[i - 1] == bb[j - 1] {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = dp[i - 1][j].max(dp[i][j - 1]);
            }
        }
    }
    dp[n][m]
}

fn main() {
    println!("{}", lcs_length("ABCBDAB", "BDCABA"));
}

공통 부분수열 축 전개

LCS는 문자열 두 축을 동시에 추적해야 하므로 2차원이 자연스럽습니다. 문자가 같으면 대각선에서 이어지고, 다르면 위/왼쪽 중 더 긴 쪽을 선택합니다. 2차원 격자 위상으로 보면 전이 결정 배경가 명확해집니다.

평균 시간복잡도: O(NM)
최악 시간복잡도: O(NM)
공간복잡도: O(NM)

DP 차원: 2차원 DP(편집 거리)

문제 의도: 삽입/삭제/치환 전이를 갖는 편집 거리 DP를 구현합니다.
입력 예시: a="kitten", b="sitting"
출력 예시: 3

main.cpp

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;

int editDistance(const string& a, const string& b) {
    int n = (int)a.size(), m = (int)b.size();
    vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
    for (int i = 0; i <= n; ++i) dp[i][0] = i;
    for (int j = 0; j <= m; ++j) dp[0][j] = j;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (a[i - 1] == b[j - 1]) dp[i][j] = dp[i - 1][j - 1];
            else dp[i][j] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
        }
    }
    return dp[n][m];
}

int main() {
    cout << editDistance("kitten", "sitting") << "\n";
    return 0;
}

Main.java

public class Main {
    static int editDistance(String a, String b) {
        int n = a.length(), m = b.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 0; i <= n; i++) dp[i][0] = i;
        for (int j = 0; j <= m; j++) dp[0][j] = j;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (a.charAt(i - 1) == b.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = 1 + Math.min(
                        dp[i - 1][j],
                        Math.min(dp[i][j - 1], dp[i - 1][j - 1])
                    );
                }
            }
        }
        return dp[n][m];
    }

    public static void main(String[] args) {
        System.out.println(editDistance("kitten", "sitting"));
    }
}

main.py

def edit_distance(a, b):
    n, m = len(a), len(b)
    dp = [[0] * (m + 1) for _ in range(n + 1)]

    for i in range(n + 1):
        dp[i][0] = i
    for j in range(m + 1):
        dp[0][j] = j

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if a[i - 1] == b[j - 1]:
                dp[i][j] = dp[i - 1][j - 1]
            else:
                dp[i][j] = 1 + min(
                    dp[i - 1][j],     # 삭제
                    dp[i][j - 1],     # 삽입
                    dp[i - 1][j - 1]  # 교체
                )

    return dp[n][m]

print(edit_distance("kitten", "sitting"))
# 출력: 3

main.rs

fn edit_distance(a: &str, b: &str) -> usize {
    let mut aa: Vec<char> = Vec::new();
    for ch in a.chars() {
        aa.push(ch);
    }
    let mut bb: Vec<char> = Vec::new();
    for ch in b.chars() {
        bb.push(ch);
    }
    let n = aa.len();
    let m = bb.len();
    let mut dp = vec![vec![0usize; m + 1]; n + 1];

    for i in 0..=n {
        dp[i][0] = i;
    }
    for j in 0..=m {
        dp[0][j] = j;
    }

    for i in 1..=n {
        for j in 1..=m {
            if aa[i - 1] == bb[j - 1] {
                dp[i][j] = dp[i - 1][j - 1];
            } else {
                dp[i][j] = 1 + dp[i - 1][j].min(dp[i][j - 1]).min(dp[i - 1][j - 1]);
            }
        }
    }
    dp[n][m]
}

fn main() {
    println!("{}", edit_distance("kitten", "sitting"));
}