11. 그리디 알고리즘 (1)

1. 전형적인 그리디 알고리즘의 구조

 

-눈 앞의 이익만 추구하는 알고리즘을 총칭해서 그리디 알고리즘 (Greedy Algorithm)이라고 한다.

-그리디 알고리즘은 대부분의 경우 뛰어난 결과를 도출하지 못하지만 드물게 최적해를 보장하는 경우가 있다.

-그리디 알고리즘은 최적화 문제를 대상으로 한다.

 

** 최적해, 最適解, optimal solution 선형 프로그래밍에서 제약 조건을 충족시키는 가능한 해 (解) 중 목적 함수 값을 최대 또는 최소로 만드는 값.

 

-최적해를 찾을 수 있으면 그것을 목표로 삼고, 찾기 어려운 경우에는 주어진 시간 내에 그런대로 괜찮은 해를 찾는 것을 목표로 삼는다.

-아래는 전형적인 그리디 알고리즘의 구조이다.

do
	가장 좋아 보이는 선택을 한다
until (해 구성 완료)

 

-그리디 알고리즘은 하나의 온전한 해가 만들어질 때까지 눈앞에 가장 좋아보이는 선택을 반복한다.

-ex) 최소 신장 트리 알고리즘

: n개의 정점을 가진 어떤 그래프의 최소 신장 트리는 사이클을 이루지 않는 총 n-1개의 간선으로 이루어짐

: 간선이 하나도 없는 집합에서 시작하여 간선을 하나씩 더해 나가면서 n-1개의 간선이 될 때까지 집합을 키워나가는데, 이 과정에서 각 단계에서 어떤 간선을 선택할지 결정하는 로직이 있어야 한다.

: 이 로직이 눈 앞의 이익만 추구하면 그리디 알고리즘 계열에 속하게 된다.

:최소 신장 트리에서는 간선을 하나 더할 때마다 해당 간선이 기존에 선택된 간선들과 사이클을 이루지 않는지 확인해야 하고, 모든 그리디 알고리즘은 이런 구성 요소를 포함한다.

 

-최소 신장 트리를 찾는 그리디 알고리즘 중 하나인 프림 알고리즘

#G=그래프, r=시작 정점

Prim(G, r):
	S<-null, T<-null  #S=정점집합, T=간선집합
    S.append(r)
    while(S!=T)
    	S에서 V-S를 연결하는 간선들 중 최소 길이의 간선 (x, y)를 찾는다
        T에 간선 (x, y)를 더한다.
        정점 y를 집합 S에 더한다.

 

-간선의 집합 T는 공집합으로 시작하여 알고리즘이 끝나면 n-1개의 간선을 포함하게 되고, 그것이 최적해가 된다.

 

#C=원소들의 총집합

Greedy(C):
	S<-null
    while(C!=null and S는 아직 온전한 해가 아님):
    	x<-C에서 원소를 하나 선택 ---(1)
        집합 C에서 x를 제거
        if (S에 x를 더해도 됨) S<-S U {x} --- (2)
    if(S가 온전한 해임) return S
    else return "해없음!"

 

-(1)에서 원소를 선택하는 기준이 눈 앞의 이익을 우선하는 그리디 알고리즘 계열에 속한다.

-프림 알고리즘의 경우 집합 S에 속하는 정점과 속하지 않는 정점을 연결하는 간선들 중 가장 짧은 것을 우선 택한다.

-최소 신장 트리는 간선의 합을 최소로 하는 신장 트리를 찾는 것이므로 부분적으로 만들어진 신장 트리에 연결할 수 있는 간선 중 길이가 가장 짧은 것을 우선 택하고 보는 것이다.

-이러한 근시안적인 선택이 최적해를 보장하는 경우는 드물지만, 최소 신장 트리 문제는 이런 방식으로 최적해가 보장되는 드문 예 중 하나이다.

-(2)는 원소를 하나 더하기 전에 해당 원소를 더함으로써 온전한 해가 될 가능성이 없어지지 않았는지 체크하는 과정이다

 

 

