[알고리즘] Greedy Algorithm (탐욕 알고리즘)

출처: http://janghw.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Greedy-Algorithm-%ED%83%90%EC%9A%95-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

탐욕 알고리즘

정의 : 미리 정한 기준에 따라서 매번 가장 좋아 보이는 답을 선택하는 알고리즘

동적 계획법과 마찬가지로 최적화 문제를 푸는데 사용한다.

근시안적으로 해를 구할 당시에 가장 최적인 해를 구한다.

탐욕 알고리즘은 동적 계획법보다 효율적이긴 하지만 동적 계획법처럼 반드시 최적의 해를 구해준다는 보장을 하지 못한다.

알고리즘

1. 해 선택 (Selection Procedure) : 지금 당시에 가장 최적인 해를 구한뒤, 이를 부분해 집합에 추가한다.

2. 적절성 검사 (Feasibility Check) : 새로운 부분해 집합이 적절한지 검사한다.

3. 해 검사 (Solution Check) : 새로운 부분해 집합이 문제의 해가 되는지 검사한다. 아직 문제의 해가 완성되지 않았다면 1번부터 다시 시작한다.

탐욕 알고리즘의 활용

1. 최소수의 동전으로 거스름돈 거슬러주기

편의점같은 곳에서 돈을 거슬러 줄 때에는 서비스 차원에서 최소한의 동전 개수로 돈을 거슬러 주는 게 좋다. 거스름돈이 550원인데 50원짜리 동전을 11개 주면 받는 손님은 불쾌할 것이 분명하다. 이 문제의 해는 거슬러 줄 총액에 해당하는 동전의 집합이고, 최적해는 동전의 개수가 최소가 되는 집합이다.

알고리즘

1. 해 선택 (Selection Procedure) : 가장 가치가 높은 동전을 우선으로 거스름돈을 구성하면 동전의 개수가 줄어들테니, 현재 고를 수 있는 가장 가치가 높은 동전을 골라서 부분해 집합에 추가한다.

2. 적절성 검사 (Feasibility Check) : 부분해 집합이 거슬러 줄 금액을 초과하는지 검사한다. 초과한다면 가장 최근에 추가한 동전을 삭제하고, 1로 돌아가서 현재보다 한 단계 작은 동전을 추가한다.

3. 해 검사 (Solution Check) : 부분해 집합이 거슬러 줄 금액과 일치하는지 검사한다. 액수가 모자라면 다시 1로 돌아가서 부분해 집합에 추가한 동전을 고른다.

이렇게 만든 알고리즘은 꽤 쓸만해 보인다. 하지만 항상 최적의 해를 구해주는 것은 아니다. 대부분의 국가에서 사용하는 화폐들의 단위는 이 알고리즘이 항상 최적의 해를 구할 수 있도록 되어있다. 우리나라의 동전은 500원, 100원, 50원, 10원 이렇게 네가지가 있다. 이 중 아무것이나 두 개를 골라서 최대공약수를 구하면 항상 작은 값의 동전 단위가 나온다. 예를 들어 500과 50의 최대 공약수는 50이고, 100과 10의 최대 공약수는 10이다.

이런 시스템에서는 가장 최소수의 동전으로 이루어진 거스름돈을 만들기가 쉽다. 예를 들어 물건금액이 3,800원이고 손님이 5,000원을 지불했다면 500원짜리 두개와 100원짜리 두개를 거슬러 주면 된다. 이것은 위의 알고리즘으로도 같은 결과를 얻을 수 있다.

하지만 여기에 400원짜리 동전이 생긴다면 어떻게 될까. 400은 500과 최대공약수가 100으로 작은 값의 동전 단위가 나오지 않는다. 이 때 거스름돈을 1200원 거슬러 주어야 한다면 400원짜리 동전 3개를 거슬러 주는 것이 가장 최적의 방법이지만, 위의 알고리즘대로라면 500원짜리 2개와 100원짜리 2개를 거슬러주게 될 것이다. 이처럼 탐욕 알고리즘은 항상 최적의 결과를 보장하지는 못한다.

2. 최소비용 신장트리 (Minimum Spanning Trees)

정의 : 그래프 내의 모든 정점을 최소의 비용으로 연결하는 트리

다음과 같은 그래프가 있다고 하면

최소비용 신장트리는 다음과 같을 수 있다.

최소비용 신장트리를 만드는 알고리즘에는 프림 알고리즘, 크루스칼 알고리즘 크게 두가지가 있다. 일단은 크루스칼 알고리즘만 다뤄보기로 한다.

크루스칼 알고리즘

1. 그래프 내의 모든 간선을 가중치의 오름차순으로 목록을 만든다.

