[Week04] Dynamic Progrmming, Linked-List

Linked List (연결 리스트)

핵심 개념

• 노드(Node)들이 포인터로 연결된 선형 구조. 임의 접근은 불가하지만 삽입/삭제가 위치만 알면 O(1).
• 종류: 단일(Singly), 이중(Doubly), 원형(Circular), 더미(dummy) 헤드/테일 사용 여부.
• 언제 유리? 크기 가변, 중간 삽입/삭제 잦을 때, 큐/스택/해시 체이닝, LRU 캐시 등.

필수 연산 & 패턴

class Node:
    def __init__(self, val=0, nxt=None):
        self.val = val
        self.next = nxt

class SinglyLinkedList:
    def __init__(self):
        self.head = Node()  # dummy

    def push_front(self, x):
        n = Node(x, self.head.next)
        self.head.next = n

    def find(self, x):
        cur = self.head.next
        while cur and cur.val != x:
            cur = cur.next
        return cur

    def delete(self, x):
        prev, cur = self.head, self.head.next
        while cur:
            if cur.val == x:
                prev.next = cur.next
                return True
            prev, cur = cur, cur.next
        return False

대표 테크닉

def reverse(head):
    prev, cur = None, head
    while cur:
        nxt = cur.next
        cur.next = prev
        prev, cur = cur, nxt
    return prev

def kth_from_end(head, k):
    fast = slow = head
    for _ in range(k):
        if not fast: return None
        fast = fast.next
    while fast:
        fast = fast.next
        slow = slow.next
    return slow

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast: return True
    return False

Dynamic Programming (DP)

• 중복 부분문제 + 최적 부분구조가 있을 때 사용.
• Top-down (재귀+메모이제이션) vs Bottom-up (반복+테이블).

DP 절차

1. 상태 정의 dp[i] 의미 문장화
2. 전이 식 설계
3. 기저/초기값
4. 순회 순서
5. 정답 위치 파악

def dp_template(n):
    dp = [0]*(n+1)
    dp[0] = base
    for i in range(1, n+1):
        dp[i] = f(dp[i-1], dp[i-2], input[i])
    return dp[n]

DP 복잡도 표

문제	상태	시간
Fibonacci	dp[i]	O(n)
LCS	dp[i][j]	O(n·m)
Knapsack	dp[w]	O(N·W)
LIS	dp[i]	O(n²)

Knapsack Problem (배낭 문제)

• 0/1 배낭: 아이템은 0번 또는 1번 선택
• Unbounded: 여러 번 가능
• Fractional: 분할 가능 → Greedy

0/1 Knapsack

def knapsack_01(weights, values, W):
    n = len(weights)
    dp = [0]*(W+1)
    for i in range(n):
        w,v = weights[i], values[i]
        for cap in range(W, w-1, -1):
            dp[cap] = max(dp[cap], dp[cap-w]+v)
    return dp[W]

Unbounded Knapsack

def knapsack_unbounded(weights, values, W):
    dp = [0]*(W+1)
    for i in range(len(weights)):
        w,v = weights[i], values[i]
        for cap in range(w, W+1):
            dp[cap] = max(dp[cap], dp[cap-w]+v)
    return dp[W]

Fractional Knapsack

def fractional_knapsack(items, W):
    items.sort(key=lambda x: x[0]/x[1], reverse=True)
    value = 0.0
    for v,w in items:
        if W == 0: break
        take = min(W, w)
        value += v*(take/w)
        W -= take
    return value