18_dp.py - Examples

  1"""
  2동적 프로그래밍 (Dynamic Programming) 기초
  3Basic Dynamic Programming
  4
  5복잡한 문제를 작은 하위 문제로 나누어 해결하는 알고리즘 기법입니다.
  6"""
  7
  8from typing import List
  9from functools import lru_cache
 10
 11
 12# =============================================================================
 13# 1. 피보나치 수열 (세 가지 방법)
 14# =============================================================================
 15
 16# 방법 1: 재귀 (비효율적 - O(2^n))
 17def fibonacci_recursive(n: int) -> int:
 18    """재귀: 지수 시간 복잡도"""
 19    if n <= 1:
 20        return n
 21    return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)
 22
 23
 24# 방법 2: 메모이제이션 (Top-down DP)
 25def fibonacci_memo(n: int, memo: dict = None) -> int:
 26    """메모이제이션: O(n)"""
 27    if memo is None:
 28        memo = {}
 29    if n in memo:
 30        return memo[n]
 31    if n <= 1:
 32        return n
 33    memo[n] = fibonacci_memo(n - 1, memo) + fibonacci_memo(n - 2, memo)
 34    return memo[n]
 35
 36
 37# 방법 2b: lru_cache 데코레이터 사용
 38@lru_cache(maxsize=None)
 39def fibonacci_cached(n: int) -> int:
 40    """lru_cache 사용: O(n)"""
 41    if n <= 1:
 42        return n
 43    return fibonacci_cached(n - 1) + fibonacci_cached(n - 2)
 44
 45
 46# 방법 3: 테뷸레이션 (Bottom-up DP)
 47def fibonacci_tabulation(n: int) -> int:
 48    """테뷸레이션: O(n) 시간, O(n) 공간"""
 49    if n <= 1:
 50        return n
 51    dp = [0] * (n + 1)
 52    dp[1] = 1
 53    for i in range(2, n + 1):
 54        dp[i] = dp[i - 1] + dp[i - 2]
 55    return dp[n]
 56
 57
 58# 방법 4: 공간 최적화
 59def fibonacci_optimized(n: int) -> int:
 60    """공간 최적화: O(n) 시간, O(1) 공간"""
 61    if n <= 1:
 62        return n
 63    prev2, prev1 = 0, 1
 64    for _ in range(2, n + 1):
 65        curr = prev1 + prev2
 66        prev2, prev1 = prev1, curr
 67    return prev1
 68
 69
 70# =============================================================================
 71# 2. 계단 오르기 (Climbing Stairs)
 72# =============================================================================
 73def climb_stairs(n: int) -> int:
 74    """
 75    한 번에 1칸 또는 2칸 오를 수 있을 때
 76    n개의 계단을 오르는 경우의 수
 77    """
 78    if n <= 2:
 79        return n
 80    prev2, prev1 = 1, 2
 81    for _ in range(3, n + 1):
 82        curr = prev1 + prev2
 83        prev2, prev1 = prev1, curr
 84    return prev1
 85
 86
 87# =============================================================================
 88# 3. 동전 교환 (Coin Change)
 89# =============================================================================
 90def coin_change(coins: List[int], amount: int) -> int:
 91    """
 92    주어진 동전으로 금액을 만드는 최소 동전 개수
 93    불가능하면 -1 반환
 94    """
 95    dp = [float('inf')] * (amount + 1)
 96    dp[0] = 0
 97
 98    for i in range(1, amount + 1):
 99        for coin in coins:
