그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)

그리디 알고리즘(욕심쟁이 알고리즘, Greedy Algorithm)이란 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 모토를 가지는 알고리즘 설계 기법이다.

예를 들어 5개의 도시를 모두 한 번씩만 거쳐서 여행하고 싶은데 여행 도중 기름값을 아끼기 위해 가능하면 짧은 경로를 이용하고 싶다고 가정하자. 이 문제를 해결하기 위해 사용할 수 있는 전략은 몇 가지가 있다. 가능한 120가지의 경우의 수를 브루트 포스로 모두 살펴봐서 그중 가장 짧은 경로를 선택하는 것도 하나의 전략이 될 것이고, 외판원 순회 문제 문서에 나와있는 복잡한 전략을 쓸 수도 있고, "지금 내가 있는 도시에서 고를 수 있는 도로 중 가장 짧은 도로를 선택한다"라는 방법, 즉 그리디 알고리즘을 쓸 수도 있다.

단, 그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것을 명심해야 한다. 위와 같은 예시에서 매 순간 최적을 따라가면 1-1-1-100라는 순서로 가는데, 중간에 살짝 먼 길을 섞어서 1-1-10-10으로 움직이는 것이 전체적으로 더 짧은 길이 될 수 있으니 말이다. 스탠퍼드 마시멜로 실험에 비유하면 그리디 알고리즘을 사용한다는 것은 지금 당장 눈 앞에 있는 마시멜로를 먹는 것이다. 하지만 이 방법을 사용하는 것은 "기다렸다가 2개를 먹는다"라는 최적해를 보장해주지 못한다.

그리디 알고리즘은 부분의 최적해들의 집합이 곧 전체 문제의 해답이 될 때 사용할 수 있다. 위 서술 같은 경우는 그리디 알고리즘으로 해결 할 수 없는 문제에 그리디 알고리즘을 적용한 경우니 당연히 최적해를 보장해주지 못한다.

 

그리디 알고리즘은 탐욕 선택 속성(greedy choice property), 최적 부분 구조(optimal substructure) 특성을 가지는 문제들을 해결하는 데 강점이 있다. 즉, 한번의 선택이 다음 선택에는 전혀 무관한 값이어야 하며 매 순간의 최적해가 문제에 대한 최적해여야 한다는 의미이다.

 

 

출처 ]

나무위키 : 그리디 알고리즘

 

 

참고문제]

C언어 232제] 유리 구슬(Marbles)

 

 

 

 

 

※ 10월 25일은 독도의 날입니다.

대한민국의 아름다운 영토, 독도의 여름