[알고리즘] 욕심쟁이 알고리즘(최단 경로, 작업 스케줄링 문제, 작업 선택 문제, 허프만 코딩)

최단 경로

가중 방향 그래프에서 두 정점을 연결하는 경로 중에서 간선의 가중치의 합이 가장 작은 경로

플로이드 알고리즘 Floyd0	데이크스트라 알고리즘 Dijkstra
모든 정점 간의 경로	특정한 하나의 정점에서 다른 모든 정점으로의 최단 경로 (단일 출발점 최단 경로)
동적 프로그래밍 방법 적용	욕심쟁이 방법 적용
O(|V|^3)	O(|V|^2)
가중치의 합이 음수인 사이클이 없다고 가정	음의 가중치를 갖는 간선이 없다고 가정

데이크스트라 알고리즘

거리 d[v] : 출발점에서 현재까지 선택된 정점 집합 S를 경유하여 정점 v에 이르는 최소 경로의 길이

출발점에서 시작하여 거리 d[]가 최소인 정점을 차례로 선택하여 최단 경로를 구하는 방법

• 초기화 : 출발점 d[s]=0 . 나머지 모든 정점 v의 d[v]=무한대. 선택 정점 집합 S={}.
• 미선택 정점 집합 V-S에서 d[]가 가장작은 정점 u를 선택 -> u의 인접 정점에 대해서 u를 경유하는 거리와 기존 거리 중에서 작은 것을 새로운 거리값으로 조정

모든 정점들이 선택될 때까지 while 반복

가장 작은 d[a]를 선택하고 그 중 인접한 정점을 이을 때 가장 작은 가중치의 값을 해당 정점의 d[정점] 값으로 변경하게 된다.

a는 선택됐으므로 다음 정점을 선택하자면, 방금 변경된 값 중 가장 작은 값을 가진 d[정점]의 정점을 선택하게된다.

d[b]=1로 가장 작으므로 b를 선택한다. 그 다음 d[d]값이 4였는데, b와 인접한 정점인 d는 이전에 a에서 b로가는 가중치1과 b에서 d로 가는 가중치 2를 합해서 d[d]=3으로 변경된다. 그리고 인접한 정점들의 경우 방향을 가리키기 위해 a에서 가중치가 작은 b를 선택한다면 b에서 a로 향하는 점선 화살표를 그리게 되는데 그 다음 d를 선택했으므로 d에서 b로 향하는 점선 화살표를 그리게 된다. 

이러한 방법을 반복하여 최단경로를 찾을 수 있다.

 

음의 가중치를 갖는 간선이 없어야 함

 

작업 스케줄링 문제

가장 적은 개수의 기계를 사용해서 작업 간의 충돌이 발생하지 않도록 모든 작업을 기계에 할당하는 문제

작업의 집합 T={t1,t2,...,tn} , ti={si,fi_(1<=i<=n)

si:작업 시작 시간, fi:작업 완료 시간

 

작업 간의 충돌이 없어야 함

작업 간의 충돌 : 한 기계에서 두 개 이상의 작업이 동시에 수행되는 것

작업 i와 j가 충돌을 피하기 위한 조건 -> fi<=si or fi<=si

각 작업이 시작되면 중단없이 완료해야 함

 

각 단계에서 시작 시간이 빠른 작업을 우선 선택

충돌이 발생 안하면 -> 해당 기계에 배정

충돌 발생 -> 새로운 기계에 배정

 

시작시간이 빠른것 순서대로 정렬

작업시간이 겹치지 않도록 차례대로 기계에 배치

기계가 몇개 필요한가?

 

성능

작업을 시작 시간의 오름차순으로 정렬 O(nlogn)

충돌발생 확인 O(n), O(logn)

O(nlogn)

 

작업 선택 문제

하나의 기계만을 사용해서 충돌 없이 최대 개수의 작업을 기계에 할당하는 문제

작업의 집합 T = {t1, t2, ..., tn}, ti={si,fi) (1<=i<=n)

 

각 단계에서 완료시간이 빠른 작업을 우선 선택

충돌 발생안함 -> 기계에 배정

충돌 발생 -> 해당 작업을 버림

충돌 없이 하나의 기계에서 처리할 수 있는 작업의 갯수 구함

 

성능

정렬 O(nlogn)

충돌발생 확인 O(n)

O(nlogn)

 

허프만 코딩

허프만 코딩 != 욕심쟁이 방법

 

문자의 빈도 또는 확률 정보를 이용한 통계적 압축 방법

텍스트에서 각 문자가 출현하는 빈도수에 따라 다른 길이의 부호를 부여

출현 빈도수가 높은 문자 : 짧은 코드

출현 빈도수가 낮은 문자 : 긴 코드

 

ex) ababcdbad

저장 공간이 얼마나 필요한가?

8bit 아스키 코드로 표현하는 경우 -> 9문자 * 8bit = 72bit

고정 길이 변환 코드로 표현하는 경우  -> 9문자 * 2bit = 18bit

 (문자 집합={a,b,c,d} - a:00 b:01 c:10 d:11

단순히 빈도수에 따른 가변 길이 변환 코드로 표현하는 경우

 (빈도수 - a(3) b(3) c(1) d(2) -> a:'0' b:'1' c:'00' d:'01'  이를 이용하여 인코딩하면 010100011001 )

그런데 디코딩하려면 ... 모호성이 있다.

 

모호성 없이 디코딩하려면 접두부 코드 prefix code 이어야 함

각 문자에 부여된 이진 코드가 다른문자에 부여된 이진 코드의 접두부가 되지 않는 코드

a : '101' 이라면 1, 10, 101은 다른 문자들에게는 부여할 수 없다.

 

허프만 코딩

접두부 코드, 최적 코드(인코딩된 메시지의 길이가 가장 짧은 코드)

인코딩 과정

 1. 주어진 텍스트에서 각 문자의 출현 빈도수를 계산

 2. 각 문자의 빈도수를 이용하여 허프만 트리를 생성하여 각 문자에 이진 코드를 부여

 3. 주어진 텍스트의 각 문자를 이진 코드로 변환하여 압축된 텍스트를 생성

 

허프만 트리

허프만 코딩에서 각 문자에 이진 코드를 부여하기 위해서 상향식으로 만드는 이진 트리

허프만 트리 == 욕심쟁이 방법

리프 노드가 각 문자를 표시하는 전 이진트리

각 문자가 개별적인 트리인 상태에서 시작해서 빈도수가 작은 두 트리를 합쳐서 보다 큰 트리를 생성하는 과정을 반복

 각 노드는 비도수로 표시, 좌우의 두 간선은 각각 0, 1로 레이블됨, 합쳐지는 두 트리를 자식 노드로 갖는 부모 노드를 생성해서 만들어짐

 

빈도수 F[]에 따라 최소 힙 Q 생성; O(n)
for(i=0; i<n; i++) { O(n)
	u <- 힙 Q에서 최솟값 삭제; O(logn)
    v <- 힙 Q에서 최솟값 삭제;

O(nlogn) 허프만 트리

O(nlogn) + O(m)  허프만 트리 + 인코딩(텍스트의 길이만큼)

 

각 문자의 빈도수를 모르는 경우 -> 텍스트를 2번 읽어야 함 (빈도수를 계산할 때, 텍스트를 읽으면서 실제 인코딩할 때) -> 속도가 상당히 느림

압축된 데이터를 디코딩하려면 각 문자의 빈도수, 허프만 트리에 대한 정보, 문자 집합 정보가 필요, -> 데이터의 헤더에 필요한 정보를 제공 -> 실제 압축률 저하 초래