그리디 (활동 선택 문제, 분할 가능 배낭 문제)
그리디 알고리즘 그리디 알고리즘이란 눈앞의 이익만 우선 추구하는 알고리즘을 말한다. 예를들어 이진 트리에서 그리디 탐색을 한다고 했을때 트리의 내용을 사전에 알지 못하는 상태에서 루트부터 시작해 왼쪽으로 갈지 오른쪽으로 갈지 매 단계마다 결정해서 가장 큰값을 찾아낸다고 하자 루트의 오른쪽에 60 이 있고 루트의 왼쪽에 15가 있다면 그리디는 눈앞의 이익을 우선하기 때문에 60을 쫒아간다. 하지만 60은 밑에 자식이 없고 15는 밑에 100이라는 자식이 있다면 결국 15로 갔을때 가장 큰값이 나오게된다. 이렇듯 그리디 알고리즘은 대부분의 경우 뛰어난 결과를 도출하지 못하지만 드물게 최적해를 보장하는 경우가 있다. 그 예로는 최소 신장 트리를 찾는 프림알고리즘이 있다. 프림 알고리즘은 그래프에서 연결하는 간..
2019.06.03