다이나믹 프로그래밍(DP) 패턴별 완전 정복 – Knapsack부터 비트마스킹 DP까지

def knapsack(weights, values, W):
    """
    0/1 Knapsack 문제 해결

    Args:
        weights: 각 물건의 무게 리스트
        values: 각 물건의 가치 리스트
        W: 배낭의 최대 무게

    Returns:
        최대 가치
    """
    n = len(weights)
    # dp[i][w] = 처음 i개 물건으로 무게 w 이하일 때 최대 가치
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(W + 1):
            # i번째 물건을 선택하지 않는 경우
            dp[i][w] = dp[i-1][w]

            # i번째 물건을 선택할 수 있는 경우
            if weights[i-1] <= w:
                # 선택하지 않는 경우 vs 선택하는 경우 중 최댓값
                dp[i][w] = max(dp[i][w], dp[i-1][w - weights[i-1]] + values[i-1])

    return dp[n][W]

# 예제
weights = [2, 3, 4, 5]
values = [3, 4, 5, 6]
W = 8

print(f"최대 가치: {knapsack(weights, values, W)}")  # 출력: 10

def knapsack_optimized(weights, values, W):
    """
    공간 복잡도 O(W)로 최적화된 Knapsack
    """
    dp = [0] * (W + 1)

    for i in range(len(weights)):
        # 역순으로 순회해야 이전 값이 덮어씌워지지 않음
        for w in range(W, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

    return dp[W]

def unbounded_knapsack(weights, values, W):
    """
    물건을 무한히 선택 가능한 배낭 문제
    """
    dp = [0] * (W + 1)

    # 모든 무게에 대해
    for w in range(1, W + 1):
        # 모든 물건을 시도
        for i in range(len(weights)):
            if weights[i] <= w:
                # 현재 물건을 또 선택할 수 있으므로 dp[w - weights[i]] 사용
                dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

    return dp[W]

# 예제: 동전 교환 문제
coins = [1, 2, 5]  # 동전 종류 (무게)
values = [1, 2, 5]  # 가치 = 액면가
target = 11

print(f"최대 가치: {unbounded_knapsack(coins, values, target)}")  # 출력: 11

def lis_dp(arr):
    """
    O(n^2) DP 방식의 LIS
    """
    n = len(arr)
    if n == 0:
        return 0

    # dp[i] = i번째 원소를 마지막으로 하는 LIS 길이
    dp = [1] * n  # 최소 길이는 자기 자신 1개

    for i in range(1, n):
        for j in range(i):
            # arr[j] < arr[i]이면 arr[j] 뒤에 arr[i]를 붙일 수 있음
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)

    return max(dp)  # 모든 위치 중 최댓값

# 예제
arr = [10, 9, 2, 5, 3, 7, 101, 18]
print(f"LIS 길이: {lis_dp(arr)}")  # 출력: 4

import bisect

def lis_binary_search(arr):
    """
    O(n log n) 이분 탐색 방식의 LIS

    tails[i] = 길이 i+1인 증가 수열의 마지막 원소 중 최솟값
    """
    tails = []  # 증가 수열 유지

    for num in arr:
        # num이 들어갈 위치 찾기 (이분 탐색)
        pos = bisect.bisect_left(tails, num)

        if pos == len(tails):
            # num이 가장 크면 수열 확장
            tails.append(num)
        else:
            # 기존 위치를 더 작은 값으로 갱신
            tails[pos] = num

    return len(tails)

# 예제
arr = [10, 9, 2, 5, 3, 7, 101, 18]
print(f"LIS 길이: {lis_binary_search(arr)}")  # 출력: 4

def lis_with_path(arr):
    """
    LIS 길이와 실제 수열을 함께 반환
    """
    n = len(arr)
    dp = [1] * n
    parent = [-1] * n  # 이전 원소의 인덱스 저장

    for i in range(1, n):
        for j in range(i):
            if arr[j] < arr[i] and dp[j] + 1 > dp[i]:
                dp[i] = dp[j] + 1
                parent[i] = j  # j에서 i로 연결

    # 최댓값 위치 찾기
    max_length = max(dp)
    max_idx = dp.index(max_length)

    # 역추적으로 수열 복원
    lis = []
    idx = max_idx
    while idx != -1:
        lis.append(arr[idx])
        idx = parent[idx]

    return max_length, lis[::-1]  # 역순으로 저장했으므로 뒤집기

# 예제
arr = [10, 9, 2, 5, 3, 7, 101, 18]
length, sequence = lis_with_path(arr)
print(f"LIS 길이: {length}")  # 4
print(f"LIS 수열: {sequence}")  # [2, 3, 7, 101] (또는 다른 가능한 LIS)

def lcs(s1, s2):
    """
    두 문자열의 LCS 길이 계산
    """
    m, n = len(s1), len(s2)
    # dp[i][j] = s1[:i]와 s2[:j]의 LCS 길이
    dp = [[0] * (n + 1) for _ in range(m + 1)]

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                # 문자가 같으면 대각선 값 + 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]

# 예제
s1 = "ABCDGH"
s2 = "AEDFHR"
print(f"LCS 길이: {lcs(s1, s2)}")  # 출력: 3

