Ch 04. 그리디 알고리즘 (2)

4.4 집합 커버 문제

개념

• U = {1, 2, 3, 4, ..., n}
• F = {$S_1, S_2, S_3, ... , S_n$}, $S_n\subset U$
• F에서 어떤 집합들을 선택하여 합집합하면 U와 같아질까?
• $S_k+S_l+... = U$일 때까지 F에서 선택하는 집합들의 수를 최소화하는 문제

신도시 학교 배치 문제

• 10개의 마을이 신도시에 만들어질 계획이다.
• 아래의 2가지 조건이 만족되도록 학교 위치를 선정해야 한다.
  • 학교는 마을에 위치해야 한다.
  • 등교 거리는 걸어서 15분 이내이어야 한다.
• 어느 마을에 학교를 신설해야 학교의 수가 최소가 되는가?
  
  

• 최적해
  

  $S_2$∪$S_6$ = {1, 2, 3, 4, 8}∪{5, 6, 7, 9, 10}
  = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} = U
  따라서, 2와 6 위치에 배치하는 것이 최적

  • F 집합의 모든 조합을 하나씩 합집합하여 U가 되는지 확인하고 최소 집합 수를 찾는다.
  • 그러나 n개 원소일 때, $2^n-1$ 개 검사 -> n이 커지면 최적해 찾기 불가능
  • 최적해에 근접한 근사해 찾기! => How? 그리디 방법으로!

• 근사해
  • 집합 $S_i$가 현재 상태의 U에 있는 원소를 가장 많이 커버하면 그리디하게 $S_i$를 집합 커버에 포함시킨다.
  • 근사 알고리즘

1. U의 원소를 가장 많이 커버하는 집합인 $S_4$={2, 3, 4, 5, 7, 8}을 F에서 선택
   • U = U - $S_4$ = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} - {2, 3, 4, 5, 7, 8} = {1, 6, 9, 10}
2. U의 원소를 가장 많이 커버하는 집합인 $S_6$={5, 6, 7, 9, 10}을 F에서 선택
   • U = U - $S_4$ = {1, 6, 9, 10} - {5, 6, 7, 9, 10} = {1}
3. U의 원소를 가장 많이 커버하는 집합인 $S_1$={1, 2, 3, 8}을 F에서 선택($S_1$ 대신에 $S_2$, $S_3$, $S_8$ 중에서 어느 하나를 선택해도 무방)
   • U = U - $S_1$ = {1} - {1, 2, 3, 8}=∅
     
     따라서, 1, 4, 6 위치에 배치하는 것이 근사적으로 최적

구현

• Pseudocode
  입력: U = {1, 2, 3, 4, ..., n}, F = {$S_1, S_2, S_3, ... , S_n$}
  출력: 집합 커버 C

SetCover(U, F){
	C = NULL; //C 초기화
    while(!U){ //U가 공집합이 될 때까지
    	U의 원소를 가장 많이 커버하는 집합 S_i 선택;
        // 각 집합 S_i와 U의 원소를 비교
        U = U - S_i;
        F = F - S_i;
        C = C + S_i;
    }
    return C;
 }

시간복잡도

• while-Loop: n번 * O(1)(U 비었는지 검사) = $O(n)$

  • 각각의 $S_i$를 U와 비교: n($S_i$ 최대 개수) * O(n)(하나의 $S_i$ 비교하는 데 걸리는 시간) = $O(n^2)$
  • U에서 $S_i$ 원소 제거: $O(n)$
  • F에서 $S_i$ 제거: $O(1)$
  • C에 $S_i$ 추가: $O(n)$

  $\therefore O(n)*O(n^2)=O(n^3)$

---

4.5 작업 스케줄링

개념

• 작업의 수행 시간이 중복되지 않도록 모든 작업을 가장 적은 수의 기계에 배정하는 문제
• 작업 스케줄링 문제에 주어진 문제 요소
  • 작업의 수: 입력의 크기(알고리즘 직접적 요소 X)
  • 각 작업의 시작시간과 종료시간
  • 작업의 길이

그리디 알고리즘

• 빠른 시작시간 작업 우선 (Earliest start time first) 배정
  • 이 알고리즘만 최적해 보장
• 빠른 종료시간 작업 우선 (Earliest finish time first) 배정
• 짧은 작업 우선 (Shortest job first) 배정
• 긴 작업 우선 (Longest job first) 배정

과정(빠른 시작시간 작업 우선 (Earliest start time first) 배정)

• 작업 [시작시간, 종료시간]
  t1=[7,8], t2=[3,7], t3=[1,5], t4=[5,9], t5=[0,2], t6=[6,8], t7=[1,6]

1. 시작시간의 오름차순으로 정렬(빠른 시작시간 작업부터)

   • [0,2], [1,6], [1,5], [3,7], [5,9], [6,8], [7,8]

2. 기계 1에 배정 가능하므로 작업 [0, 2] 배정
   

3. 기계 2에 배정 불가능하므로 기계 2에 작업 [1,6] 배정
   

4. 기계 1, 2에 배정 불가능하므로 기계 3에 작업 [1,5] 배정
   

5. 기계 1에 배정 가능하므로 기계 1에 작업 [3,7] 배정
   

6. 기계 1, 2에 배정 불가능, 기계 3에 배정 가능하므로 기계 3에 작업 [5,9] 배정
   

7. 기계 1, 3에 배정 불가능, 기계 2에 배정 가능하므로 기계 2에 작업 [6,8] 배정
   