2. 1에서 만든 간선의 목록을 차례대로 순회하면서 간선을 최소비용 신장트리에 추가한다. 단, 이때 추가된 간선으로 인해 트리구조가 망가지면 안된다.

탐욕적인 방법으로 처리되는 부분은 2단계이다.

이 부분에서 '해 선택 - 적설성 검사 - 해 검사'의 반복이 이루어진다.

해 검사는 부분해 집합이 하나가 되면 최적해로 판단한다.

위의 그래프로 간선의 가중치의 오름차순 목록을 만들면

C-E(1), A-C(2), E-F(2), B-D(3), C-F(3), D-E(3), D-G(3), A-B(4), B- C(4), F-G(6), A-E(8) 이다.

그리고 먼저 C-E(1)를 추가한다.

트리 구조가 망가지진 않았으니 계속한다.

파란원으로 묶은 정점들과 묶지 않은 개별 정점 하나하나는 부분해 집합들이다.

부분해 집합이 하나가 아니므로 반복한다.

그다음 A-C(2)와 E-F(2)를 추가한다.

트리 구조가 망가지진 않았으니 계속한다.

부분해 집합이 하나가 아니므로 반복한다.

B-D(3), C-F(3), D-E(3), D-G(3)를 추가한다.

C-F(3)은 사이클을 형성하여 트리 구조를 망가뜨리니 삭제한다.

부분해 집합이 하나이므로 종료한다.

