[정글 WEEK04_알고리즘] 개발일지 - Knapsack Problem으로 알아보는 DP와 Greedy

🪄 DP(Dynamic Programming)

"복잡한 문제를 작은 하위 문제들로 나누고, 그 결과를 저장해두었다가 중복 계산을 피하면서 최적해를 찾는 기법"

 

 1️⃣ 중복되는 부분 문제를 피하기 위해 부분 문제의 결과 저장

 2️⃣ 모든 경우의 수를 고려하며 최적의 해 탐색

 3️⃣ 이전 상태를 기반으로 현재 상태를 계산할 수 있는 점화식 도출 필수

 

✏️ 풀이 방식

아래와 같은 일반적인 피보나치 수열 풀이와 두 가지 DP 풀이를 비교해서 DP의 개념을 확실히 이해해보자!

# 일반적인 피보나치 수열 풀이
def fibonacci(n):
    if n == 0:
        return n
    elif n == 1:
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

 

1. Top-Down 방식 (재귀 + 메모이제이션)

구현이 직관적이고, 문제가 재귀적으로 구성되어있을 때 사용

# DP - '재귀 + 메모이제이션'을 사용한 피보나치 수열 풀이
def fibonacci_top_down_(n, memo):
    if n == 0:
        return n
    elif n == 1:
        return n
    if memo[n] != -1:
        return memo[n]
    memo[n] = fibonacci_top_down(n - 1, memo) + fibonacci_top_down(n - 2, memo)
    
    return memo[n]

memo = [-1] * (n + 1)
fibonacci_top_down(n, memo)

* functools 라이브러리에서 제공하는 lru_cache를 쓰면 메모이제이션을 자동으로 구현해줌

내부적으로 딕셔너리처럼 값을 저장하고 특정 값이 한 번 계산되변 다음엔 바로 반환하는 방식

from functools import lru_cache

@lru_cache(maxsize=None) # 캐시 무한 저장
def fibonacci_top_down(n):
    if n == 0:
        return n
    elif n == 1:
        return n
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

 

2. Bottom-Up 방식 (반복문)

제한 조건이 있거나 공간 최적화가 필요할 때 사용 

# DP - '반복문'을 사용한 피보나치 수열 풀이
def fibonacci_bottom_up(n):
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    
    return dp[n]

 

🪄 Greedy

"항상 지금 당장 최선의 선택을 통해 지역 최적 선택을 전역 최적으로 연결하는 시도를 하는 알고리즘"

 

 1️⃣ 아래 두 조건을 만족시키지 않으면 지역 최적 선택이 항상 전역 최적으로 이어지는 것은 아님

 2️⃣ 탐욕 선택 속성(Greedy Choice Property: 문제의 최적해는 현재 최선의 선택을 포함하고 있으며, 현재의 선택이 이후의 선택을 망치면 안 됨)을 만족해야 함

 3️⃣ 최적 부분 구조(Optimal Substructure: 문제의 최적해는 하위 문제들의 최적해로 구성됨)를 만족해야 함

 

✔︎ Greedy 사용 문제

• Fractional Knapsack

   1) 가치/무게 비율 기준 내림차순 정렬

   2) 하나씩 보면서 배낭에 넣을 수 있는지 확인

   3) 무게가 넘치면 일부만 담고 종료

 

• 회의실 배정

   1) 종료 시간 기준 오름차순 정렬 

   2) 하나씩 보면서 시작 시간이 이전 회의 종료 시간보다 크거나 같은지 확인

   3) 조건 충족하면 선택 (회의 카운트 ++)

 

• Huffman Coding

   1) 문자 빈도 기준 오름차순 정렬

   2) 빈도 낮은 두개 뽑아서 합치고 다시 삽입
   3) 반복해서 트리 완성 

 

• Dijkstra

   1) 거리 기준으로 오름차순 정렬

   2) 현재 가장 가까운 노드 선택
   3) 선택한 노드의 인접 노드에 대해 거리 업데이트

 

