그리디 알고리즘은 최적화 문제를 해결하는 알고리즘이다. 그리디 알고리즘은 입력 데이터 간의 관계를 고려하지 않고, 수행 과정에서 최소값 또는 최대값을 가진 데이터를 선택한다.
최적화(optimization) 문제: 가능한 해들 중에서 최대 또는 최소의 해를 찾는 문제
이러한 선택은 '근시안적'인 선택이라고도 부른다. 근시안적으로 부분적인 최적해를 찾고, 이들을 모아서 문제의 최적해를 얻기 때문이다. 그리디 알고리즘은 한 번 선택하면 이를 번복하지 않으므로, 매우 단순하다. 아래의 동전 거스름돈 구하기 알고리즘은 아주 간단한 그리디 알고리즘에 해당한다고 할 수 있다.
동전 거스름돈
물건을 사고 거스름돈을 동전으로 받아야 한다. 최소 동전의 수로 거슬러 받을 때, 500원, 100원, 50원, 10원, 1원 동전의 개수를 각각 구하라.
남은 거스름돈 액수를 넘지 않는 한도에서, 가장 큰 액면의 동전을 계속하여 선택하는 알고리즘으로, 이러한 종류의 알고리즘을 그리디(Greedy) 알고리즘이라고 한다.
#include<stdio.h>
#include<stdlib.h>
void CoinChange(int money, int* change);
int main() {
int* change = malloc(sizeof(int) * 5); // 500원, 100원, 50원, 10원, 1원 동전 개수 배열
int money;
printf("거스름돈 액수: ");
scanf_s("%d", &money);
CoinChange(money, change);
free(change);
}
// 거스름돈을 가장 적은 수의 동전으로 바꿔주는 함수
void CoinChange(int money, int * change) {
int Money = money;
for(int i=0; i<5; i++)
change[i] = 0; // 배열 초기화
while(Money >= 500){ // 가장 큰 액면의 동전 개수부터 차례로 선택
change = change - 500;
change[0]++;
}
while(Money >= 100){
change = change - 100;
change[1]++;
}
while(Money >= 50){
change = change - 50;
change[2]++;
}
while(Money >= 10){
change = change - 10;
change[3]++;
}
while(Money >= 1){
change = change - 1;
change[4]++;
}
printf("500원 동전 %d개, 100원 동전 %d개, 50원 동전 %d개, 10원 동전 %d개, 1원 동전 %d개", change[0], change[1], change[2], change[3], change[4]);
}500원 동전을 처리할 때는 다른 동전을 몇개씩 거슬러 주어야 할 것인지에 대해선 전혀 고려하지 않는다. 이러한 부분에서 그리디 알고리즘의 근시안적인 특성을 엿볼 수 있다.
최소 신장 트리 (Minimum Spanning Tree)
주어진 그래프의 최소 신장 트리를 찾아라.
신장 트리란 사이클이 없도록 모든 점들을 연결시킨 트리를 말하며, 최소 신장 트리란 주어진 가중치 그래프에서 신장 트리들 중 간선들의 가중치 합이 최소인 트리를 말한다.
그래프의 정점 수가 n개일 때, 신장 트리에는 정확히 (n-1)개의 간선이 있다.
최소 신장 트리 알고리즘에서 쓰이는 그래프 자료구조에 대해 먼저 알아보자.
그래프 자료구조
#include <stdio.h>
#include <stdlib.h>
/*간선 구조체*/
typedef struct Edge
{
char v1, v2; // 시작 정점과 끝 정점 이름
int weight; // 가중치
struct Edge* next; // 그래프의 간선 리스트에서 다음 간선을 가리키는 포인터
}Edge;
/* 정점 aName에 부착된 간선을 표현하는 간선 구조체 */
typedef struct IncidentEdge
{
char aName; // 정점 이름
Edge* e; // 부착된 간선
struct IncidentEdge* next; // 정점 aName의 부착 간선 리스트에서 다음 간선을 가리키는 포인터
}IncidentEdge;
/*정점 구조체*/
typedef struct Vertex
{
char vName; // 정점 이름
IncidentEdge* iHead; // 정점 vName의 부착 간선 리스트의 헤더 간선 포인터
struct Vertex* next; // 그래프의 정점 리스트에서 다음 정점을 가리키는 포인터
}Vertex;
/*그래프 구조체*/
typedef struct
{
Vertex* vHead; // 정점 리스트의 헤드 정점 포인터
Edge* eHead; // 간선 리스트의 헤드 간선 포인터
int eCount, vCount; // eCount: 간선 개수 m, vCount: 정점 개수 n
}Graph;
/* 그래프 초기화 함수*/
void init(Graph* G)
{
G->vHead = NULL;
G->eHead = NULL;
G->vCount = G->eCount = 0;
}
/*새로운 정점 추가 함수*/
void makeVertex(Graph* G, char vName)
{
Vertex* v = (Vertex*)malloc(sizeof(Vertex)); // 새로운 정점에 동적 메모리 할당
v->vName = vName; // 새로운 정점의 이름 저장
v->iHead = NULL;
v->next = NULL;
G->vCount++; // 그래프 정점 개수 +1
Vertex* q = G->vHead; // q에 그래프의 정점 리스트 헤더 정점 포인터 저장
if (q == NULL)
G->vHead = v;
else
{
while (q->next != NULL)
q = q->next;
q->next = v; // 그래프의 정점 리스트에 새로운 정점 추가
}
}
/*정점 v에 부착된 간선 리스트에 간선을 추가하는 함수*/
void makeIncidentEdge(Vertex* v, char aName, Edge* e)
{
IncidentEdge* p = (IncidentEdge*)malloc(sizeof(IncidentEdge)); // 새로운 간선에 동적 메모리 할당
p->aName = aName; // 정점 v의 이름 저장
p->e = e; // 간선 저장
p->next = NULL;
IncidentEdge* q = v->iHead; // q에 v의 부착 간선 리스트의 헤더 간선 저장
if (q == NULL)
v->iHead = p;
else
{
while (q->next != NULL)
q = q->next;
q->next = p; // v의 부착 간선 리스트에 새로운 간선 추가
}
}
/*정점 탐색 함수*/
Vertex* findVertex(Graph* G, char vName)
{
Vertex* v = G->vHead; // v에 그래프의 정점 리스트 헤더 정점 저장
while (v->vName != vName)
v = v->next;
return v; // 정점 이름이 vName인 정점 리턴
}
/*간선 추가 함수*/
void insertEdge(Graph* G, char v1, char v2, int w)
{
Edge* e = (Edge*)malloc(sizeof(Edge)); // 새로운 간선에 동적 메모리 할당
e->weight = w; // 가중치 저장
e->v1 = v1; // 시작 정점 저장
e->v2 = v2; // 끝 정점 저장
e->next = NULL;
G->eCount++; // 그래프의 간선 개수 +1
Edge* q = G->eHead;
if (q == NULL)
G->eHead = e;
else
{
while (q->next != NULL)
q = q->next;
q->next = e; // 간선 리스트에 새로운 간선 추가
}
Vertex* v = findVertex(G, v1);
makeIncidentEdge(v, v1, e); // 새로운 간선을 v1 정점의 부착 간선 리스트에 추가
v = findVertex(G, v2);
makeIncidentEdge(v, v2, e); // 새로운 간선을 v2 정점의 부착 간선 리스트에 추가
}
/*그래프 출력 함수*/
void print(Graph* G)
{
Vertex* p;
IncidentEdge* q;
for (p = G->vHead; p != NULL; p = p->next)
{
printf("[%c] : ", p->vName); // 정점 이름 출력
for (q = p->iHead; q != NULL; q = q->next)
printf("[%c, %d] ", q->aName, q->e->weight); // 정점 p의 부착 간선 리스트를 순회하며 부착된 간선 정보 출력
printf("\n");
}
printf("\n");
}
Edge partition(Edge* e[], int left, int right){
Edge pivot = e[left];
int temp;
int low=left, high=right+1;
do{
do{
low++;
}while(e[low] < pivot);
do{
high--;
}while(e[high] > pivot):
if(low<high){
temp = e[low];
e[low] = e[high];
e[high] = temp;
}
}while(low < high);
temp = e[left];
e[left] = e[high];
e[high] = temp;
return high;
}
void quickSort(Edge* e[], int left, int right){
if(left<right){
int p = partition(e, left, right);
quickSort(e, left, p-1);
quickSort(e, p+1, right);
}
}
/*가중치 오름차순 퀵정렬 함수 (e[]에 정렬된 간선 배열이 저장됨)*/
void incSort(Graph* G, Edge* e[])
{
Edge* p = G->eHead;
for(i = 0; i < G->eCount; i++)
{
e[i] = p;
p = p->next;
}
quickSort(e, 0, G->eCount-1);
}(1) 크루시칼(Kruskal) 알고리즘
가중치가 가장 작은 간선이 사이클을 만들지 않을 때에만 욕심내어 그 간선을 추가시킨다.
크루시칼(kruskal) 알고리즘을 의사코드(pseudo code)로 정리하면 아래와 같다.
KruskalMST(G)
입력: 가중치 그래프 G=(V, E) (단, |V|=n, |E|=m, V: vertex 정점, E: edge 간선)
출력: 최소 신장 트리 T
1. 가중치의 오름차순으로 간선들을 정렬: L = 정렬된 간선 리스트
2. T를 초기화
3. while(T의 간선 수 < n-1) {
L에서 가장 작은 가중치를 가진 간선 e를 가져오고, e를 L에서 제거
if(간선 e가 T에 추가되어 사이클을 만들지 않으면) e를 T에 추가
else e를 버린다.
}
4. return T 이를 코드로 작성하면 아래와 같다.
/*사이클 체크 함수*/
int vFind(int v[], int vNum)
{
if(v[vNum] == -1)
return vNum;
while(v[vNum] != -1)
vNum = v[vNum];
return vNum;
}
void vUnion(int v[], int vNum1, int vNum2)
{
int r1 = vFind(v, vNum1);
int r2 = vFind(v, vNum2);
if(r1 != r2)
v[r2] = r1;
}
/* v에 사이클 시작 정점 저장. (Ex) v[2]=0이면 'c'->'a'로 연결된 것.
만약 v1-97=0, v2-97=2이고 vNum1=0, vNum2=0이면 'c'->'a'로 가는 path가 존재하는 것이므로
간선 'a'-'c'는 최소 신장 트리에 추가하지 않는다. (추가할 경우 사이클이 발생한다.)*/
void kruskal(Graph* G, Edge* e[], int v[])
{
int eCnt = 0, i = 0;
int vNum1, vNum2;
Edge* p;
while(eCnt < G->eCount - 1) // 그래프의 간선 리스트 순회
{
p = e[i]; // 가장 작은 가중치를 가진 간선을 p에 저장
vNum1 = vFind(v, p->v1 - 97); // 97은 소문자 'a'. 따라서 v1-97의 값은 0부터 시작한다.
vNum2 = vFind(v, p->v2 - 97);
if(vNum1 != vNum2) // 간선 p가 추가되어 사이클을 만들지 않으면
{
printf("%d. [%c%c (%d)]\n", eCnt+1, p->v1, p->v2, p->weight);
eCnt++; // 최소 신장 트리의 간선 개수
vUnion(v, vNum1, vNum2);
}
i++;
}
}퀵정렬을 이용하여 간선을 정렬하는데 간선의 개수 m에 대하여 O(mlogm) 시간이 걸리고, while-루프는 최대 m번 수행되며 while-루프 내에서 사이클 여부를 체크하는데 거의 O(1) 시간이 걸리므로, 시간복잡도는 O(mlogm)이다.
(2) 프림(Prim) 알고리즘
임의의 점 하나를 선택한 후, 트리 T 내부의 점들과 T 외부의 점들을 연결하는 간선들 중에서 최소 가중치를 가진 간선을 구하고, 해당 간선과 연결된 외부의 점을 T에 추가한다. 항상 T 밖에 있는 점을 추가하므로 사이클이 만들어지지 않는다.
프림(Prim) 알고리즘을 의사코드(pseudo code)로 정리하면 아래와 같다.
PrimMST(G)
입력: 가중치 그래프 G=(V, E) (단, |V|=n, |E|=m, V: vertex 정점, E: edge 간선)
출력: 최소 신장 트리 T
1. G에서 임의의 점 p를 시작점으로 선택. D[p]=0
/* D배열: T에 속한 점과 연결된 간선들 중 가중치가 가장 작은 간선의 가중치를 저장.
D[v]엔 T에 속한 점과 점v 사이의 간선들 중 가중치가 가장 작은 간선의 가중치를 저장. */
2. for(점 p가 아닌 점 v에 대하여){ // D배열 초기화
if(간선 (p,v)가 그래프에 있으면)
D[v] = 간선(p,v)의 가중치
else
D[v]= ∞
}
3. T={p} // 초기 트리 T에 점 p 추가
4. while(T에 있는 점의 수 < n){ // n은 그래프 정점의 개수
T에 속하지 않은 각 점 v에 대하여, D[v]가 최소인 점 Vmin과 연결된 간선을 T에 추가.
for(T에 속하지 않은 각 점 w에 대하여){
if(간선(Vmin, w)의 가중치 <D[w])
D[w] = 간선 (Vmin, w)의 가중치 //D[w]를 갱신
}
}
5. return T코드로 작성하면 아래와 같다.
#define FALSE 0
#define TRUE 1
char getMinVertex(Graph* G, int D[]){
Vertex* p;
char vName;
for(p=G->vHead; p !=NULL; p=p->next){ // 그래프의 정점 리스트 순회
if(p->isVisit==FALSE){ // 정점이 최소신장트리 T에 속하지 않았다면
vName = p->vName; // 정점의 이름 저장
break;
}
}
for(p=G->vHead; p!=NULL; p=p->next)
if(p->isVisit==FALSE && (D[p->vName-97] < D[vName-97])) // 정점 vName보다 정점 p의 가중치가 더 작으면
vName = p->vName; // vName에 가중치가 가장 작은 정점의 이름 저장
return vName;
}
void prim(Graph* G, char vName, int D[]){
Vertex* p = findVertex(G, vName);
IncidentEdge* q;
char c;
D[p->vName-97]=0; // 정점 vName을 시작점으로 선택
for(int i=0; i<G->vCount-1; i++){ // 그래프의 정점 리스트 순회
c = getMinVertex(G, D);
p = findVertex(G, c); // 정점 이름이 c인 정점을 p에 저장
p->isVisit = TRUE;
printf("(%c) ", p->vName);
for(q = p->iHead; q!=NULL; q=q->next){ // 정점 p의 부착 간선 리스트 순회
p = findVertex(G, q->aName); // p에 q가 속한 정점 저장
if(p->isVisit == FALSE){ // 정점 p가 최소신장트리 T에 속하지 않았다면
D[q->aName-97] = q->e->weight; // 간선의 가중치를 저장
}
}
}
}시간복잡도는 (n-1)×O(n) = O()이고, 최소 힙(Binary Heap)을 사용하여 Vmin을 찾으면 간선 수 m에 대하여 O(mlogm)이다.
최단 경로(Shortest Path) 문제
주어진 가중치 그래프에서 어느 한 출발점에서 또 다른 도착점까지의 최단 경로를 찾는 문제이다.
다익스트라(Dijkstra) 알고리즘
주어진 출발점에서 시작하고, 출발점으로부터 최단 거리가 확정되지 않은 점들 중에서 출발점으로부터 가장 가까운 점을 추가하고, 그 점의 최단 거리를 확정한다.
ShortestPath(G, s)
입력: 가중치 그래프 G=(V,E), |V|=n, |E|=m
출력: 출발점 s로부터 (n-1)개의 점까지 각각 최단 거리를 저장한 배열 D
1. 배열 D를 ∞로 초기화. 단, D[s]=0로 초기화
2. while(s로부터의 최단 거리가 확정되지 않은 점이 있으면){
3. 현재까지의 최단 거리가 확정되지 않은 점 v에 대해서 최소의 D[v]의 값을 가진 점 Vmin을 선택하고, s로부터 점 Vmin까지의 최단거리 D[Vmin]을 확정
4. s로부터 현재보다 짧은 거리로 점 Vmin을 통해 우회 가능한 각 점 w에 대해서 min(기존 D[w], D[Vmin]+weight(Vmin,w))로 D[w]를 갱신
}
5. return D
시간 복잡도는 while문이 (n-1)회 반복되고, 1회 반복될 때 Vmin을 찾기 위해 배열 D에서 최솟값을 찾는 동안 O(n) 시간이 걸리고, Vmin에 연결된 점의 수가 최대 (n-1)개이므로 D[w]를 갱신하는데 O(n) 시간이 걸린다. 따라서 (n-1)×{O(n)+O(n)}=O()이다. 최소 힙(Binary Heap)을 사용하면 간선 수 m에 대하여 O(mlogn)이다.
배낭(Knapsack) 문제
n개의 물건이 각각 1개씩 있고, 각 물건은 무게와 가치를 가지고 있으며, 배낭이 한정된 무게의 물건들을 담을 수 있을 때 최대의 가치를 갖도록 배낭에 넣을 물건들을 정하는 문제
(1) 부분 배낭(Fractional Knapsack) 문제
물건을 부분적으로 담는 것을 허용한다.
단위 무게 당 가장 값나가는 물건을 배낭에 넣고, 계속해서 그 다음으로 값나가는 물건을 넣는다. 물건을 통째로 배낭에 넣을 수 없으면, 배낭에 넣을 수 있을 만큼만 물건을 부분적으로 배낭에 담는다.
FractionalKnapsack
입력: n개의 물건, 각 물건의 무게와 가치, 배낭의 용량 C
출력: 배낭에 담은 물건 리스트 L과 배낭 속의 물건 가치의 합 v
1. 각 물건에 대해 단위 무게 당 가치를 계산한다.
2. 물건들을 단위 무게 당 가치를 기준으로 내림차순으로 정렬하고, 정렬된 물건 리스트를 S라 한다.
3. L은 배낭에 담을 물건 리스트, w는 배낭에 담긴 물건들의 무게 합, v는 배당에 담긴 물건들의 가치의 합이며, L=NULL, w=0, v=0으로 초기화한다.
4. S에서 단위 무게 당 가치가 가장 큰 물건 x를 가져온다.
5. while w+(x의 무게) <= C{
x를 L에 추가
w = w + (x의 무게)
v = v + (x의 가치)
x를 S에서 제거
S에서 단위 무게 당 가치가 가장 큰 물건 x를 가져온다.
}
6. if C-w >0{
물건 x를 (C-w)만큼만 L에 추가
v = v + ((C-w)만큼의 x의 가치)
}
7. return L, v;
시간 복잡도는 단위 무게 당 가치를 계산하는데 O(n), 단위 무게 당 가치에 대해서 정렬하는데 O(nlogn), while 루프의 수행은 n번을 넘지 않으며, 루프 내부의 수행은 O(1). 따라서 시간 복잡도는 O(nlogn)이다.
(2) 0-1 배낭 문제
부분 배낭 문제의 원형으로, 물건을 통쨰로 배낭에 넣어야 한다. (이 문제는 동적 계획 알고리즘, 백트래킹 기법, 분기 한정 기법으로 해결한다.)
집합 커버 문제
n개의 원소를 가진 집합 U가 있고, U의 부분집합들을 원소로 하는 집합 F가 주어질 때, F의 원소들인 집합들 중에서 어떤 집합들을 선택하여 합집합하면 U와 같게 되는가? ⇒ 집합 F에서 선택하는 집합들의 수를 최소화하는 문제
SetCover
입력: U, F = {Si}, i=1,...,n
출력: 집합 커버 C
C= NULL
while U != NULL {
U의 원소를 가장 많이 가진 집합 Si를 F에서 선택
U = U- Si
Si를 F에서 제거하고, Si를 C에 추가
}
return C
while 루프는 최대 n회 수행되고, 루프가 1회 수행될 때 Si들의 수가 n개이고 각 Si와 U의 비교는 O(n)이므로 O() 시간이 걸린다. 따라서 시간 복잡도는 O()이다.
작업 스케줄링(Job Scheduling) 문제
작업의 수행 시간이 중복되지 않도록 모든 작업을 가장 적은 수의 기계에 배정하는 문제. 작업의 수/각 작업의 시작시간과 종료시간/작업의 길이를 고려해야한다.
JobScheduling
입력: n개의 작업
출력: 각 기계에 배정된 작업 순서
작업을 시작 시간 오름차순으로 정렬하여 배열 L에 저장한다.
while (L != NULL){
L에서 가장 이른 시작 시간 작업을 가져온다.
if(수행할 기계가 있으면) 해당 기계에 작업 배정
else 새 기계에 작업 배정
수행한 작업 L에서 제거
}
return 각 기계에 배정된 작업 순서;
시작 시간 오름차순으로 정렬하는데 O(nlogn). while 루프는 총 n번 수행되며, 1회 수행될 때 수행 가능한 기계를 찾아서 배정하므로 기계의 수 m에 대해 O(m). 따라서 시간 복잡도는 O(nlogn)+O(mn)이다.
허프만 압축
파일의 각 문자가 8bit 아스키 코드로 저장된다고 하자. 고정된 크기의 코드로 구성된 파일을 저장하거나 전송할 때, 파일의 크기를 줄이고 메모리 공간을 효율적으로 사용하기 위해 파일의 크기를 줄이는 방법을 파일 압축이라고 한다. 허프만 압축은 파일에 빈번히 나타나는 문자에는 짧은 이진 코드를 할당하고, 드물게 나타나는 문자에는 긴 이진 코드를 할당하는 방법이다.
허프만 압축 방법으로 변환시킨 문자 코드들 사이에는 접두부 특성(prefix property)이 존재하는데, 이는 각 문자에 할당된 이진 코드가 다른 문자에 할당된 이진 코드의 접두부(prefix)가 되지 않는 특성이다. 따라서 허프만 압축에서는 코드와 코드 사이를 구분할 특별한 코드가 필요 없다.