3. 다익스트라 알고리즘 (Dijkstra's Algorithm)

정의 : 그래프 내의 한 정점에서 다른 정점으로 가는 최단 경로를 구하는 알고리즘

예를 들면 다음과 같은 그래프가 있다고 하면 최소한의 비용으로 A에서 G까지 가는 방법을 찾는 것이다.

알고리즘

1. 각 정점 위에 시작점으로부터 자신에게 이르는 경로의 길이를 저장할 곳을 정의하고 모든 정점 위에 있는 경로의 길이를 (무한대)로 초기화한다.

2. 시작 정점의 길이를 0으로 초기화하고 최단 경로에 추가한다.

3. 최단 경로에 새로 추가된 정점의 인접 정점들에 대해 경로 길이를 갱신하고 이들을 최단 경로에 추가한다. 만약 추가하려는 인접 정점이 이미 최단 경로위에 있는 정점이라면 갱신할려는 경로의 길이가 더 짧은 경우에만 기존의 경로를 현재 정점을 경유하게 수정한다.

4. 그래프 내의 모든 정점이 최단 경로에 속할 때까지 3을 반복한다.

탐욕 알고리즘으로 이 알고리즘을 보면 1, 2 단계가 알고리즘의 초기화 단계이고, 3단계는 해 선택과 적절성 검사, 4단계는 해 검사를 맡고있다.

먼저 각 정점에 시작점으로부터 자신에게 이르는 경로의 길이를 저장할 곳을 정의하고 모든 정점 위에 있는 경로의 길이를 (무한대)로 초기화한다.

A를 시작 정점이라고 하고 경로 길이를 0으로 초기화하고 최단 경로에 추가한다.

현재 새로 추가한 정점은 A이므로 정점 A에 인접한 정점인 정점 B, C, F를 최단 경로에 추가하고, 각 정점에 이르는 데 드는 비용을 갱신한다.

이미 최단 경로 안에 들어 있는 정점들은 없으므로 적절성 검사는 통과한다. 아직 최단 경로가 완성되진 않았으므로 4의 해 검사는 통과하지 못하므로 3을 반복한다.

새로 추가한 정점이 정점 B, F, C 세가지 이므로 차례차례대로 3을 수행한다.

먼저 B에 대해서 3을 수행한다. 인접 정점은 E 하나 뿐이므로, E를 최단 경로에 추가하고 경로의 길이를 갱신한다. 

적절성 검사는 통과하고, 해 검사는 통과하지 못하므로, 계속해서 C에 대해서 처리한다.

C의 인접 정점은 정점 D, F, G가 있는데 D와 G는 경로 길이가 무한대이므로 적절성 검사를 통과하지만, F는 이미 최단 경로 안에 포함되어 있고, 새로 추가할려는 경로보다 짧으므로 적절성 검사를 통과하지 못한다. 그리고 모든 정점이 최단 경로에 속하므로 해 검사를 통과한다.

하지만 이 해는 최적해가 아니다. A에서 E에 이르는 거리는 B를 거쳐 E로 가는 것보다 F를 거쳐 E로 가는게 더 짧다. 이처럼 탐욕 알고리즘은 항상 최적해를 보장하지 못한다.

하지만 이 알고리즘은 조금 더 개선하여 그래프에 사이클이 존재하지 않는 이상 무조건 최적해를 나오게 할 수 있다. 탐욕 알고리즘의 이점인 실행시간을 조금 포기해야한다.

알고리즘

1. 시작 정점에서 도달가능한 정점들에 대해 경로의 길이를 설정하고, 나머지 정점들까지의 거리는 로 초기화한다.

2. 제일 가까운 경로의 정점을 하나 선택한다.

3. 시작점에서 출발하여 결정된 최단거리 정점들을 제외한 모든 정점들을 경유하여 선택한 점까지 도달하는 거리를 체크한다. 기존의 경로보다 짧을 경우 기존의 경로를 갱신한다.

4. 2~3을 n-1번 반복한다.

같은 그래프에 대해서 다시 이 알고리즘을 수행해보자.

시작 정점에서 도달가능한 정점에 대해 경로의 길이를 설정하고, 나머지 정점들에 대한 거리는 로 초기화 하였다.

B에서 제일 가까운 정점인 E를 선택한다.

E까지 도달 가능한 경로는 A-B-E와 A-F-E이다. A-F-E경로가 더 짧으므로 해당 경로를 선택한다.

B에서 더 이상 선택가능한 정점이 없으므로 다음 정점인 C에서 제일 가까운 점인 D를 선택한다.

D까지 도달 가능한 경로 중 제일 짧은 거리를 선택한다.

A에서 C를 거쳐 F까지 다다르는 거리와 A에서 F로 바로 가는 경로의 길이를 비교하고, 원래 경로가 짧으므로 갱신하지 않는다.

A에서 C를 거쳐 G까지 다다르는 거리와 A에서 G로 바로 가는 경로의 길이를 비교하고, A에서 C를 거쳐 G로 가는 경로의 길이가 짧으므로 경로를 갱신한다.

나머지 정점들에 대해서 계속 진행해주어도 갱신되는 점 없이 이렇게 결정될 것이다.

방금과 달리 최적해가 나왔다.

사이클이 없는 경우 최적해를 보장하지만 이 알고리즘은 무조건 의 시간 복잡도를 가진다.

4. 허프만 코딩 (Huffman Coding)

정의 : 데이터를 압축하는 방법중의 하나로 쓰이는 알고리즘

허프만 코딩을 알기 위해서는 먼저 고정 길이 코드와 접두어 코드를 알아야 한다.

고정 길이 코드(Fixed Length Code)란 말 그대로 모든 코드의 길이가 똑같은 코드의 체계를 말한다. ASCII가 그 대표적인 예로, 모든 코드가 8bit의 길이를 가진다. 코드의 길이가 같으므로 다루기가 쉽지만 쓰지 않는 공간이 생기기 때문에 저장 공간의 낭비가 일어난다. 이를 위해 쓰는 것이 가변 길이 코드(Variable Length Code)이다. 접두어 코드(Prefix Code)는 이 가변 길이 코드의 한 종류이다.

접두어 코드란 코드 집합의 어느 한 코드도 다른 코드의 접두어가 되지 않는 코드를 말한다.예를 들어 {"0", "1", 01", "11"}은 접두어 코드가 아니다. "0"이 "01"의 접두어가 되고, "1"이 "11"의 접두어가 되기 때문이다. {"00", "01", "11", "101"}은 어느 코드도 다른 코드의 접두어가 되지 않기 때문에 접두어 코드이다.

ASCII와 같은 고정 길이 코드로 이루어진 데이터를 접두어 코드로 변환시켜 데이터를 압축시키는 메커니즘이 바로 허프만 코딩인것이다.

허프만 코딩에서 제일 중요한 요소는 기호의 빈도와 이진 트리이다.

기호의 빈도란 한 기호가 데이터 안에서 얼마나 자주 나오느냐이다. 기호의 빈도는 길이가 짧은 접두어 코드를 빈도가 높은 기호에 부여하기 위해 사용된다. 이렇게 함으로써 그만큼 저장공간을 아낄 수 있다. 예를 들어 어떤 문자열이 'x' 15개와 'y' 4개로 이루어진다고 하고,  'x'라는 코드에 111을, 'y'에 코드 10을 부여한다면, 변환된 데이터의 크기는 3(111의 비트 길이) X 15 + 2(10의 비트 길이) X 4 = 53비트가 된다. 하지만 이와 반대로 'x'에 10을, 'y'에 111을 부여한다면 2(111의 비트 길이) X 15 + 3(10의 비트 길이) X 4 = 42비트가 되어 앞의 방법보다 비트를 절약할 수 있다.

이진 트리는 접두어 코드를 표현하는데 사용된다. 트리의 왼쪽 자식 노드는 0, 오른쪽 자식 노드는 1을 나타낸다. 모든 기호는 잎 노드에만 저장된다. 루트 노드에서 잎 노드까지 이르는 경로가 기호의 접두어 코드가 된다. 이런 방식으로 작성된 이진 트리를 허프만 트리라고 한다. 다음이 그 예이다.

a까지의 경로는 0이고 이것이 a의 접두어 코드가 된다. b까지의 경로는 10이고 이것이 b의 접두어 코드가 된다. c까지의 경로는 11이고 이것이 접두어 코드가 된다.

이러한 원리로 허프만 코딩을 적용시켜보자. 'aabaabbccde'라는 문자열을 압축시켜보자. a의 빈도는 4이고 b의 빈도는 3이고 c는 2, d는 1, e는 1이다. 먼저 기호들을 빈도와 함께 노드를 생성한다.

노드 위의 숫자는 빈도를 나타낸다.

이 노드들은 끝까지 잎 노드로 남아야 함으로 노드들 위에 부모 노드를 생성해 나가면서 이어붙인다.

우선 가장 빈도가 작은 노드 두 개를 선택한다. d, e가 둘 다 빈도가 1이므로 d, e를 선택하고 이 노드들 위에 부모노드를 하나 만들어서 연결한다. 부모 노드의 빈도는 자식 노드의 빈도들의 합인 2가 된다.

모든 잎 노드들이 기호를 가지고 있으므로 적절성 검사는 통과하지만, 허프만 트리가 완성되지는 않았으므로 해 검사는 통과하지 못한다. 그러므로 다시 해 선택으로 돌아간다.

c와 새로 만든 노드(d와 e의 부모 노드)의 빈도가 가장 작으므로 이 두 노드 사이에 부모 노드를 새로 만든다.

적절성 검사는 통과하고, 해 검사는 통과하지 못하므로 다시 해 선택으로 돌아간다.

제일 같은 빈도가 b와 새로 만든 노드이므로 이 두 노드 사이에 부모 노드를 새로 만든다.

적절성 검사는 통과하고, 해 검사는 통과하지 못하므로 다시 해 선택으로 돌아간다.

제일 같은 빈도가 a와 새로 만든 노드이므로 이 두 노드 사이에 부모 노드를 새로 만든다.

적절성 검사를 통과하고, 허프만 트리가 완성되었으므로 해 검사도 통과한다.

이제 이 허프만 트리의 접두어 코드로 데이터를 표현하면 데이터가 압축되는 것이다.

a	a	b	a	a	b	b	c	c	d	e
0	0	10	0	0	10	10	110	110	1110	1111

압축 결과는 00100010101101101110111이다. ASCII로 표현하였을때는 88비트이겠지만, 23비트로 압축되었다.

압축을 했으면 압축을 해제하는 방법도 있어야한다.

알고리즘

1. 압축을 위해 만들었던 허프만 트리와, 압축 해제가 된 데이터를 담을 부분을 준비한다.

2. 압축 데이터에 아직 읽지 않은 부분이 있으면 한 비트 읽는다.

3. 읽은 비트가 0이면 왼쪽 자식 노드로, 1이면 오른쪽 자식 노드로 이동한다. 잎 노드에 다다르면 노드에 있는 기호를 데이터에 담고 다시 루트 노드로 이동한다.

앞에서 압축한 00100010101101101110111를 압축 해제 해보겠다.

데이터를 한 비트 읽는다. 0이 나왔으므로 왼쪽 자식 노드로 이동한다. 잎 노드 a가 나왔으니, a를 압축 해제된 데이터에 추가하고 루트 노드로 돌아간다.

그 다음 비트를 읽으니 또 0이 나왔으므로  왼쪽 자식 노드로 이동한다. 잎 노드 a가 나왔으니, a를 압축 해제된 데이터에 추가하고 루트 노드로 돌아간다.

그 다음 비트를 읽으면 1이 나온다. 오른쪽 자식 노드로 이동했는데 잎 노드가 아니므로 그 다음비트를 읽는다. 0이 나왔으므로 왼쪽 자식 노드로 이동한다. 잎 노드 b가 나왔으므로, b를 압축 해제된 데이터에 추가하고 루트 노드로 돌아간다.

같은 방법으로 계속 반복하다보면 데이터를 끝까지 읽고 압축이 완전히 해제된 데이터를 볼 수 있다.

압축 해제된 데이터는 'aabaabbccde'로 압축한 데이터와 같은 문자열을 얻었다.