• MST(최소 신장 트리)

   [Kruskal] - 간선 기준

   1) 간선 가중치 기준 오름차순 정렬

   2) 간선을 하나씩 순회하면서 싸이클 검사 (Union-Find)
   3) 싸이클 없으면 간선 선택, 있으면 패스

   [Prim] - 정점 기준

   1) 현재 트리에 연결된 정점들에서 나가는 간선들 중, 가중치가 가장 작은 간선 선택

   2) 해당 간선이 연결하는 정점이 아직 트리에 없다면 해당 정점을 트리에 추가

   3) 새로 추가된 정점에서 나갈 수 있는 간선들을 탐색 후보에 추가 

 

---

🎒 Knapsack Problem

"무게 제한이 있는 배낭에 물건들을 골라담아, 그 안에 담긴 물건들의 가치의 총합을 최대화하는 문제"

 

출처: https://ko.wikipedia.org/wiki/%EB%B0%B0%EB%82%AD_%EB%AC%B8%EC%A0%9C

 

실생활 예시

 - 예산 배분

 - 자원이 제한된 서버에  파일 배치

 - 시간 제한 안에 최대한 많은 할 일 처리하기

 - 기업의 투자 문제 등

 

🔖 유형 1. 0/1 Knapsack

(DP) 모든 조합 중 최적의 해 선택 - 각 물건을 한 번만 선택하거나 안 하거나

 - 시간복잡도: O(N * W) (N: 물건 수, W: 배낭 용량)

 - 예시: 게임 아이템 선택, 과제 선택, 예산 범위 내 구매

 

✏️  풀이 전략

1️⃣ 물건을 하나씩 보면서 해당 물건을 넣을 수 있는 무게인지 확인

2️⃣ 넣을 수 있다면 넣는 경우와 넣지 않는 경우 중 더 큰 가치를 선택해 저장

3️⃣ 이 과정을 모든 물건에 대해 반복,마지막에 배낭 최대 무게에서의 최대 가치가 정답

 

⚡️ 배낭 압축

2차원 DP(O (N*W)) -> 1차원 DP(O(K))

def knapsack_2d(weights, values, max_weight):
    n = len(weights)
    dp = [[0] * (max_weight + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        for w in range(max_weight + 1):
            if weights[i - 1] > w:
                dp[i][w] = dp[i - 1][w]
            else:
                dp[i][w] = max(dp[i - 1][w],
                               dp[i - 1][w - weights[i - 1]] + values[i - 1])
    return dp[n][max_weight]

위 코드를 잘 보면 dp[i][w]는 dp[i-1][...]만 참조하므로 이전 행만 있으면 충분

def knapsack_1d(weights, values, max_weight):
    dp = [0] * (max_weight + 1)
    n = len(weights)

    for i in range(n):
        for w in range(max_weight, weights[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[max_weight]

❗️주의할 점 정방향 순회 시 같은 물건을 여러 번 선택하는 경우가 생길 수 있으므로 역방향 순회 필요

 

🔖 유형 2. Fractional Knapsack

(Greedy) 물건을 "쪼개서" 일부만 선택

물건의 가치 대비 무게 비율을 기준으로 정렬한 후 무게 제한까지 계속 채워나감

 - 시간복잡도: O(N log N) (정렬(O(N log N)) + N번 순회(O(N))

 - 예시: 석유/사료 운반, 금 캐기, 유체적 자원 배분, 분량 단위로 나눌 수 있는 프로젝트 할당

 

✏️  풀이 전략

1️⃣ 물건들을 가치/무게 비율 기준으로 내림차순 정렬

2️⃣ 무게 제한이 허용하는 한 물건을 배낭에 통째로 담음

3️⃣ 만약 남은 무게가 부족하다면, 해당 물건의 일부만 담고 종료