[Algorithm Study] Algorithm - Greedy algorithm

1. 그리디 알고리즘(Greedy agorithm)이란?

그리디 알고리즘은 간단히 설명하면 "매 선택에서 현재 당장 최적인 답"을 선택함으로써 전체 문제에 대하여 적합한 결과를 도출하는 알고리즘이다. 즉, 백트래킹을 통한 추가 점검 없이, 현재 조건에서 가장 적절한 선택을 했다면 다른 경우의 수는 고려하지 않는다.
그리디 알고리즘은 모든 경우에서 통하지는 않는다. 예를 들어 노드를 거쳐 가면서 마주하는 수의 합이 최대가 되도록 하는 경우를 찾는다고 해 보자.

그림에서 보듯이, '현재 상태에서의 선택'만을 고려하기 때문에 전체 문제에 대한 결과가 최적해가 되지는 않는다.

그럼에도 불구하고 그리디 알고리즘은 속도가 매우 빠르다는 장점이 있다. 따라서, 특수한 조건이 만족되었을 때 그리디 알고리즘을 사용할 수 있다.

2. 그리디 알고리즘의 정당성

그리디 알고리즘을 통해 최적해를 도출하기 위해서는 두 가지 조건을 만족해야 한다.

탐욕적 선택 속성(Greedy choice property)

탐욕적인 선택이 항상 안전하다는 것이 보장된다는 의미이다. 즉, 그리디한 선택을 했을 때 언제나 최적해가 도출된다는 것이 보장되어야 한다. 이는 현재의 선택이 다음의 선택에 영향을 주지 않는다는 것을 의미한다.

최적 부분 구조

부분 최적해(Local optimum)들이 모여 전체 최적해(Global optimum)을 구성할 수 있는 경우이다. 즉, 전체 문제가 여러 개의 부분 문제로 분할 가능하고, 이 단계 하나하나에 대한 최적해가 도출 가능해야 한다는 것이다.

참고 자료

• 알고리즘 - 그리디 알고리즘(Greedy Algorithm)
• [Algorithm] 탐욕 알고리즘 (Greedy algorithm)
• [알고리즘] 탐욕 알고리즘(Greedy Algorithm)

관련 코딩테스트 풀이

• Programmers - 구명 보트(Level 2)
• Programmers - 큰 수 만들기(Level 2)