AYSTORY

algo_lec7 본문

Computer Algorithms

algo_lec7

bye0nzn 2025. 4. 14. 19:28

Example 5: Fractional Knapsack

문제 정의

: fractional knapsack problem이란?

 

  • 물건마다 가치(value)와 무게(weight)가 있음
  • 배낭의 최대 수용 무게 W가 주어짐
  • 각 물건은 조각내어 일부만 넣을 수 있음 (fractional 가능)

 

  • 배낭 용량 W 안에서, 물건을 쪼개서 최대 가치를 채워 넣는 문제

Greedy 해법

  • 단위 무게당 가치 (value/weight) 기준으로 내림차순 정렬
  • 배낭에 넣을 수 있을 만큼 넣고, 남으면 일부만 비례하여 넣음

코드 핵심

class Item:
    def __init__(self, value, weight):
        self.value = value
        self.weight = weight

def fractional_knapsack(W, items):
    # value/weight 비율로 정렬 (내림차순)
    items.sort(key=lambda x: x.value / x.weight, reverse=True)

    total_value = 0.0  # 총 가치
    remaining_capacity = W

    for item in items:
        if item.weight <= remaining_capacity:
            # 전체 항목을 넣을 수 있으면 전부 넣음
            total_value += item.value
            remaining_capacity -= item.weight
        else:
            # 일부만 넣고 종료
            fraction = remaining_capacity / item.weight
            total_value += item.value * fraction
            break

    return total_value
  • 정렬 후 반복문으로 가득 찰 때까지 item 추가
  • 시간복잡도: O(n log n)

The greedy approach always gives an optimal solution for the fractional knapsack problem. 

 

Example 6: Shortest Path – Dijkstra's Algorithm

문제 정의

  • 단일 시작 정점에서 다른 정점까지의 최단 경로

핵심 아이디어

  • dist[ ]: 시작점부터의 최단 거리
  • sptSet[ ]: shortest path tree에 포함 여부
  • 방문하지 않은 정점 중 가장 가까운 정점을 선택 → 인접 정점의 거리 갱신

코드 흐름

import sys  # 무한대를 표현하기 위한 용도 (sys.maxsize 사용)

V = 5  # 그래프의 정점 수

# 현재까지 확정되지 않은 정점 중에서 최단 거리(dist)가 가장 짧은 정점을 선택
def minDistance(dist, sptSet):
    min = sys.maxsize  # 초기값은 무한대
    for u in range(V):
        if not sptSet[u] and dist[u] < min:
            min = dist[u]
            min_index = u
    return min_index  # 최단 거리 정점의 인덱스 반환

# Dijkstra 알고리즘 구현
def dijkstra(graph, src):
    dist = [sys.maxsize] * V  # 시작점으로부터 각 정점까지의 거리. 초기값은 무한대
    dist[src] = 0             # 시작점은 거리 0
    sptSet = [False] * V      # 최단 경로가 확정된 정점 여부를 저장하는 배열

    for _ in range(V):
        u = minDistance(dist, sptSet)  # 아직 확정되지 않은 정점 중 최단 거리인 정점 선택
        sptSet[u] = True               # 선택된 정점은 최단 경로 확정

        # 선택된 정점 u에 인접한 모든 정점 v에 대해 거리 갱신
        for v in range(V):
            # 조건:
            # 1. u와 v 사이에 간선이 존재해야 하고 (graph[u][v] > 0)
            # 2. v는 아직 최단 경로가 확정되지 않았으며
            # 3. u를 거쳐 v로 가는 경로가 기존보다 짧을 경우
            if graph[u][v] > 0 and not sptSet[v] and \
               dist[u] + graph[u][v] < dist[v]:
                dist[v] = dist[u] + graph[u][v]  # 거리 갱신

    # 결과 출력: 시작점으로부터 각 정점까지의 최단 거리
    print("Vertex \tDistance from Source")
    for i in range(V):
        print(i, "\t", dist[i])
  • 초기 dist는 ∞, 시작점은 0
  • 인접 정점 탐색하며 조건에 따라 dist 업데이트

예시

  • 5개 정점의 가중치 그래프
  • 각 단계에서 dist[] 값이 갱신됨

Time Complexity

  • O(V²)

가중치가 음수가 아닌 그래프에 대해 항상 최적해 보장

6. Huffman Coding

목적: 문자 인코딩 압축

  • 어떤 문자열에서 문자마다 고정된 길이의 코드 대신, 빈도에 따라 가변 길이 코드를 부여하면 전체 파일 크기를 줄일 수 있음
  • 특히 자주 등장하는 문자는 짧게, 드물게 등장하는 문자는 길게 코딩하면 효율적

기본 용어

  • prefix-free code:
    어떤 코드도 다른 코드의 접두사(prefix)가 되어서는 안 됨
    (예: "0", "01" → 접두사 관계 → X)
  • Huffman Code:
    문자들의 등장 빈도(frequency)를 기반으로 prefix-free한 최적의 이진 코드를 만들어주는 알고리즘
    → Greedy 알고리즘 기반