2. 그리디 알고리즘으로 최적해가 보장되지 않는 예

 

- 그리디 알고리즘은 대부분의 경우 최적해를 보장하지 못함, 다음은 이의 예시임

 

(1) 이진 트리의 최적합 경로 찾기

-각 노드가 양의 가중치를 가지는 이진트리가 존재하고, 트리의 내용은 사전에 알지 못 한다.

-루트노드부터 시작해 왼쪽으로 분기할 지, 오른쪽으로 분기할 지를 매 단계마다 결정해야 하고, 이렇게 내려가다 리프 노드를 만나면 끝이 나게 되는 구조이다.

-이 과정에서 만난 노드에 있는 가중치의 합이 이 경로의 점수이고, 이 합을 최대화하는 알고리즘을 찾아야 한다.

-이 문제는 척 보면 모든 노드를 다 보기 전에는 최적해를 보장할 수 없다는 것을 알게 된다.

-극단적인 예로, 가보지 않은 어떤 노드가 모든 다른 경로의 합보다 큰 가중치를 가지고 있을 가능성을 배제할 수 없다.

-그러므로 루트로부터 DFS와 같은 백트래킹 탐색을 할 수밖에 없고, 수행 시간의 상한은 트리의 총 노드 수에 비례하게 된다.

그리디 알고리즘이 이진 탐색 트리에서 최적해를 보장하지 못하는 경우

 

(2) 보따리 문제

-부피가 M인 보따리 (냅색, Knapsack)와 이 보따리에 넣으려하는 n개의 물건이 있다.

-물건 i의 부피는 Wi 이고, 이 물건을 보따리에 넣을 경우 Pi의 가치가 있다. 물건들의 전체 부피 합이 M을 넘지 않도록 하면서 가치가 최대가 되도록 보따리에 물건들을 넣어보는 문제이다.

-이 그리디 알고리즘은 보따리 용량을 초과하지 않은 한 단위 부피당 가치가 가장 큰 물건 순서로 각 물건을 보따리에 추가하게 되는데, 이 방식의 그리디 알고리즘은 최적해를 보장하지 못 한다. (30이 최대치일 때 10+9+8 보다 7+6+5+4+3+2+1 이 더 값이 크기 때문)

-보따리 문제에서 물건을 자를 수 있다며 최적해를 보장할 수 있게 되는데, 즉 단위 부피당 가치가 가장 큰 물건 순서로 각 물건을 보따리에 추가하다가 어떤 물건을 넣으려는 순간 보따리 용량을 초과하면 남은 용량에 들어갈 만큼만 잘라서 넣으면 문제가 해결되기 때문이다.

-이 유형의 문제를 자를 수 있는 보따리 문제라고 부른다. (Fractional Knapsack problem)

 

(3) 동전 바꾸기

-우리나라에는 500원, 100원, 50원, 10원, 1원의 여섯 가지 동전이 존재한다.

-3256원을 가장 적은 개수의 동전을 사용해 만든다고 하면, 먼저 500원을 쓸 수 있을 때까지 쓰면 6개, 다음 100원 2개, 50원 1개, 5원 1개, 1원 1개를 사용하면 총 11개의 동전으로 3256원을 만들 수 있고, 이 경우가 최적해이다.

-이처럼 동전의 액면이 커지면서 바로 아래 액면의 배수가 되는 경우에는 위의 예시와 같이 그리디한 방식으로 최적해를 구할 수 있다.

-그렇지만 동전의 액면이 증가하면서 앞 액면의 배수가 되지 않는 경우에는 그리디한 방법으로 최적해가 보장되지 않는다. 이에 대한 예시는 동전의 액면이 다음과 같이 500원, 400원, 100원, 75원, 50원일 때이다.

-위의 동전들로 1300원을 만들어보게 되면, 앞에서 사용한 그리디 알고리즘을 사용하면 500원이 2개, 100원 3개를 선택하게 되어 총 5개의 동전을 사용하게 된다.

-하지만 이에 대한 최적해는 500원 1개, 400원 2개로 총 3개의 동전인 경우이다.

