[자료구조] Chapter 14 탐욕 알고리즘

탐욕 알고리즘의 개요

탐욕 알고리즘은 최적화된 문제의 답을 얻기 위해 사용된다. 아래와 같은 과정으로 동작한다.

1. 해 선택: 현재 상태에서 부분 문제의 최적해를 구한 후 이를 부분 집합에 추가한다.
2. 실행 가능성 검사: 새로운 부분해 집합이 실행 가능한 것인지 확인한다. 다시 말해, 문제의 제약 조건을 위반하지 않는지를 검사하는 것이다.
3. 해 검사: 새로운 부분해 집합이 문제의 해가 되는지 확인한다. 아직 전체 문제의 해가 완성되지 않는다면 1의 해 선택부터 다시 한다.

 

거스름돈 줄이기 문제

“어떻게 하면 손님에게 거스름돈으로 주는 지폐와 동전의 개수를 최소한으로 줄일 수 있을까?”

1. 해 선택: 가장 좋은 해를 선택하면 된다. 단위가 큰 동전으로만 거스름돈을 만들면 동전의 개수를 줄일 수 있다. 현재 고를 수 있는 가장 큰 단위의 동전을 골라 거스름돈에 추가한다.
2. 실행 가능성 검사: 거스름돈이 손님에게 줘야 할 액수를 추가하는지 확인한다. 초과하면 마지막에 추가한 동전을 거스름돈에서 빼고 단계 1로 돌아가 현재보다 한 단계 작은 단위의 동전을 추가한다.
3. 거스름돈 문제의 해를 구성하는 동전은 손님에게 줘야 할 액수와 같아야 한다. 거스름 돈 액수가 모자라면 1로 돌아가서 추가할 동전을 고른다.

 

크루스칼 알고리즘 다시 보기

그래프 내의 모든 정점을 최소 비용으로 연결하는 트리를 최소 신장트리라고 한다. 최소 신장 트리를 구축할 때 중요한 점은 최소 신장 트리 내에 사이클이 형성되서는 안된다는 것이다.
 
크루스칼 알고리즘은 2단계로 동작한다.

1. 그래프 내의 모든 간선을 가중치의 오름차순으로 정렬하여 목록을 만든다.
2. 1단계에서 만든 간선의 목록을 차례대로 순회하며 간선을 최소 신장 트리에 추가한다. 이때 추가된 간선으로 인해 최소 신장 트리 내에 사이클이 형성되면 안 된다.

크루스칼 알고리즘에서 탐욕적인 방법으로 처리되는 부분은 2단계이다. 탐욕 알고리즘은 해 선택 → 실행 가능성 검사 → 해 검사의 반복으로 이루어지는데. 해당 부분이 크루스칼 알고리즘에서 간선의 목록을 돌며 최소 신장 트리를 완성하는 것이다. 해 선택은 가장 작은 가중치의 간선을 택함으로써 이루어지며, 정렬은 이미 끝났기에 차례대로 선택하기만 하면 된다.
 
크루스칼 알고리즘에서 중요한 것은 실행가능성이다. 해 선택 단계에서 고른 간선이 신장 트리 내에 사이클을 형성한다면 이 간선을 버리고 다음 가중치의 간선을 골라야 한다. 크루스칼 알고리즘은 사이클 탐지를 위해 분리집합을 이용한다. 크루스칼 알고리즘은 간선을 추가할 때마다 간선 양 끝에 있는 정점들을 같은 집합에 추가하는데, 2개의 정점이 이미 같은 집합에 속해있다면 해당 간선이 사이클을 형성한다고 판단한다.

 

데이크스트라 알고리즘 다시 보기

데이크스트라 알고리즘은 그래프 내의 한 정점에서 다른 정점으로 향하는 가장 짧은 경로를 구하는 알고리즘이다.
데이크스트라 알고리즘은 다음과 같이 동작한다.
 