100            if coin <= i and dp[i - coin] != float('inf'):
101                dp[i] = min(dp[i], dp[i - coin] + 1)
102
103    return dp[amount] if dp[amount] != float('inf') else -1
104
105
106def coin_change_ways(coins: List[int], amount: int) -> int:
107    """
108    주어진 동전으로 금액을 만드는 경우의 수
109    """
110    dp = [0] * (amount + 1)
111    dp[0] = 1
112
113    for coin in coins:
114        for i in range(coin, amount + 1):
115            dp[i] += dp[i - coin]
116
117    return dp[amount]
118
119
120# =============================================================================
121# 4. 0/1 배낭 문제 (Knapsack)
122# =============================================================================
123def knapsack_01(weights: List[int], values: List[int], capacity: int) -> int:
124    """
125    0/1 배낭 문제: 각 아이템을 넣거나 안 넣거나
126    최대 가치 반환
127    """
128    n = len(weights)
129    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
130
131    for i in range(1, n + 1):
132        for w in range(capacity + 1):
133            # 현재 아이템을 넣지 않는 경우
134            dp[i][w] = dp[i - 1][w]
135            # 현재 아이템을 넣을 수 있으면
136            if weights[i - 1] <= w:
137                dp[i][w] = max(dp[i][w], dp[i - 1][w - weights[i - 1]] + values[i - 1])
138
139    return dp[n][capacity]
140
141
142def knapsack_01_optimized(weights: List[int], values: List[int], capacity: int) -> int:
143    """0/1 배낭 (공간 최적화 - 1D 배열)"""
144    dp = [0] * (capacity + 1)
145
146    for i in range(len(weights)):
147        # 역순으로 순회 (같은 아이템 중복 사용 방지)
148        for w in range(capacity, weights[i] - 1, -1):
149            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
150
151    return dp[capacity]
152
153
154# =============================================================================
155# 5. 최장 공통 부분 수열 (LCS)
156# =============================================================================
157def longest_common_subsequence(text1: str, text2: str) -> int:
158    """
159    두 문자열의 최장 공통 부분 수열 길이
160    """
161    m, n = len(text1), len(text2)
162    dp = [[0] * (n + 1) for _ in range(m + 1)]
163
164    for i in range(1, m + 1):
165        for j in range(1, n + 1):
166            if text1[i - 1] == text2[j - 1]:
167                dp[i][j] = dp[i - 1][j - 1] + 1
168            else:
169                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
170
171    return dp[m][n]
172
173
174def get_lcs_string(text1: str, text2: str) -> str:
175    """LCS 문자열 복원"""
176    m, n = len(text1), len(text2)
177    dp = [[0] * (n + 1) for _ in range(m + 1)]
178
179    for i in range(1, m + 1):
180        for j in range(1, n + 1):
181            if text1[i - 1] == text2[j - 1]:
182                dp[i][j] = dp[i - 1][j - 1] + 1
183            else:
184                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
185
186    # 역추적
187    lcs = []
188    i, j = m, n
189    while i > 0 and j > 0:
190        if text1[i - 1] == text2[j - 1]:
191            lcs.append(text1[i - 1])
192            i -= 1
193            j -= 1
194        elif dp[i - 1][j] > dp[i][j - 1]:
195            i -= 1
196        else:
197            j -= 1
198
199    return ''.join(reversed(lcs))
200
201
202# =============================================================================
203# 6. 최장 증가 부분 수열 (LIS)
204# =============================================================================
205def longest_increasing_subsequence(nums: List[int]) -> int:
206    """
207    최장 증가 부분 수열 길이 (O(n²))
208    """
209    if not nums:
210        return 0
211
212    n = len(nums)
213    dp = [1] * n  # dp[i] = nums[i]로 끝나는 LIS 길이
214
215    for i in range(1, n):
216        for j in range(i):
217            if nums[j] < nums[i]:
218                dp[i] = max(dp[i], dp[j] + 1)
219
220    return max(dp)
221
222
223def lis_binary_search(nums: List[int]) -> int:
224    """
225    최장 증가 부분 수열 길이 (O(n log n))
226    이분 탐색 활용
227    """
228    from bisect import bisect_left
229
230    if not nums:
231        return 0
232
233    tails = []  # tails[i] = 길이 i+1인 LIS의 마지막 원소 최솟값
234
235    for num in nums:
236        pos = bisect_left(tails, num)
237        if pos == len(tails):
238            tails.append(num)
239        else:
240            tails[pos] = num
241
242    return len(tails)
243
244
245# =============================================================================
246# 7. 최대 부분 배열 합 (Kadane's Algorithm)
247# =============================================================================
248def max_subarray_sum(nums: List[int]) -> int:
249    """
250    연속 부분 배열의 최대 합 (카데인 알고리즘)
251    O(n) 시간, O(1) 공간
252    """
253    if not nums:
254        return 0
255
256    max_sum = curr_sum = nums[0]
257
258    for num in nums[1:]:
259        curr_sum = max(num, curr_sum + num)
260        max_sum = max(max_sum, curr_sum)
261
262    return max_sum
263
264
265# =============================================================================
266# 8. House Robber
267# =============================================================================
268def rob(nums: List[int]) -> int:
269    """
270    인접한 집을 털 수 없을 때 최대 금액
271    """
272    if not nums:
273        return 0
274    if len(nums) <= 2:
275        return max(nums)
276
277    prev2, prev1 = nums[0], max(nums[0], nums[1])
278
279    for i in range(2, len(nums)):
280        curr = max(prev1, prev2 + nums[i])
281        prev2, prev1 = prev1, curr
282
283    return prev1
284
285
286# =============================================================================
287# 테스트
288# =============================================================================
289def main():
290    print("=" * 60)
291    print("동적 프로그래밍 (DP) 기초 예제")
292    print("=" * 60)
293
294    # 1. 피보나치
295    print("\n[1] 피보나치 수열")
296    n = 10
297    print(f"    fib({n}) = {fibonacci_tabulation(n)}")
298    print(f"    처음 10개: {[fibonacci_optimized(i) for i in range(10)]}")
299
300    # 2. 계단 오르기
301    print("\n[2] 계단 오르기")
302    for n in [2, 3, 5]:
303        ways = climb_stairs(n)
304        print(f"    {n}개 계단: {ways}가지")
305
306    # 3. 동전 교환
307    print("\n[3] 동전 교환")
308    coins = [1, 2, 5]
309    amount = 11
310    min_coins = coin_change(coins, amount)
311    ways = coin_change_ways(coins, amount)
312    print(f"    동전: {coins}, 금액: {amount}")
313    print(f"    최소 동전 수: {min_coins}")
314    print(f"    경우의 수: {ways}")
315
316    # 4. 0/1 배낭
317    print("\n[4] 0/1 배낭 문제")
318    weights = [2, 3, 4, 5]
319    values = [3, 4, 5, 6]
320    capacity = 5
321    max_value = knapsack_01(weights, values, capacity)
322    print(f"    무게: {weights}, 가치: {values}")
323    print(f"    용량: {capacity}, 최대 가치: {max_value}")
324
325    # 5. LCS
326    print("\n[5] 최장 공통 부분 수열 (LCS)")
327    text1, text2 = "ABCDGH", "AEDFHR"
328    length = longest_common_subsequence(text1, text2)
329    lcs_str = get_lcs_string(text1, text2)
330    print(f"    문자열1: {text1}")
331    print(f"    문자열2: {text2}")
332    print(f"    LCS 길이: {length}, LCS: '{lcs_str}'")
333
334    # 6. LIS
335    print("\n[6] 최장 증가 부분 수열 (LIS)")
336    nums = [10, 9, 2, 5, 3, 7, 101, 18]
337    length = longest_increasing_subsequence(nums)
338    length_fast = lis_binary_search(nums)
339    print(f"    배열: {nums}")
340    print(f"    LIS 길이: {length} (O(n²)), {length_fast} (O(n log n))")
341
342    # 7. 최대 부분 배열 합
343    print("\n[7] 최대 부분 배열 합 (Kadane)")
344    nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
345    max_sum = max_subarray_sum(nums)
346    print(f"    배열: {nums}")
347    print(f"    최대 합: {max_sum}")
348
349    # 8. House Robber
350    print("\n[8] House Robber")
351    houses = [2, 7, 9, 3, 1]
352    max_money = rob(houses)
353    print(f"    집별 금액: {houses}")
354    print(f"    최대 금액: {max_money}")
355
356    print("\n" + "=" * 60)
357    print("DP 접근 방식 비교")
358    print("=" * 60)
359    print("""
360    | 방식           | 방향      | 구현          | 장점                    |
361    |---------------|----------|---------------|------------------------|
362    | 메모이제이션   | Top-down | 재귀 + 캐시   | 필요한 부분만 계산       |
363    | 테뷸레이션     | Bottom-up| 반복문 + 배열 | 스택 오버플로우 없음     |
364
365    DP 문제 해결 단계:
366    1. 상태 정의: dp[i]가 무엇을 의미하는지
367    2. 점화식 도출: dp[i]를 이전 상태로 표현
368    3. 초기값 설정: base case
369    4. 계산 순서 결정: 의존성에 따라
370    5. 정답 도출: dp 테이블에서 답 추출
371    """)
372
373
374if __name__ == "__main__":
375    main()