이번 커밋은 허프만 코딩, 0-1 배낭 문제, 탐욕적 배낭 문제 알고리즘을 구현하고 테스트하는 내용을 담고 있습니다.

20260430-huffman_knapsack: 알고리즘 문제 구현 및 테스트

이번 커밋은 허프만 코딩, 0-1 배낭 문제, 탐욕적 배낭 문제 알고리즘을 구현하고 테스트하는 내용을 담고 있습니다.

요약

2026년 4월 29일에 메인 브랜치에 푸시된 이 커밋은 Week08_problem 디렉토리 아래의 세 가지 알고리즘 문제를 다룹니다. 허프만 코딩, 0-1 배낭 문제, 그리고 탐욕적 배낭 문제에 대한 파이썬 코드를 작성하고, 각 알고리즘의 올바른 작동을 검증하기 위한 테스트 케이스를 포함합니다. 총 331줄의 코드가 추가되었습니다.

배경 및 목적

알고리즘 강의의 8주차 과제로, 주요 알고리즘 문제 해결 능력을 향상시키는 것이 목적입니다. 허프만 코딩은 데이터 압축에, 배낭 문제는 자원 할당 문제에 사용되는 기본적인 알고리즘입니다. 이러한 알고리즘들의 구현을 통해 문제 해결 능력과 코드 설계 능력을 기르고자 했습니다.

구현 내용

세 개의 파이썬 파일에 걸쳐 알고리즘 구현 및 테스트 코드가 작성되었습니다.

1. `4.5.huffman_problem.py`

허프만 코딩 알고리즘을 구현했습니다.

주요 변경사항:
- Node 클래스를 정의하여 허프만 트리의 노드를 표현합니다. 각 노드는 문자(또는 내부 노드를 나타내는 '*')와 빈도를 가집니다.
- huffman 함수는 주어진 문자들과 빈도를 바탕으로 허프만 트리를 생성합니다. 최소 힙을 사용하여 가장 빈도가 낮은 두 노드를 지속적으로 병합하며 트리를 구축합니다.
- preorder 및 inorder 메서드를 Node 클래스에 추가하여 트리의 전위 및 중위 순회 결과를 얻을 수 있도록 했습니다.
- print_huffman_tree 및 test_huffman 함수를 통해 생성된 허프만 트리의 구조를 시각적으로 확인하고, 예상 결과와 비교하여 검증합니다.
변경 파일: Week08_problem/4.5.huffman_problem.py
추가 라인: 136
삭제 라인: 0
핵심 코드 설명:

def huffman(n, s, f):
    heap = []
    for i in range(n):
        heappush(heap, (f[i], Node(s[i], f[i])))

    while len(heap) > 1:
        freq1, node1 = heappop(heap)
        freq2, node2 = heappop(heap)
        
        merged_freq = freq1 + freq2
        merged_node = Node('*', merged_freq)    
        merged_node.left = node1
        merged_node.right = node2
        heappush(heap, (merged_freq, merged_node))

    return heappop(heap)[1]

이 코드는 최소 힙을 사용하여 빈도가 가장 낮은 문자 노드들을 반복적으로 결합하여 최종 허프만 트리를 구성하는 핵심 로직입니다.

2. `4.6.fractional_knapsack_problem.py`

탐욕적 배낭 문제(Fractional Knapsack Problem)를 구현했습니다.

주요 변경사항:
- Item 클래스를 정의하여 각 아이템의 ID, 무게, 이익, 그리고 단위 무게당 이익을 저장합니다. 단위 무게당 이익을 기준으로 아이템을 정렬할 수 있도록 __lt__ 메서드를 오버라이드했습니다.
- knapsack_fractional 함수는 주어진 배낭 용량 W 내에서 최대 이익을 얻기 위해 아이템을 선택합니다. 단위 무게당 이익이 높은 아이템부터 선택하며, 필요시 아이템의 일부만 포함시킵니다. 힙을 사용하여 단위 무게당 이익이 높은 아이템을 효율적으로 관리합니다.
- test_knapsack_fractional 함수를 통해 다양한 입력에 대한 알고리즘의 정확성을 검증합니다.
변경 파일: Week08_problem/4.6.fractional_knapsack_problem.py
추가 라인: 90
삭제 라인: 0
핵심 코드 설명:

def knapsack_fractional(n, W, w, p):
    heap = []
    for i in range(n):
        item = Item(i + 1, w[i], p[i])
        heappush(heap, (-item.profit_per_weight, item)) # 음수로 푸시하여 최대 힙처럼 사용
    maxprofit = 0
    total_weight = 0

    while heap and total_weight < W:
        _, item = heappop(heap)
        if total_weight + item.weight <= W:
            maxprofit += item.profit
            total_weight += item.weight
        else:
            remain = W - total_weight
            maxprofit += item.profit_per_weight * remain
            total_weight += remain
    return maxprofit