정의

  • 각 문자를 고유한 Binary cid(이진 코드)로 표현
  • 빈도에 따라 가변 길이 코드를 할당해 전체 길이 최소화

예시

  • fixed-length binary code
    • a:00 b:01 c:11
    • ababcbbbc 000100011101010111 (18 bits)
  • variable-length binary code
    • a:10 b:0 c:11
    • ababcbbbc 1001001100011 (13bits)
  • 허프만 코드 (가변 길이): 150비트 (약 25% 절약 가능)

 

→ 각 줄의 의미는 다음과 같아:

  • freq: 각 문자가 등장하는 횟수 (총 60 + 5 + 30 + 5 = 100회 등장)
  • fixed: 고정 길이 binary code(2비트씩)
    • 4개의 문자니까 ⌈log⁡2 4⌉=2bit 필요
  • prefix: 가변 길이 코드 (Huffman coding 기반)
    • 자주 등장하는 문자일수록 코드가 짧다 (예: a는 1비트)

(1) Fixed-length 코드의 경우:

  • 문자 하나당 2bit 고정
  • 문자 100개 전체 저장에 필요한 비트 수:100×2=200 bits

(2) Prefix code의 경우 (Huffman 기반):

  • 각 문자의 비트 수 × 등장 횟수로 계산: 
문자 빈도 코드 길이 총 bit 수
a 60 1 (code: 0) 60 × 1 = 60
b 5 3 (code: 110) 5 × 3 = 15
c 30 2 (code: 10) 30 × 2 = 60
d 5 3 (code: 111) 5 × 3 = 15
합계 100 — 150 bits

 

얼마나 절약되었는가?

  • Fixed-length: 200비트
  • Prefix code: 150비트
  • 절약된 비트 수: 200−150=50비트
  • 절감률: 50200×100=25%

→ 25% 저장공간 절약

 

 

표 해석: Fixed-length vs Variable-length Huffman Codewords

문자 고정 길이 코드 (3비트) Huffman 코드 (가변 길이)
a 000 0
b 001 101
c 010 100
d 011 111
e 100 1101
f 101 1100

고정 길이 코드

  • 6개의 문자를 표현해야 하므로 최소 ⌈log⁡2 6⌉=3비트 필요
  • 모든 문자가 3비트로 고정됨

Huffman 코드

  • 빈도 기반 트리 구조에 따라 부여된 가변 길이 코드
  • 자주 등장하는 a는 1비트, 드물게 등장하는 e, f는 4비트

아래 그림: 두 개의 Huffman Tree 구조

두 그림 모두 같은 문자 집합을 사용했지만,
Huffman Tree 구성 순서에 따라 구조가 달라질 수 있음을 보여줌.

 

하지만 중요한 건:

두 트리 모두 동일한 total bit 수 (224비트)를 만들어냄 
(왜냐하면, Huffman coding은 최적 prefix-free 코드를 항상 생성하기 때문)

Huffman 인코딩의 총 비트 수 계산

bit(T) = ∑ freq(v_i) × depth(v_i)

  • freq(v_i): 문자 v_i의 등장 횟수
  • depth(v_i): Huffman tree에서 해당 문자가 위치한 깊이 (루트에서의 거리)

적용 예제

문자 freq. depth 계산
a 45 1 45
b 13 3 39
c 12 3 36
d 16 3 48
e 9 4 36
f 5 4 20
합계 100   224비트

 

→ 실제로 슬라이드 전체 Huffman 예제에서 나온 총 비트 수와 정확히 일치.

Example

  1. 가장 작은 두 빈도 f:8, b:9 → 합쳐서 17
    (이게 그림의 오른쪽 하단 트리로 표시됨)
  2. 그 다음 작은 두 빈도 c:12, d:14 → 합쳐서 26
    (왼쪽 하단 트리로 표시됨)
  3. 다음 작은 두 빈도 a:15, 17 → 합쳐서 32
    (오른쪽 상단에서 32가 생김)
  4. 마지막으로 26과 32를 합쳐서 58
    (중앙 루트 노드가 58인 트리 생성)

여기까지 병합한 결과:

  • 왼쪽 서브트리 (26): c, d 포함
  • 오른쪽 서브트리 (32): a, f, b 포함
  • 루트는 58

아직 등장하지 않은 노드: e:42

  • Step 4에서 생성된 트리의 루트가 58
  • 남은 노드 e:42와 위에서 만든 노드 58을 합쳐서 루트 노드 100 생성

알고리즘 흐름

  • 각 문자 빈도수로 우선순위 큐 생성 (min-heap)
  • 빈도 낮은 두 노드를 병합
  • 최종 트리에서 각 문자에 prefix-free codeword 부여

Time Complexity

  • Heap 사용 시 O(n log n)

항상 최적의 prefix-free binary code를 생성함

 

'Computer Algorithms' 카테고리의 다른 글

algo_lec9  (0) 2025.04.24
algo_lec8  (0) 2025.04.14
algo_lec6  (1) 2025.04.13
algo_lec5  (0) 2025.04.13
algo_lec4  (0) 2025.04.13
'Computer Algorithms' Related Articles more