[알고리즘] Week 9: 그리디 알고리즘 - 개념과 예제

Day 1: 그리디 알고리즘의 개념

• 강의 내용:
  • 그리디 알고리즘의 정의와 중요성
    • 그리디 알고리즘(Greedy Algorithm)이란 무엇인가?
    • 그리디 알고리즘의 기본 원리 (국소 최적해 선택)
    • 그리디 알고리즘의 장점 및 활용 사례
  • 그리디 알고리즘의 장단점
    • 장점: 간결하고 이해하기 쉬움, 빠른 실행 시간
    • 단점: 항상 전역 최적해를 보장하지 않음
• 실습:
  • 간단한 그리디 알고리즘 문제 예제 설명

# 동전 교환 문제의 간단한 그리디 알고리즘 예제
def coin_change_greedy(coins, amount):
    coins.sort(reverse=True)
    result = []
    for coin in coins:
        while amount >= coin:
            amount -= coin
            result.append(coin)
    return result

# 예제 실행
coins = [1, 2, 5, 10, 20, 50, 100]
amount = 287
print("동전 교환 결과:", coin_change_greedy(coins, amount))  # [100, 100, 50, 20, 10, 5, 2]

 

Day 2: 활동 선택 문제 (Activity Selection Problem)

• 강의 내용:
  • 활동 선택 문제의 개념과 정의
    • 활동 선택 문제 소개
    • 그리디 접근법을 통한 해결
  • 활동 선택 문제의 구현
    • 종료 시간이 가장 빠른 활동을 선택하는 그리디 전략
• 실습:
  • 활동 선택 문제 알고리즘 구현 및 예제

# 활동 선택 문제 알고리즘 구현
def activity_selection(activities):
    activities.sort(key=lambda x: x[1])
    selected_activities = [activities[0]]
    for i in range(1, len(activities)):
        if activities[i][0] >= selected_activities[-1][1]:
            selected_activities.append(activities[i])
    return selected_activities

# 예제 실행
activities = [(1, 3), (2, 4), (3, 5), (0, 6), (5, 7), (8, 9), (5, 9)]
print("선택된 활동:", activity_selection(activities))  # [(1, 3), (3, 5), (5, 7), (8, 9)]

 

Day 3: 최소 신장 트리 (Minimum Spanning Tree)

