Greedy algorithm #

Greedy algorithm(탐욕 or 욕심쟁이 알고리즘) #

Greedy algorithm은 어떤 문제에 대한 최적의 결괏값 또는 해결방안을 찾기 위해 사용하는 메소드 중 하나로, 순간마다 최적의 답이라고 판단되는 대상을 순차적으로 선택해나가는 방식이다. 전체적인 상황을 보고 판단하는 것이 아니므로 이 방식을 통해 얻어낸 최종 결과가 최적의 해라는 보장은 없지만, 복잡하지 않고 가장 빠르게 답이 있는 쪽으로 근접해 갈 수 있어서 신속하게 근사치를 구해야 하는 문제에 활용하기에 적합하다.

Divide & Conquer 방식과의 차이 #

Divide & Conquer 방식은 큰 문제를 작은 단위로 나누어 해결하는 방식의 algorithm 이다. 큰 단위를 작은 단위로 쪼개어 하나씩 풀어나간다는 점에서 Divide & Conquer와 Greedy algorithm은 비슷한 면이 있지만, 큰 단위를 작은 단위로 나누는 방식에서 Divide & Conquer는 큰 문제와 동일한 속성을 지닌 작은 단위의 문제로 대상의 규모를 축소시킨 상태에서 해결책을 찾아 이를 확장하며 적용하는 식이고 Greedy의 경우에는 지금 바로 앞에 마주한 부분부터 해결해나가는 식이라는 점에서 차이가 있다. 따라서 두 algorithm은 서로 다른 성격의 문제를 해결하는 데 사용된다. Greedy algorithm은 최단거리(Shortest path)를 찾는 문제처럼 시작 점과 종료 점이 명시된 문제에서 빠르게 종료 점에 도달하고자 하는 상황에서, Divide & Conquer는 데이터 정렬 문제와 같이 군집에 특정 규칙을 적용한 결과를 얻고자 할 때 활용된다.

Greedy algorithm 예제 #

가장 많이 이용되는 예는 우리가 사용하는 지폐나 동전을 이용하여 정해진 금액(예를 들면 거스름돈)을 구성하는 문제이다. 이때 최적의 해는 가장 적은 수의 동전과 지폐로 해당 액수를 구성하는 방법이라고 할 수 있다. 구성할 금액을 n이라고 한다면, Greedy algorithm은 내가 가지고 있는 동전이나 지폐 중에서 n보다 작으면서 가장 큰 것(이것이 현시점에서 가장 최상의 선택)을 선택하는 식으로 진행된다. 거스름돈의 예가 바로 Greedy algorithm의 특징이 가장 잘 드러나는 예라고 할 수 있다.

우리가 100원, 50원, 10원 동전을 여러 개 가지고 있는 상황에서 140원의 거스름돈을 만들어야 하는 상황이라고 한다면 Greedy algorithm에서는 우선 140원보다는 작으면서 후보 목록 중에서는 가장 큰 액수인 100원짜리 동전을 선택한다. 그런 다음 남아있는 40원보다 작으면서 큰 금액인 10원짜리 동전을 4번 연속으로 채워나가면 140원이 만들어지게 된다.

실제 동전이나 지폐의 경우에는 모두가 5의 배수이거나 10의 배수로 이루어져 있기 때문에 어떠한 하위 단위를 이용하더라도 상위 단위를 완벽하게 구성할 수 있다. 예를 들면, 만원은 10원 동전 1,000개, 100원 동전 100개, 1,000원 지폐 10장이 모이면 구성할 수 있는 구조이기 때문에 동전과 지폐의 경우에는 Greedy algorithm을 이용해서 최적해를 구할 수 있는 예에 해당한다고 볼 수 있다. 그렇지만 하위 요소의 조합으로 상위요소를 완벽하게 구성할 수 없는 상황에서는 Greedy algorithm은 최적의 해를 구하지 못하게 된다.

동전 중에 70원 동전이 존재한다고 가정하고 140원을 구성하는 위의 문제를 풀어간다면, 70원 동전 2개를 이용해서 140원을 구성하는 것이 최소의 동전을 이용하는 최적의 답이 될 수 있다. 이런 경우에는 Greedy algorithm이 좋은 선택이 되지 못하는 것이다.

Greedy algorithm 개념코드 #

tempP = P                   // tempP 는 현재 남아있는 문제
while tempP not empty loop  // tempP가 남아있으면 반복 수행
    in subproblem tempP, decide greedy choice C // tempP서 greedy로 해결책 C를 선택(C는 현재 선택가능한 최적의 해)
    Add value of C to solution // 해결책에 C의 값을 적용
    tempP := subproblem tempP reduced based on choice C // 남은 문제의 축소
end loop

Incoming Links #

Related Articles (Article 0) #

• Hot topics