동적 계획법 - 2. DP의 기본 패턴 익히기

2. DP의 기본 패턴 익히기

동적 계획법(DP)을 효율적으로 사용하려면 기본적인 패턴을 익히는 것이 중요합니다. 여기서는 1차원 DP와 2차원 DP를 활용하는 대표적인 문제들을 소개합니다.

---

2-1. 기본적인 1차원 DP

1차원 DP는 배열 또는 변수 몇 개를 이용해 최적의 해를 구하는 방식입니다. 대표적인 예제로 피보나치 수열, 계단 오르기 문제, 동전 거스름돈 문제 등을 살펴보겠습니다.

---

📌 계단 오르기 문제 (Climbing Stairs)

문제 설명

• 한 번에 1칸 또는 2칸씩 오를 수 있을 때, n개의 계단을 오르는 방법의 수를 구하는 문제.
• 예시:
  • 계단이 3개일 때 가능한 경우: (1,1,1), (1,2), (2,1) → 총 3가지 방법.

점화식

dp(n)=dp(n−1)+dp(n−2)

초기 조건:

dp(1)=1,dp(2)=2

피보나치 수열과의 관계

• 위 점화식이 피보나치 수열과 동일해 보이지만, 초기값이 다르기 때문에 결과값이 다릅니다.
• 피보나치 수열은 F(0) = 0, F(1) = 1로 시작하지만, 계단 오르기 문제는 dp(1) = 1, dp(2) = 2로 시작합니다.
• 따라서 dp(n)은 피보나치 수열에서 한 칸씩 밀린 형태입니다.

시간 복잡도:

• O(n) (반복문 1회 실행)
• 공간 복잡도: O(1) (변수 2개 사용)

바텀업 DP 코드

def climb_stairs(n):
    if n <= 2:
        return n
    a, b = 1, 2
    for _ in range(3, n+1):
        a, b = b, a + b
    return b

# 테스트 케이스
print(climb_stairs(5))  # 출력: 8
print(climb_stairs(10))  # 출력: 89

---

2-2. DP의 2차원 배열 활용

2차원 DP는 행렬이나 표를 사용하여 최적해를 구하는 방식입니다.

---

📌 최장 증가 부분 수열 (LIS, Longest Increasing Subsequence)

문제 설명

• 주어진 수열에서 길이가 가장 긴 증가하는 부분 수열을 찾는 문제.

점화식

dp[i]=max⁡(dp[j]+1)  for all j<i and nums[j]<nums[i]

시간 복잡도:

• O(n^2) (기본 DP)
• O(nlog⁡n) (이진 탐색을 활용한 최적화)

---

📌 LIS 최적화 (O(n log n), 이진 탐색 활용)

• tails 리스트를 유지하여 가장 작은 증가 부분 수열을 관리합니다.
• bisect_left()을 이용해 삽입 위치를 찾아 업데이트합니다.

from bisect import bisect_left

def longest_increasing_subsequence_optimized(nums):
    if not nums:
        return 0
    tails = []
    for num in nums:
        pos = bisect_left(tails, num)
        if pos == len(tails):
            tails.append(num)
        else:
            tails[pos] = num
    return len(tails)

# 테스트 케이스
print(longest_increasing_subsequence_optimized([10, 9, 2, 5, 3, 7, 101, 18]))  # 출력: 4 (2, 3, 7, 101)
print(longest_increasing_subsequence_optimized([0, 1, 0, 3, 2, 3]))  # 출력: 4 (0, 1, 2, 3)
print(longest_increasing_subsequence_optimized([7, 7, 7, 7]))  # 출력: 1 (모든 값이 같음)

---

📌 LCS와 LIS의 차이점

문제 유형	설명	시간 복잡도
LCS (Longest Common Subsequence)	두 문자열에서 순서를 유지하면서 가장 긴 공통 부분을 찾음	O(m×n)
LIS (Longest Increasing Subsequence)	하나의 수열에서 증가하는 부분 수열의 최댓값을 찾음	O(n^2) (DP) / O(nlog⁡n) (이진 탐색 활용)