[Chapter4] 그리디 알고리즘(1)

- 그리디 알고리즘은 최적화 문제를 해결하는 알고리즘

* 최적화 문제: 가능한 해들 중에서 가장 좋은 해(최소 비용, 최대 이익 등..)를 찾는 문제

 

- 욕심쟁이 방법, 탐욕적 방법, 탐욕 알고리즘 등으로 불림

 

- 근시안적 선택

: 입력 데이터 간 관계 고려x 수행 과정에서 순간순간 최솟값 또는 최댓값 가진 데이터 선택

 

- 일단 한 번 선택하면 -> 절대로 번복하지 x

=> 대부분의 그리디 알고리즘들은 매우 단순, 제한적인 문제만이 그리디 알고리즘으로 해결 가능

 

동전 거스름돈 문제

 

남은 액수를 초과하지 않는 조건 하에 욕심내어 가장 큰 액면의 동전을 취하는 것

 

CoinChange
입력: 거스름돈 액수 W
출력: 거스름동 액수에 대한 최소 동전 수
change=W, n500=n100=n50=n10=n1=0
while(change>=500)
	change=change-500, n500++ //500원 동전 수 1 증가
while(change>=100)
	change=change-100, n100++ //100원 동전 수 1 증가
while(change>=50)
	change=change-50, n50++ //50원 동전 수 1 증가
while(change>=10)
	change=change-10, n10++ //10원 동전 수 1 증가
while(change>=1)
	change=change-1, n1++ //1원 동전 수 1 증가
return (n500+n100+n50+n10+n1) //총 동전 수 리턴

 

def coin_change(don):
	coin=[500,100,50,10,5,1]
    count=0
    for i in range(len(coin)):
		count don // coin[i] #동전 수
        don=don%coin[i] #남은 돈
        if count!=0:
        	print('{:3}원짜리 동전: {:2}개'.format(coin[i], count))

 

문제점

 

한국은행에서 160원 동전을 추가로 발행한다면, CoinChange 알고리즘이 항상 최소 동전 수를 계산할 수 있을까?

- 거스름돈이 200원이라면, CoinChange 알고리즘은 160원 동전 1개와 10원 동전 4개로서 총 5개를 리턴

- 200원에 대한 최소 동전 수는 100원짜리 동전 2개

=> 썼을 때보다 안 썼을 때 동전 개수가 적음

 

최소 신장 트리(Minimum Spanning Tree)

 

주어진 가중치 그래프에서 사이클이 없이 모든 점들을 연결시킨 트리들 중 간선들의 가중치 합이 최소인 트리

 

<트리가 되기 위한 조건>

1. n개의 vertax를 n-1개의 edge가 연결하고 있으며(∵ 그래야 모든 점들이 연결될 수 있기 때문)

2. 점들 간 cycle 없을 때(∵ edge가 n-1보다 크면 반드시 cycle 만들어짐)

<최소 신장 트리>

다음 중 최소 신장 트리는 1번. 왜냐.

=> 3번 한 점이 빠져서 안 되고, 2번은 가중치 합이 커서 안 됨

 

- Kruskal 알고리즘: 정렬 사용

- Prim 알고리즘: 정렬 사용하지 않고 임의의 점 하나를 선택한 후 그걸 기준으로 추가시켜나감

크러스컬(Kruskal) 알고리즘

 

: 가중치가 가장 작은 간선이 사이클을 만들지 않을 때만 욕심내어 그 간선 추가

쉽게 말해, 남은 것 중에 최소 가중치 간선부터 추가

 

<알고리즘>

KruskalMST(G)
입력: 가중치 그래프 G=(V,E), |V|=n, |E|=m //입력은 1개의 연결 성분으로 된 가중치 그래프
출력: 최소 신장 트리 T
1. 가중치의 오름차순으로 간선들 정렬: L = 정렬된 간선 리스트 //** 포인트1
2. T=∅ // 트리 T를 초기화
3. while(T의 간선 수 < n-1) //트리의 간선 수가 n-1이 되면 더 이상 안 해도 됨
	L에서 가장 작은 가중치를 가진 간선 e를 가져오고, e를 L에서 제거
    if(간선 e가 T에 추가되어 사이클을 만들지 않으면) //**포인트2(사이클 검사)
    	e를 T에 추가
    else	//e가 T에 추가되어 사이클이 생기는 경우
    	e를 버린다.
return 트리 T //T는 최소 신장 트리

 

<시간복잡도>

(Line 1) 간선 정렬하는 데 O(mlogm)

* m = 입력 그래프에 있는 간선 수

(Line 2) 초기화하는 것이므로 O(1)

(Line 3~8) 사이클 검사 -**point**

while 루프는 최대 m번 수행

while 루프 내에서는 사이클 검사 O(1)

 

==> O(mlogm)

 

def find(u): # 경로 연산
	if u != p[u]: # u가 u자신의 부모가 아니면
    	p[u] = find(p[u]) #경로 압축
	return p[u]
    
def union(u,v): # 부모 설정
	root1 = find(u)
    root2 = find(v)
    p[root2] = root1
    