-따라서 이 문제는 그리디 알고리즘보다, 이전에 배운 동적 프로그래밍의 방식을 이용하여 최적해를 구하는 것이 더 좋은 방법이라고 할 수 있다.

 

 

3. 그리디 알고리즘으로 최적해가 보장되는 예

 

(1) 최소 신장 트리

-최소 신장 트리를 위한 프림 알고리즘, 크루스칼 알고리즘은 그리디 알고리즘으로 최적해가 보장되는 경우이다.

-다음은 프림 알고리즘에 대한 예시이다.

#G(V, E) : 주어진 그래프, r: 시작 정점

Prim(G, r):
	S<-null
    for each u is in V:
    	u.cost<- unlimited
    r.cost<-0
    
    while(S!=V)
    	u<-extractMin(V-S, d)
        S<-S U {u}
        for each V is in u.adjlist
        	if(v is in V-S and w(u,v) < v.cost)
            	v.cost <- w(u,v)
                v.prev<-u

 

-이 알고리즘이 진행되는 중간의 한 시점을 살펴보면, 집합 S에 지금까지 처리가 끝난 정점들의 집합이 들어있고, 아직 처리가 끝나지 않은 정점 (V-S에 속하는 정점)들 중에서 집합 S로 연결하는 간선 중 가장 짧은 간선을 가진 정점 (u)을 집합 S에 더한다.

-어떤 시점이든지 그 시점에서 집합 S에 가잔 싼 비용으로 연결이 되는 정점을 택하고, 이렇게 그리디한 방법을 사용했음에도 불구하고 다행히 최적해를 놓치지 않는다.

 

(2) 회의실 배정 문제

-회사에 1개의 회의실이 존재하고, 여러 부서가 회의실을 사용하므로 미리 신청을 받아 스케줄링을 한다.

-회의실을 사용하고자 하는 부서는 원하는 회의 시작 시간과 종료 시간을 명시하여 신청서를 제출한다. 이렇게 받은 n개의 회의 신청에 대하여 회의실 사용 스케줄을 정하려고 하는 문제이다.

-구현의 편의를 위해 앞 회의 종료시간과 바로 다음 회의 시작 시간이 같아도 된다고 가정하자.

# S={s(i), t(i) | i=1, 2, ..., n}, n: 신청 회의 수}
# s:시작 시간 , t:종료 시간

Greedy_Schedule(S, n):
	t(1)에 대한 오름차순으로 정렬하고, 이 순서대로 S의 번호를 매긴다.
    T<-{1}
    last<-1
    for(i<-2 to n)
    	if(t(last)<=s(i))
        	T<- T U {i}
            last <- i
    return T

 

-ex) 다음 8개의 회의가 신청이 된 상황 -> (3, 5), (1, 6), (6, 7), (5, 9), (8, 13), (7, 14), (12, 18), (16, 20)

-알고리즘은 이 순서로 회의들을 포함시킬지 체크한다.

-먼저 1번 회의 (3, 5)는 무조건 들어가고, 1번 회의가 끝난 시간은 5이다.

-앞의 회의와 배정 시간이 겹피는 (1,6)은 제외되고, 그 다음 (6, 7)은 겹치지 않으므로 포함되게 된다.

-위와 같은 알고리즘으로 배정한 결과는 다음과 같다 -> (3, 5), (6, 7), (8, 13), (16, 20)

-이것은 얼핏 보면 직관과 어긋나 보이지만, 시작 시간이 가장 빠른 회의를 먼저 고려하는 것보다 훨씬 최적의 해를 가지게 되는 결과를 초래한다

 

(3) 그 밖의 예

-그래프에서 최단 경로를 구하는 다익스트라 알고리즘도 그리디 알고리즘이다

-문서에서 각 원소들의 출현 빈도가 주어질 때 해당 문서를 효율적으로 압축하는 코드를 만드는 허프만 코딩 알고리즘도 그리디 알고리즘이다

-이들은 그리디 알고리즘이면서 최적해가 보장이 되는 예시이다.