def lcs_with_string(s1, s2):
    """
    LCS 길이와 실제 문자열을 함께 반환
    """
    m, n = len(s1), len(s2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]

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

    # 역추적으로 LCS 복원
    lcs_str = []
    i, j = m, n
    while i > 0 and j > 0:
        if s1[i-1] == s2[j-1]:
            # 문자가 같으면 LCS에 포함
            lcs_str.append(s1[i-1])
            i -= 1
            j -= 1
        elif dp[i-1][j] > dp[i][j-1]:
            # 위쪽에서 온 경우
            i -= 1
        else:
            # 왼쪽에서 온 경우
            j -= 1

    return dp[m][n], ''.join(reversed(lcs_str))

# 예제
s1 = "ABCDGH"
s2 = "AEDFHR"
length, lcs_str = lcs_with_string(s1, s2)
print(f"LCS 길이: {length}")  # 3
print(f"LCS 문자열: {lcs_str}")  # ADH

def matrix_chain_order(dims):
    """
    행렬 연쇄 곱셈 최소 연산 횟수

    Args:
        dims: 행렬 크기 배열 [p0, p1, ..., pn]
              행렬 Ai는 p[i-1] x p[i] 크기

    Returns:
        최소 곱셈 연산 횟수
    """
    n = len(dims) - 1  # 행렬 개수
    # dp[i][j] = 행렬 i부터 j까지 곱하는 최소 연산 횟수
    dp = [[0] * n for _ in range(n)]

    # length: 곱할 행렬 체인의 길이
    for length in range(2, n + 1):  # 2개부터 n개까지
        for i in range(n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')

            # k: 분할 지점 (i부터 j-1까지)
            for k in range(i, j):
                # [i...k] + [k+1...j] + 합치는 비용
                cost = (
                    dp[i][k] +  # 왼쪽 부분 곱셈
                    dp[k+1][j] +  # 오른쪽 부분 곱셈
                    dims[i] * dims[k+1] * dims[j+1]  # 두 결과 행렬 곱셈
                )
                dp[i][j] = min(dp[i][j], cost)

    return dp[0][n-1]

# 예제: 행렬 크기가 10×20, 20×30, 30×40, 40×30
dims = [10, 20, 30, 40, 30]
print(f"최소 곱셈 횟수: {matrix_chain_order(dims)}")  # 출력: 18000

def tsp(dist):
    """
    외판원 순회 문제 (비트마스킹 DP)

    Args:
        dist: dist[i][j] = 도시 i에서 j로 가는 비용

    Returns:
        최소 비용 (0번 도시에서 시작하여 모든 도시 방문 후 복귀)
    """
    n = len(dist)
    # dp[mask][i] = mask 상태에서 도시 i에 있을 때 남은 최소 비용
    # mask: 방문한 도시를 비트로 표현 (1 << i가 1이면 도시 i 방문)
    dp = [[float('inf')] * n for _ in range(1 << n)]

    # 기저: 모든 도시를 방문한 상태에서 시작 도시(0)로 복귀
    for i in range(n):
        dp[(1 << n) - 1][i] = dist[i][0]  # 도시 i → 0 비용

    # 역순으로 DP (많이 방문한 상태 → 적게 방문한 상태)
    for mask in range((1 << n) - 2, -1, -1):
        for i in range(n):
            # 도시 i를 이미 방문했는지 확인
            if not (mask & (1 << i)):
                continue

            # 다음 방문할 도시 j 시도
            for j in range(n):
                # 아직 방문하지 않은 도시만
                if mask & (1 << j):
                    continue

                # 도시 i → j로 이동
                next_mask = mask | (1 << j)
                dp[mask][i] = min(dp[mask][i], dist[i][j] + dp[next_mask][j])

    return dp[1][0]  # 0번 도시만 방문한 상태에서 시작

# 예제: 4개 도시
dist = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
]
print(f"최소 비용: {tsp(dist)}")  # 출력: 80 (0→1→3→2→0)

# ❌ 잘못된 예: 최댓값을 구할 때 0으로 초기화
dp = [0] * n

# ✅ 올바른 예: -inf로 초기화
dp = [float('-inf')] * n
dp[0] = 0  # 기저 조건만 명시

# ❌ 문자열 인덱스 혼동
if s1[i] == s2[j]:  # i, j는 1부터 시작하는데 문자열은 0부터
    dp[i][j] = dp[i-1][j-1] + 1

# ✅ 올바른 예
if s1[i-1] == s2[j-1]:  # DP 인덱스와 문자열 인덱스 구분
    dp[i][j] = dp[i-1][j-1] + 1

# ❌ 0/1 Knapsack을 정순으로 순회 (같은 물건을 여러 번 선택)
for i in range(n):
    for w in range(weights[i], W + 1):  # 정순
        dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

# ✅ 역순으로 순회
for i in range(n):
    for w in range(W, weights[i] - 1, -1):  # 역순
        dp[w] = max(dp[w], dp[w - weights[i]] + values[i])

# 공간 최적화: O(n^2) → O(n)
def lcs_optimized(s1, s2):
    m, n = len(s1), len(s2)
    prev = [0] * (n + 1)
    curr = [0] * (n + 1)

    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                curr[j] = prev[j-1] + 1
            else:
                curr[j] = max(prev[j], curr[j-1])
        prev, curr = curr, prev  # 행 교체

    return prev[n]