weights = [ .... ] #정렬된 간선들
mst = [] #최종 트리
N = 정점 수
p = [] #부모 정점 정보 for 사이클 검사(초기값은 자기 자신)
tree_edges = 0
mst_cost = 0
while True:
	if tree_edges == N-1:
    	break
    u,v,wt = weights.pop(0) # 다음 최소 가중치 간선 가져오기
    if find(u) != find(v): # 사이클 검사(중요)
    	union(u, v) # 부모 설정
        mst.append((u,v)) #트리에 (u,v) 추가
        mst_cost += wt

1. b-c(1) 선택

find(b): p[b]=b(초기화 상태)이므로, 그냥 b를 리턴

find(c): p[c]=c(초기화 상태)이므로, 그냥 c를 리턴

find(b)!=find(c)이므로

union(b,c): b가 c의 부모가 됨(p[c]=b)

 

 

2. c-f(1) 선택

find(c): p[c]=b이므로, p[c]=find(b)=b 리턴

find(f): p[f]=f이므로, 그냥 f를 리턴

find(c)!=find(f)이므로

union(c,f): find(c)=b가 f의 부모가 됨(p[f]=b)

 

 

3. a-d(2) 선택

find(a): p[a]=a이므로, a 리턴

find(d): p[d]=d이므로, d 리턴

find(a)!=find(d)이므로

union(a,d): find(a)=a가 d의 부모가 됨(p[d]=a)

 

 

4. b-f(2) 선택

find(b): p[b]=b이므로, 그냥 b를 리턴

find(f): p[f]=b이므로, p[f]=find(p[f])=find(b)=b 리턴

=> find(b)=find(f)이므로 선택x(cycle 발생)

 

5. d-e(3) 선택

find(d): p[d]=a이므로, p[d]=find(p[d])=find(a)=a 리턴

find(e): p[e]=e이므로 e 리턴

=> find(d)!=find(e)이므로

union(d,e): find(d)=a가 e의 부모가 됨(p[e]=a)

6. a-e(4) 선택

find(a): p[a]=a이므로 a 리턴

find(e): p[e]=a이므로 p[e]=find(p[e])=find(a)=a 리턴

=> find(a)=find(e)이므로 선택x(cycle 발생)

 

7. b-d(4) 선택

find(b): p[b]=b이므로 b 리턴

find(d): p[d]=a이므로 p[a]=find(p[a])=find(a)=a 리턴

=> find(b)!=find(d)이므로

union(b,d): find(b)=b가 find(d)=a의 부모가 됨(p[a]=b)

코드 없이 다음과 같이 풀면 된다.

프림 알고리즘

 

: 임의의 점 하나 선택 -> (n-1)개의 간선 하나씩 추가

쉽게 말해, 임의의 점 하나를 먼저 선택하고, 두 점과 연결된 모든 간선들 중 최소 가중치 가진 점부터 추가

 

(Line 1)

임의의 점 c 선택, D[c]=0으로 초기화

 

(Line 2~6)

- 시작점 c와 간선으로 연결된 각 점 v에 대해, D[v]를 각 간선의 가중치로 초기화

- 나머지 각 점 v에 대해, D[v]는 ∞로 초기화

(Line 7)

T={c}로 초기화

 

(Line 8~9)

1. min{∞,1,∞,∞,1}=1

=> T에 가장 가까운 점 b를 추가

=> b에 연결된 a와 d의 D[a]와 D[d] 갱신

2. min{3,4,∞,1}=1

=> T에 가장 가까운 점 f를 추가

=> f에 연결된 e의 D[e] 갱신

 

3. min{3,4,9}=3

=> a를 T에 추가

=> a에 연결된 d, e의 D[d]와 D[e] 갱신

4. min{4,2}=2

=> d를 T에 추가

=> 갱신x

5. min{4}=4

=> e를 T에 추가

=> MST 완성

PrimMST(G)
입력: 가중치 그래프 G=(V,E), |V|=n, |E|=m
출력: 최소 신장 트리 T
1. G에서 임의의 점 p를 시작점으로 선택 D[p]=0
//D[v]는 T에 있는 u와 v를 연결하는 간선의 최소 가중치를 저장하기 위한 원소
2. for (점 p가 아닌 각 점 v에 대하여) // 배열 D의 초기화
	if (간선 (p,v)가 그래프에 있으면)
    	D[v] = 간선 (p,v)의 가중치
    else
    	D[v] = ∞
   T={p} //초기에 트리 T는 점 p만을 가진다.
   while (T에 있는 점의 수 < n) {
   	T에 속하지 않은 각 점 v에 대하여,
    D[v]가 최소인 점 vmin과 연결된 간선 (u, vmin)을 T에 추가,
    여기서 u는 T에 속한 점이고, 점 vmin도 T에 추가
   for(T에 속하지 않은 각 점 w에 대해서)
   	if(간선 (vmin, w)의 가중치 < D[w]) //D[w]를 갱신
   }

 

<시간 복잡도>

 