• 강의 내용:
  • 최소 신장 트리의 개념과 정의
    • 그래프에서 최소 신장 트리의 중요성
    • 그리디 접근법을 통한 해결 (크루스칼 알고리즘, 프림 알고리즘)
  • 크루스칼 알고리즘 (Kruskal's Algorithm)
    • 간선 선택 기준 (가장 가중치가 작은 간선 선택)
    • 유니온-파인드 자료구조 사용
• 실습:
  • 크루스칼 알고리즘 구현 및 예제

# 크루스칼 알고리즘 구현
class Graph:
    def __init__(self, vertices):
        self.V = vertices
        self.graph = []

    def add_edge(self, u, v, w):
        self.graph.append([u, v, w])

    def find(self, parent, i):
        if parent[i] == i:
            return i
        return self.find(parent, parent[i])

    def union(self, parent, rank, x, y):
        root_x = self.find(parent, x)
        root_y = self.find(parent, y)
        if rank[root_x] < rank[root_y]:
            parent[root_x] = root_y
        elif rank[root_x] > rank[root_y]:
            parent[root_y] = root_x
        else:
            parent[root_y] = root_x
            rank[root_x] += 1

    def kruskal_mst(self):
        result = []
        i = e = 0
        self.graph = sorted(self.graph, key=lambda item: item[2])
        parent = []
        rank = []

        for node in range(self.V):
            parent.append(node)
            rank.append(0)

        while e < self.V - 1:
            u, v, w = self.graph[i]
            i = i + 1
            x = self.find(parent, u)
            y = self.find(parent, v)

            if x != y:
                e = e + 1
                result.append([u, v, w])
                self.union(parent, rank, x, y)

        return result

# 예제 실행
g = Graph(4)
g.add_edge(0, 1, 10)
g.add_edge(0, 2, 6)
g.add_edge(0, 3, 5)
g.add_edge(1, 3, 15)
g.add_edge(2, 3, 4)
print("크루스칼 알고리즘에 의한 최소 신장 트리:", g.kruskal_mst())  # [(2, 3, 4), (0, 3, 5), (0, 1, 10)]

 

Day 4: 프림 알고리즘 (Prim's Algorithm)

• 강의 내용:
  • 프림 알고리즘의 개념과 정의
    • 시작 노드에서부터 신장 트리를 확장하는 그리디 전략
  • 프림 알고리즘의 구현
    • 우선순위 큐 사용
• 실습:
  • 프림 알고리즘 구현 및 예제

# 프림 알고리즘 구현
import heapq

def prim_mst(graph, start):
    mst = []
    visited = set()
    min_heap = [(0, start)]
    
    while min_heap:
        weight, u = heapq.heappop(min_heap)
        if u in visited:
            continue
        visited.add(u)
        mst.append((u, weight))
        
        for v, w in graph[u]:
            if v not in visited:
                heapq.heappush(min_heap, (w, v))
    
    return mst

# 예제 실행
graph = {
    0: [(1, 10), (2, 6), (3, 5)],
    1: [(0, 10), (3, 15)],
    2: [(0, 6), (3, 4)],
    3: [(0, 5), (1, 15), (2, 4)]
}
print("프림 알고리즘에 의한 최소 신장 트리:", prim_mst(graph, 0))  # [(0, 0), (3, 5), (2, 4), (1, 10)]

 

Day 5: 허프만 코딩 (Huffman Coding)

• 강의 내용:
  • 허프만 코딩의 개념과 정의
    • 데이터 압축을 위한 그리디 알고리즘
    • 빈도 기반의 이진 트리 생성
  • 허프만 코딩의 구현
    • 우선순위 큐 사용
• 실습:
  • 허프만 코딩 알고리즘 구현 및 예제

# 허프만 코딩 구현
import heapq

class HuffmanNode:
    def __init__(self, char, freq):
        self.char = char
        self.freq = freq
        self.left = None
        self.right = None
    
    def __lt__(self, other):
        return self.freq < other.freq

def huffman_coding(chars, freqs):
    heap = [HuffmanNode(chars[i], freqs[i]) for i in range(len(chars))]
    heapq.heapify(heap)
    
    while len(heap) > 1:
        node1 = heapq.heappop(heap)
        node2 = heapq.heappop(heap)
        merged = HuffmanNode(None, node1.freq + node2.freq)
        merged.left = node1
        merged.right = node2
        heapq.heappush(heap, merged)
    
    return heap[0]

def print_huffman_tree(node, code=""):
    if node is None:
        return
    if node.char is not None:
        print(f"{node.char}: {code}")
    print_huffman_tree(node.left, code + "0")
    print_huffman_tree(node.right, code + "1")

# 예제 실행
chars = ['a', 'b', 'c', 'd', 'e', 'f']
freqs = [5, 9, 12, 13, 16, 45]
huffman_tree = huffman_coding(chars, freqs)
print("허프만 코딩 결과:")
print_huffman_tree(huffman_tree)

 

Day 6: 그리디 알고리즘의 성능 분석

• 강의 내용:
  • 그리디 알고리즘의 성능 분석
    • 그리디 알고리즘의 시간 복잡도 및 공간 복잡도 분석
    • 최적해를 보장하는 조건
  • 그리디 알고리즘과 다른 접근 방식의 비교
    • 그리디 알고리즘과 동적 프로그래밍의 비교
    • 그리디 알고리즘과 분할 정복의 비교
• 실습:
  • 다양한 그리디 알고리즘의 성능 비교 예제

# 성능 비교 예제: 크루스칼 알고리즘 vs 프림 알고리즘
import time

def measure_time(func, *args):
    start_time = time.time()
    result = func(*args)
    end_time = time.time()
    return end_time - start_time, result

graph = {
    0: [(1, 10), (2, 6), (3, 5)],
    1: [(0, 10), (3, 15)],
    2: [(0, 6), (3, 4)],
    3: [(0, 5), (1, 15), (2, 4)]
}
vertices = 4
edges = [(0, 1, 10), (0, 2, 6), (0, 3, 5), (1, 3, 15), (2, 3, 4)]

# 크루스칼 알고리즘 시간 측정
kruskal_graph = Graph(vertices)
for u, v, w in edges:
    kruskal_graph.add_edge(u, v, w)
kruskal_time, _ = measure_time(kruskal_graph.kruskal_mst)

# 프림 알고리즘 시간 측정
prim_time, _ = measure_time(prim_mst, graph, 0)

print("크루스칼 알고리즘 시간:", kruskal_time)
print("프림 알고리즘 시간:", prim_time)

 

Day 7: 종합 연습 및 프로젝트 준비

• 강의 내용:
  • 그리디 알고리즘 종합 연습
    • 다양한 그리디 알고리즘 문제 풀이
    • 알고리즘 성능 분석 및 최적화
  • 프로젝트 준비
    • 프로젝트 주제 선정 및 요구사항 분석
    • 프로젝트 구현 계획 수립
• 실습:
  • 그리디 알고리즘 종합 연습 문제 풀기
  • 프로젝트 주제 및 계획 수립

### 종합 연습 문제 예시
1. 주어진 작업들을 완료하기 위한 최소 시간 찾기
2. 주어진 문자열을 허프만 코딩을 사용하여 압축
3. 주어진 그래프에서 최소 신장 트리 생성

### 프로젝트 주제 예시
1. 그리디 알고리즘을 활용한 스케줄링 시스템
2. 그리디 알고리즘을 이용한 네트워크 최적화 도구
3. 그리디 알고리즘을 사용한 데이터 압축 및 전송 최적화

### 프로젝트 요구사항 예시
1. 그리디 알고리즘을 활용한 스케줄링 시스템:
   - 작업 입력 및 저장
   - 그리디 알고리즘을 통한 작업 스케줄링
   - 스케줄링된 작업 출력 및 분석

### 프로젝트 계획 예시
1. 데이터 입력 모듈 구현
2. 그리디 알고리즘 구현 (예: 활동 선택 문제, 최소 신장 트리 등)
3. 데이터 출력 및 분석 모듈 구현

 

이 강의는 파이썬의 그리디 알고리즘, 특히 활동 선택 문제, 최소 신장 트리, 허프만 코딩의 기본 개념과 구현을 익히는 것을 목표로 하며, 각 강의는 이론과 실습을 포함합니다. 다음 주차에 대한 상세 강의를 원하시면 말씀해 주세요!