[기말고사] 5. Heap and Greedy Approach

Objectives

• priority 큐 추상적 데이터 구조 및 그 동작에 대해 알아보자
• 힙을 기반으로 한 우선 순위 대기열 작업의 복잡성에 대해 알아보자
• Greedy 프로그래밍 기법 설명
• 문제 해결을 위한 Greedy 접근법 vs. Divide and Conquer
• Greedy 프로그래밍을 사용하여 문제를 해결해야 할 때를 식별
• Greedy 알고리즘이 최적의 솔루션을 제공한다는 것을 증명/반증
• Greedy 접근법을 사용하여 최적화 문제 해결

Content

• Priority Queue
• Greedy Approaches for Scheduling Problem
  • Minimizing Total Time in the System
  • Scheduling with Deadlines
• Huffman code for data compression
• Graph Basics
• Greedy Graph Algorithms
  • Spanning Tree – Prim’s and Kruskal's algorithms
  • Single Source Shortest Path - Dijkstra’s algorithm

---

Priority Queues

• 우선순위 큐는 정렬에 비해 추가적인 유연성을 제공하는 자료구조입니다.
• 가장 작은 (또는 가장 높은 우선순위) 항목을 빠르게 찾을 수 있습니다.
• 이것은 작업들이 시스템에 임의의 간격으로 들어오는 경우에 중요합니다.
• 새 작업을 우선순위 큐에 삽입하는 것이 각 새 도착마다 모든 것을 재정렬하는 것보다 비용 효율적입니다.

---

Scheduling with Deadlines (기한이 있는 스케줄링)

이 스케줄링 접근 방식에서는:

• 각 작업은 한 단위의 시간이 걸립니다.
• 작업이 기한 전에 또는 기한에 시작되면 이익을 얻고, 그렇지 않으면 이익이 없습니다.
• 목표는 총 이익을 최대화하도록 작업을 스케줄링하는 것입니다.
• 모든 작업을 스케줄링할 필요는 없습니다.
• 기한 이후에 작업이 스케줄된 스케줄은 고려할 필요가 없습니다. 왜냐하면 그 스케줄은 작업을 전혀 스케줄하지 않은 경우와 동일한 이익을 가지기 때문입니다. 우리는 그러한 스케줄을 불가능한 스케줄이라고 부릅니다.

 

---

Huffman Code

• 데이터 압축의 문제는 데이터 파일을 인코딩하는 효율적인 방법을 찾는 것입니다.
• 이제 우리는 Huffman Code 와 주어진 파일을 인코딩하기 위한 greedy algorithm에 대해 이야기하겠습니다.

 

Binary Code vs. Variable-Length Binary Code (가변 길이 이진 코드)

Binary Code	Variable-Length Binary Code
파일을 표현하는 일반적인 방법은 이진 코드를 사용하는 것 이러한 코드에서는 각 문자가 codeword라고 불리는 고유한 이진 문자열로 표현됩니다. 고정 길이 이진 코드는 각 문자를 동일한 비트 수를 사용하여 표현합니다.	우리는 가변 길이 이진 코드를 사용하여 더 효율적인 인코딩을 얻을 수 있습니다. 이러한 코드는 다른 문자를 서로 다른 비트 수를 사용하여 표현할 수 있습니다.
a b a b c b b b c
ex) a: 00, b: 01, c: 11	ex) a: 10, b: 0, c: 11
0001000111010101111.	10 0 10 0 11 0 0 0 11
∴ 9 * 2 = 18비트	∴ 13비트

 

Optimal Binary Code Problem (최적의 이진 코드 문제)

• 파일이 주어졌을 때, 최적의 이진 코드 문제는 파일의 문자를 가장 적은 비트 수로 표현하는 이진 코드를 찾는 것
• 먼저, 우리는 prefix(접두사) 코드에 대해 논의하고, 그 다음에 이 문제를 해결하기 위한 Huffman’s algorithm을 개발할 것임

Prefix Codes