이 코드는 단위 무게당 이익이 높은 아이템부터 우선적으로 선택하여 배낭을 채우는 탐욕적 전략을 구현합니다. 힙을 사용해 효율성을 높였습니다.

3. `4.7.0-1_knapsack_problem.py`

0-1 배낭 문제(0-1 Knapsack Problem)를 동적 프로그래밍(DP) 방식으로 구현했습니다.

주요 변경사항:
- knapsack 함수는 재귀와 메모이제이션(Top-down DP)을 사용하여 최대 이익을 계산합니다. DP 딕셔너리에 이미 계산된 부분 문제의 결과를 저장하여 중복 계산을 방지합니다.
- 각 재귀 호출에서 현재 아이템을 포함할지, 포함하지 않을지에 대한 두 가지 경우를 고려하고, 더 큰 이익을 선택합니다.
- test_knapsack_01_dp 함수를 통해 다양한 배낭 문제 인스턴스에 대한 최대 이익을 계산하고 검증합니다.
변경 파일: Week08_problem/4.7.0-1_knapsack_problem.py
추가 라인: 105
삭제 라인: 0
핵심 코드 설명:

def knapsack(n, W, DP):
    global w, p
    if (n, W) in DP:
        return DP[(n, W)]

    if n == 0 or W <= 0:
        DP[(n, W)] = 0
    else:
        if w[n - 1] > W:
            DP[(n, W)] = knapsack(n - 1, W, DP)
        else:
            DP[(n, W)] = max(knapsack(n - 1, W, DP), p[n - 1] + knapsack(n - 1, W - w[n - 1], DP))
    return DP[(n, W)]

이 코드는 0-1 배낭 문제의 최적 해를 찾기 위해 동적 프로그래밍의 재귀적 구조와 메모이제이션을 효과적으로 활용합니다.

기술적 의사결정

자료구조 선택: 세 알고리즘 모두에서 효율적인 구현을 위해 heapq 모듈의 힙(Heap) 자료구조를 사용했습니다.
- 허프만 코딩에서는 최소 빈도의 노드를 빠르게 찾기 위해 사용했습니다.
- 탐욕적 배낭 문제에서는 단위 무게당 이익이 높은 아이템을 효율적으로 선택하기 위해 사용했습니다.
- 0-1 배낭 문제에서는 재귀 호출 시 부분 문제의 결과를 저장하고 검색하기 위해 딕셔너리(DP)를 사용했습니다. 이는 동적 프로그래밍의 핵심적인 메모이제이션 기법입니다.

배운 점 및 개선점

알고리즘 이해 심화: 각 알고리즘의 동작 원리를 코드 구현을 통해 깊이 이해할 수 있었습니다. 특히, 허프만 코딩에서 빈도 기반으로 트리를 구축하는 과정과, 배낭 문제에서 탐욕적 또는 동적 프로그래밍 접근 방식의 차이를 명확히 구분할 수 있었습니다.
재귀와 메모이제이션: 0-1 배낭 문제 구현에서 재귀 호출과 메모이제이션의 중요성을 다시 한번 확인할 수 있었습니다. 이를 통해 복잡한 문제를 효율적으로 해결하는 방법을 익혔습니다.
테스트 케이스의 중요성: 다양한 테스트 케이스를 작성하고 통과시키는 과정에서 코드의 정확성을 높일 수 있었습니다. 특히, 엣지 케이스나 복잡한 시나리오에 대한 테스트 케이스는 알고리즘의 견고함을 보장하는 데 필수적입니다.
향후 개선점:
- 0-1 배낭 문제의 경우, Bottom-up DP 방식도 고려해 볼 수 있습니다. 이는 재귀 호출 오버헤드를 줄이고 특정 상황에서는 더 직관적일 수 있습니다.
- 각 알고리즘에 대한 시간 복잡도 및 공간 복잡도 분석을 추가하여 효율성을 평가하는 것도 좋은 학습이 될 것입니다.

참고 자료

강의 자료 및 관련 알고리즘 설명 문서 (별도 명시되지 않음)

20260430-huffman_knapsack: 알고리즘 문제 구현 및 테스트

요약

배경 및 목적

구현 내용

1. 4.5.huffman_problem.py

2. 4.6.fractional_knapsack_problem.py

3. 4.7.0-1_knapsack_problem.py