8. 기계 2, 3에 배정 불가능, 기계 1에 배정 가능하므로 기계 1에 작업 [7,8] 배정
   

구현

• Pseudocode
  입력: n개의 작업 $t_1, t_2, ..., t_n$ 리스트 L
  출력: 각 기계에 배정된 작업 순서

	JobScheduling(L)
    	시작시간 오름차순으로 L 정렬;
        while (!L){//L이 빌 때까지
        	L에서 가장 이른 시작시간 작업 t_i 가져오기;
            
            if (t_i 실행가능 기계 있으면)
            	t_i 실행가능 기계에 배정;
            else
            	새로운 기계에 t_i 배정;
            L = L - t_i;
        }
        return 각 기계에 배정된 작업 순서;

빠른 종료시간 작업 우선 (Earliest finish time first) 배정

시간복잡도

• 작업 시작시간 정렬: $O(nlogn)$ => 최소 힙정렬
• while Loop: $n$번
  • 사용가능 기계 찾기: $O(m)$ => m은 기계 수

$\therefore$ $O(nlogn)+O(mn)$

---

4.6 허프만 압축

개념

• 고정 길이 코드(Fixed Length Code)
  파일의 각 문자가 8 bit 아스키 (ASCII) 코드로 저장 시
  파일의 bit 수 = 8 x (파일의 문자 수)
  
  
• 가변 길이 코드
  • 허프만 압축
  • 파일에 빈번히 나타나는 문자에는 짧은 이진 코드를 할당하고, 드물게 나타나는 문자에는 긴 이진 코드를 할당
  • 허프만 압축 방법으로 변환시킨 문자 코드들 사이에는 접두부 특성 (prefix property) 존재
    • 각 문자에 할당된 이진 코드는 어떤 다른 문자에 할당된 이진 코드의 접두부 (prefix)가 되지 않는다는 것
    • a => 101, 다른 문자 코드 1, 10, 101로 시작되지 않음
    • 따라서 코드와 코드 사이를 구분할 특별한 코드가 필요 없음
  • 각 문자의 출현 빈도수 (문자가 파일에 나타나는 횟수)에 기반을 둔 이진트리를 만들어서, 각 문자에 이진 코드 할당

과정

1. 문자와 각 문자의 빈도수
   A: 450
   T: 90
   G: 120
   C: 270

2. 우선순위 큐 Q 생성
   

3. Q에서 ‘T’와 ‘G’를 제거한 후, 둘의 가중치를 더하여 새 노드를 만들고 새 노드를 부모 노드로 한다. 새 부모 노드를 다시 Q에 삽입한다.
   

4. Q에서 ‘T’와 ‘G’의 부모 노드와 ‘C’를 제거한 후, 둘의 가중치를 더하여 새 노드를 만들고 새 노드를 부모 노드로 한다. 새 부모 노드를 다시 Q에 삽입한다.
   

5. Q에서 ‘C’의 부모 노드와 ‘A’를 제거한 후, 둘의 가중치를 더하여 새 노드를 만들고 새 노드를 부모 노드로 한다. 새 부모 노드를 Q에 삽입한다.
   

6. Q에 있는 노드 수가 2개 미만이므로(1개), 루트로부터 왼쪽 자식 노드로 내려가면 ‘0’을, 오른쪽 자식 노드로 내려가면 ‘1’을 부여한다. 문자의 이진 코드를 구한다.
   

• 이진코드

  A: 0
  T: 100
  G: 101
  C: 11

  • 가장 빈도수가 높은 ‘A’가 가장 짧은 코드를 가지고, 따라서 루트의 자식이 되어 있고, 빈도수가 낮은 문자는 루트에서 멀리 떨어지게 되어 긴 코드를 가진다.

• 압축률

  • 압축된 파일의 bit 수
    (450x1)+(90x3)+(120x3)+(270x2) = 1,620 bit

  • 아스키 코드로 된 파일 크기
    (450+90+120+270)x8 = 7,440 bit

  • 파일 압축률
    (1,620/7,440)x100 = 21.8%이며, 원래의 약 1/5 크기로 압축됨

구현

가중치 그래프 G = (V, E)
정점의 수 |V| = n
간선의 수 |E| = e

출발 정점 s
s부터 v까지의 최단거리 저장 배열 D

• Pseudocode
  입력: n개의 문자에 대한 각각의 빈도수
  출력: 허프만 트리

HuffmanCoding()
  	
    각 문자 당 노드를 만들고, 그 문자의 빈도수를 노드에 저장;
	n개의 노드의 빈도수에 대해 우선순위 큐 Q 생성;
	
    while ( len(Q) ≥ 2 ) {//Q에 있는 노드 수가 2개 미만 될 때까지
		빈도수 가장 작은 2개 노드 Q에서 제거;
		새 노드 N 생성;
		A와 B를 N의 자식 노드로;
		N 빈도수 = A 빈도수 + B 빈도수;
		노드 N을 Q에 삽입;
    }
	
    return Q //허프만 트리의 루트

시간복잡도

• n개 노드 생성, 각 빈도수 노드에 저장: $O(n)$
• 우선순위 큐 생성: $O(n)$ => 힙 자료구조 사용 시
• while-Loop: $n-1$번
  • 최소 빈도수를 가진 노드 2개 Q에서 제거(힙 삭제 연산): $O(logn)$
  • 새 노드 Q에 삽입(힙 삽입 연산): $O(logn)$
• 루트 리턴: $O(1)$

$\therefore O(nlogn)$