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

 

◆그리디 알고리즘의 특징

 

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

 

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

 

 

 

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

 

1)동전 거스름돈

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

 

#유사코드

 

 

#파이썬 소스

 

 

 

2)최소 신장 트리

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

 

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

 

#크루스컬 유사코드

 

 

#프림 유사코드

 

 

#파이썬 소스

 

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

+ Recent posts