• 하나의 특정한 가변 길이 코드 유형은 접두어 코드입니다.
• 접두어 코드에서는 한 문자의 코드워드가 다른 문자의 코드워드의 시작 부분을 구성하지 않습니다.
• 모든 접두어 코드는 이진 트리로 표현될 수 있으며, 이 트리의 잎은 인코딩할 문자들입니다.
  

• 접두어 코드의 장점은 파일을 구문 분석할 때 미리 볼 필요가 없다는 것입니다.
  → 그러니까 막 3 5 이런식이면 어? 3이 작네 이러고 왼쪽 이렇게 가는데 접두어 코드 보면 아 0 왼쪽 아 1 오른쪽 이럼
• 구문 분석을 하기 위해 파일의 왼쪽 첫 번째 비트와 트리의 루트에서 시작합니다.
• 비트를 따라가면서 0 또는 1을 만나면 트리의 왼쪽 또는 오른쪽으로 이동합니다.
• 잎에 도달하면 해당 잎의 문자를 얻습니다.
• 그런 다음 루트로 돌아가 다음 비트부터 다시 절차를 반복합니다.
• ex)
  
  • 우리 문자 집합이 {a, b, c, d, e, f}이고 각 문자가 파일에 나타나는 횟수가 표에 표시된 것과 같다고 가정합시다.
  • 각 인코딩에 대한 비트 수를 계산하십시오.

• code C2와 C3에 해당하는 이진 트리
  

  

  (b)의 경우 뒤에 나올 Huffman's Algorithm에서 살펴볼 것

  
  
• 어떤 코드에 해당하는 이진 트리 T가 주어졌을 때, 파일을 인코딩하는 데 필요한 비트 수는 다음과 같이 계산됩니다:
  

• 여기서 {𝑣1,𝑣2,…,𝑣𝑛}{v1​,v2​,…,vn​}는 파일에 있는 문자 집합이고,
  빈도(𝑣𝑖)는 파일에서 𝑣𝑖​가 나타나는 횟수이며,
  깊이(𝑣𝑖)는 트리 T에서 𝑣𝑖​의 깊이입니다.

 

Huffman’s Algorithm

• 최적의 이진 문자 코드를 생성하는 greedy 알고리즘으로, 최적의 코드에 해당하는 이진 트리를 구성합니다.
• 우선순위 큐를 사용해야합니다.
  • 우선순위 큐에서는 항상 가장 높은 우선순위를 가진 요소가 다음에 제거됩니다.
    • 가장 높은 우선순위를 가진 요소  = 파일에서 빈도가 가장 낮은 문자
  • 우선순위 큐는 연결 리스트로 구현할 수 있지만, 힙으로 구현하는 것이 더 효율적
• ex)

 

Huffman’s Algorithm Time Complexity

• 우선순위 큐가 힙으로 구현된 경우, 초기화는 θ(n) 시간에 완료될 수 있습니다.
• 또한, 각 힙 연산은 θ(log n) 시간이 소요됩니다.
• for-i 루프를 통해 n-1번의 패스를 거치므로, 알고리즘은 θ(n log n) 시간에 실행됩니다.

---

Greedy Approach

• 최적화 문제 해결
• Greedy – 동적 프로그래밍처럼 문제를 더 작은 하위 문제로 나누지 않음
• 일련의 선택을 통해 해결책을 얻음, 각 선택은 그 단계에서 최선의 선택으로 보임
• 지역적으로 최적
• 한 번 선택하면 다시 고려할 수 없음
• 과거 또는 미래의 선택을 고려하지 않고 선택이 이루어짐
• 목표는 전역적으로 최적의 해결책을 도출하는 것
• 최적 – 반드시 증명되어야 함

 

Greedy Algorithm Summary

• Greedy Approaches for Scheduling Problem
  • Minimizing Total Time in the System // 총 시간을 최소화
    • smallest service time first // 가장 짧은 서비스 시간 우선
  • Scheduling with Deadlines // 기한이 있는 스케줄링  
    • highest profit first // 가장 높은 이익 우선
• Huffman code for data compression // 데이터 압축을 위한 허프만 코드  
  • Lowest character frequency first // 가장 낮은 문자 빈도 우선