Ch.10 다이나믹 프로그래밍

문자열 DP — Edit Distance, LCS

Edit Distance(편집 거리) 문제를 2D DP로 풀고 점화식을 설명한다LCS(최장 공통 부분수열)의 구조를 이해하고 구현한다문자열 DP 문제의 공통 패턴을 파악한다

두 문자열은 얼마나 다를까?

맞춤법 검사기는 'kitten'을 'sitting'으로 바꾸려면 최소 몇 번의 편집이 필요한지 계산합니다. 이것이 Edit Distance 문제입니다.

삽입·삭제·교체 세 가지 연산 중 어떤 조합이 최소일까?

dp[i][j] = 첫 번째 문자열의 i글자와 두 번째 문자열의 j글자 사이의 최소 편집 거리

lightbulb

핵심 개념

Edit Distance

한 문자열을 다른 문자열로 바꾸는 데 필요한 최소 편집 횟수

LCS

두 문자열에서 순서를 유지하며 공통으로 나타나는 가장 긴 부분수열

article

핵심 내용

Edit Distance (LeetCode #72) 두 문자열 사이의 최소 편집 횟수

세 가지 연산: • 삽입 (Insert) • 삭제 (Delete) • 교체 (Replace) 점화식: word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] (편집 불필요) word1[i-1] != word2[j-1]: dp[i][j] = 1 + min( dp[i-1][j], # 삭제 dp[i][j-1], # 삽입 dp[i-1][j-1] # 교체 )

코드로 구현하고 dp 테이블을 확인합니다

def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 기저 사례: 빈 문자열에서의 거리
    for i in range(m + 1):
        dp[i][0] = i
    for j in range(n + 1):
        dp[0][j] = j
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if word1[i-1] == word2[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[m][n]

# "kitten" → "sitting" = 3
# (k→s, e→i, 삽입 g)

시간 O(m×n), 공간 O(m×n). 1D 최적화로 O(n) 공간도 가능합니다

LCS (LeetCode #1143) 두 문자열의 최장 공통 부분수열

예시: text1 = "abcde" text2 = "ace" LCS = "ace" → 길이 3 부분수열: 순서는 유지하되 연속일 필요 없음

점화식: text1[i-1] == text2[j-1]: dp[i][j] = dp[i-1][j-1] + 1 (공통 문자!) text1[i-1] != text2[j-1]: dp[i][j] = max(dp[i-1][j], dp[i][j-1])

def longestCommonSubsequence(text1: str, text2: str) -> int:
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[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[m][n]

# "abcde", "ace" → 3

문자열 DP 문제는 공통 패턴을 가집니다

문자열 DP 공통 구조: 1. dp[i][j] — 두 문자열의 접두사 기준 상태 2. 글자가 같으면 → 대각선(dp[i-1][j-1])에서 전이 3. 글자가 다르면 → 위/왼쪽/대각선 중 최적 선택 대표 문제: • Edit Distance — min(삽입, 삭제, 교체) • LCS — max(건너뛰기, 건너뛰기) • Longest Palindromic Subsequence • Regular Expression Matching

문자열 DP를 만나면: dp[i][j]의 정의를 먼저 세우고, 글자 같을 때/다를 때 두 케이스를 나누세요

Edit Distance도 1D 배열로 최적화 가능합니다

# 공간 최적화: O(mn) → O(n)
def minDistance(word1: str, word2: str) -> int:
    m, n = len(word1), len(word2)
    dp = list(range(n + 1))  # 첫 행 초기화
    
    for i in range(1, m + 1):
        prev = dp[0]    # dp[i-1][j-1] 보관
        dp[0] = i
        for j in range(1, n + 1):
            temp = dp[j]
            if word1[i-1] == word2[j-1]:
                dp[j] = prev
            else:
                dp[j] = 1 + min(prev, dp[j], dp[j-1])
            prev = temp
    
    return dp[n]

핵심: prev 변수로 dp[i-1][j-1]을 별도 보관합니다. 1D 배열 갱신 시 덮어써지기 때문!

면접에서 공간 최적화까지 제시하면 시니어 레벨로 평가받습니다

"horse"를 "ros"로 바꾸는 최소 편집 횟수는?

LCS에서 두 글자가 같으면 dp[i-1][j-1] + 1이다

문자열 DP 마스터!

key

핵심 용어

✏️

Edit Distance

삽입·삭제·교체로 문자열을 바꾸는 최소 횟수

🔗

LCS

두 문자열의 최장 공통 부분수열

edit_note

정리 노트

문자열 DP — Edit Distance, LCS

Edit Distance

점화식: 같으면 dp[i-1][j-1], 다르면 1 + min(삭제, 삽입, 교체)
복잡도: 시간 O(m×n), 공간 O(m×n) → O(n)

LCS

점화식: 같으면 dp[i-1][j-1]+1, 다르면 max(dp[i-1][j], dp[i][j-1])
패턴: 두 문자열 → 2D dp, 글자 비교로 전이

★

문자열 DP는 면접에서 '중급→상급' 레벨을 판별하는 핵심 주제입니다!

image

시각 자료

다이어그램: ds-d80

check_circle

핵심 정리

1Edit Distance: 삽입·삭제·교체 최소 횟수
2LCS: 순서 유지 최장 공통 부분수열
3문자열 DP = dp[i][j] + 글자 비교 전이

퀴즈와 인터랙션으로 더 깊이 학습하세요

play_circle인터랙티브 레슨 시작