[알고리즘]그리디 알고리즘

그리디 알고리즘 : 최적화 문제(가능한 해들 중 가장 좋은 해를 고르는)를 해결하는 알고리즘

 

◆그리디 알고리즘의 특징

 

1)데이터 간의 관계를 고려하지 않고 부분적인 최적해를 찾고, 이들을 모아서 문제의 최적해를 얻는다.

 

2)일단 한번 선택하면 그 데이터를 버리고 다른 것을 취하지 않는다.

 

 

 

◆그리디 알고리즘으로 해결 가능한 대표적인 문제들

 

1)동전 거스름돈

:거스름돈을 받을 때 가장 적은 수의 동전으로 주는 문제

 

#유사코드

 

입력:거스름돈 액수W 출력:거스름돈 액수에 대한 최소 동전 수 change=W,n500=n100=n10=n1=0 //n500,n100,n50,n10,n1은 각각의 동전 수를 위한 변수이다. while(change>=500) change=change-500,n500++ while(change>=100) change=change-100,n100++ while(change>=50) change=change-50,n50++ while(change>=10) change=change-10,n10++ while(change>=1) change=change-1,n1++ return (n500+n100+n50+n10+n1)

 

#파이썬 소스

 

def CoinChange(W): change=W n500=0 n100=0 n50=0 n10=0 n1=0 while change >= 500: change -= 500 n500 += 1 while change >= 100: change -= 100 n100 += 1 while change >= 50: change -= 50 n50 += 1 while change >= 10: change -= 10 n10 += 1 while change >= 1: change -= 1 n1 += 1 return (n500+n100+n50+n10+n1) print(CoinChange(760))

 

 

2)최소 신장 트리

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

 

최소 신장 트리를 찾는 대표적인 그리디 알고리즘으로는 크러스컬과 프림 알고리즘이 있음.

 

#크루스컬 유사코드

 

입력:가중치 그래프 G=(V,E), │V│=n, │E│=m 출력:최소 신장 트리 T 가중치의 오름차순으로 선분들을 정렬한다. 정렬된 선분 리스트를 L이라고 하자. T=Φ //트리 T를 초기화 while(T의 선부 수 < n-1){ L에서 가장 작은 가중치를 가진 선분 e를 가져오고, e를 L에서 제거한다. if(선분 e가 T에 추가되어 사이클을 만들지 않으면) e를 T에 추가시킨다. else //e가 T에 추가되어 사이클이 만들어지는 경우 e를 버린다. } 10. return 트리 T //T는 최소 신장 트리이다.

 

#프림 유사코드

 

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

 

#파이썬 소스

 

*크러스컬과 프림 둘 다 제 파이썬 숙련도로는 무리인 것 같습니다 지송합니다 ㅠㅠ