1. 각 정점에는 시작점으로부터 자신에게 이르는 경로의 길이를 저장할 곳을 준비하고 각 정점에 대한 경로의 길이를 무한대로 초기화한다.
2. 시작 정점의 경로 길이를 0으로 초기화하고 최단 경로에 추가한다.
3. 최단 경로에 새로 추가된 정접의 인접 정점에 대해 경로 길이를 갱신하고 이들을 최단 경로에 추가한다. 만약 추가하려는 인접 정점이 이미 최단 경로 안에 있다면 갱신되기 이전의 경로 길이가 새로운 경로의 길이보다 더 큰 경우에 한해 다른 선행 정점을 지니던 기존 경로가 현재 정점을 경유하게 수정한다.
4. 그래프 내의 모든 정점이 최단 경로에 소속될 때까지 단계 3의 과정을 반복한다.

 

허프만 코딩

음악 저장 파일 포맷인 mp3와 이미지 저장 파일 포맷인 JPEG의 공통점은 무엇일까?
바로! 허프만 코딩을 이용하는 압축 데이터 포맷이라는 점이다.

 

1) 고정 길이 코드와 접두어 코드

고정 길이 코드는 말 그대로 모든 코드의 길이가 같은 값을 갖는 코드 체계를 의미한다. 아스키코드가 대표적이다. 고정 길이 코드의 최대 장점은 다루기 쉽다는 것이다. 아스키로 문자열을 표현하고 싶다면 8비트 길이의 데이터를 연속해서 이어 붙이면 되고 반대로 문자열의 각 요소를 알고 싶다면 8비트 단위로 끊어 읽으면 된다.
 
고정 길이 코드가 이처럼 연산의 편의를 위한 것이라면 가변 길이 코드는 저장 공간 절약을 위해 사용된다. 가변 길이 코드는 저장 공간을 절약한다는 장점도 있지만 데이터 처리가 상당히 번거롭다는 단점도 있다. 접두어 코드는 가변 길이 코드의 한 종류이다. 접두어 코드는 코드 집합의 어느 코드도 다른 코드의 접두어가 되지 않는 코드를 의미한다.

 

2) 허프만 트리 구축

허프만 코딩을 이해하기 위해서는 기호의 빈도와 이진트리만 기억하면 된다.
기호의 빈도는 길이가 짧은 접두어 코드를 빈도가 높은 기호에 부여하기 위해 사용한다. 빈도가 높은 기호에 작은 접두어 코드를 부여하면 그만큼 저장 공간을 아낄 수 있기 때문이다. 압출률이 높아진다는 의미이다.
 
이진트리는 접두어 코드를 표현하기 위해 사용된다. 트리의 노드에서 왼쪽 자식 노드는 0, 오른쪽 자식 노드는 1을 의미한다. 이 트리에서 모든 기호는 잎 노드에만 기록되어 있으며 뿌리 노드에서부터 잎 노드까지 이르는 경로가 기호의 접두어 코드가 된다. 이러한 방식으로 접두어 코드를 표현하는 이진트리를 허프만 트리라고 한다.
 

뿌리 노드에서 잎 노드에 이르는 경로가 길어지면 길어질수록 접두어 코드 역시 길어진다. 앞에서 이야기한 기호의 빈도는 기호를 어느 잎 노드에 입력할 것인가를 결정하기 위해 사용된다. 빈도가 높은 기호일수록 경로를 짧게, 빈도가 늦은 기호일수록 경로를 길게 가져가야 압축률이 높아진다.

 

3) 데이터 압축 / 압축 해제

문자열의 각 요소를 차례대로 읽으며 호프만 트리가 나타내는 해당 문자의 접두어 코드로 변환하면 압축된다.
압축을 풀어내는 방법은 아래와 같다.

1. 우선 압축을 위해 만들었던 허프만 트리와 압축 해제된 데이터가 담길 버퍼를 준비한다. 여기서는 허프만 트리의 뿌리 노드로부터 시작해서 잎 노드까지 순회한다.
2. 압축 데이터에 아직 읽지 않는 부분이 남아있다면 데이터를 한 비트 읽는다.
3. 읽어낸 비트가 0이면 현재 노드의 왼쪽 자식 노드, 1이면 오른쪽 자식 노드로 이동한다. 현재 노드가 잎 노드면 버퍼에 저장된 기호를 추가하고 다시 뿌리 노드로 이동한다.