1. while-루프가 (n-1)회 반복

2. T에 속하지 않은 각 점 v에 대해, D[v]가 최소인 점 vmin을 찾는 데 O(n) 소요(∵ 배열의 크기=n)

 

=> (n-1)*O(n)=O(n^2)

 

만약, 단순 배열이 아니라 최소 힙을 사용해 vmin 찾는다면, 

 

* Binary Search Tree(이진탐색트리)는 Complete binary tree와 달리 균형이 잡혀 있지 않다.

 

* max/min heap이 있는데, max heap은 큰 숫자부터 위에서 아래로(형제관계는 상관 x)

min heap은 작은 숫자부터 위에서 아래로(형제관계는 상관 x)

=> priority queue 형태로 루트부터 꺼냄 => 꺼낸 후에는 complete binary tree 형태로 재배치

 

=> 루트 꺼내면 오른쪽 아래 요소를 루트로 옮겨야 하므로 O(logn)

간선 수를 m이라고 하면 O(mlogn)

간선 수가 O(n)이면 O(nlogn)

 

<응용>

 

: 최소 비용으로 선로 또는 파이프 네트워크를 설치하는 데 활용

(인터넷 광 케이블 선로, 케이블 TV 선로, 전화 선로, 송유관로, 가스관로, 배수로 등)

풀어보기

최단 경로 찾기

 

: 주어진 가중치 그래프에서 어느 한 출발점에서 또 다른 도착점까지의 최단 경로 찾기

 

다익스트라(Dijkstra) 알고리즘

 

: 주어진 출발점에서 시작

: 출발점으로부터의 최단 거리가 확정되지 않은 점들 중 출발점으로부터 가장 가까운 점 추가 -> 그 점의 최단 거리 확정

Prim	Dijkstra
최단 거리가 확정되지 않은 점들 중 출발점으로부터 가장 가까운 점부터 추가해나감
추가된 점까지의 거리만 계산	누적 거리 계산

 

<알고리즘>

ShortestPath(G,s)
입력: 가중치 그래프 G=(V,E), |V|=n, |E|=m
출력: 출발점 s로부터 (n-1)개의 점까지 각각 최단 거리를 저장한 배열 D
1. 배열 D를 로 초기화. 단, D[s]=0으로 초기화
//배열 D[v]에는 출발점 s로부터 점 v까지의 거리를 저장
while(s로부터의 최단 거리가 확정되지 않은 점이 있으면)
	현재까지 최단 거리가 확정되지 않은 각 점 v에 대해서
    최소의 D[v]의 값을 가진 점 vmin을 선택하고,
    s로부터 점 vmin까지의 최단 거리 D[vmin]을 확정
    s로부터 현재보다 짧은 거리로 점 vmin을 통해 우회 가능한 각 점 w에 대해서 D[w]를 갱신 //이것이 Prim 알고리즘과 다른 점
    //간선 완화
return D

 

간선 완화하는 9~13번째줄 외우자.

for k in range(N)
	m = -1
    min_value = sys.maxsize
    for j in range(N): #방문 안 된 정점들의 D 원소들 중 최솟값을 가진 정점 m 찾기
    	if not visited[j] and D[j] < min_value:
        	min_value = D[j]
            m = j
    visited[m] = True
    for w, wt in g[m]: # m에 인접한 방문 안 된 각 정점의 D의 원소 갱신
    	if not visited[w]:
        	if D[m]+wt < D[w]:
            		D[w] = D[m] + wt # 간선 완화
                	previous[w] = m

 

<step1>

: 서울 확정

=> 서울과 이웃한 원주, 천안 간선 완화

* 간선 완화란 그냥 아래처럼 표에 거리 채워넣는 것을 말함

<step2>

: 천안 확정

=> 논산, 대전 간선 완화

<step3>

: 원주 확정

=> 강릉, 대구 간선 완화

 

<step4>

: 논산 확정

=> 대전 간선 완화

<step5>

: 대전 확정

=> 간선 완화x

<step6>

: 대구 확정

=> 포항, 부산 간선 완화

 

<step7>

: 광주 확정

=> 간선 완화 x

 

<step8>

: 부산 확정

=> 포항 간선 완화

<step9>

: 강릉 확정

<step10>

: 포항 확정

 

<시간 복잡도>

- while 루프가 (n-1)회 반복되고, 1회 반복될 때

배열에서 최솟값 찾음 => 최소의 D[v]를 가진 점 vmin을 찾는 데 O(n) 시간 소요

vmin에 연결된 점의 수가 최대 (n-1)개 => D[w]를 갱신하는 데 O(n) 시간 소요

(n-1)*(O(n)+O(n))=O(n^2)

 

배열 대신 최소 힙을 사용하면 => O(mlogn)

간선 수가 O(n)이면 => O(nlogn)

 

	Kruskal	Prim	Dijkstra
시간복잡도	O(mlogm)	배열 사용 시 O(n^2) 힙 사용 시 O(mlogn)	배열 사용 시 O(n^2) 힙 사용 시 O(mlogn)