[알고리즘] - 그리디 (탐욕) 알고리즘

그리디 알고리즘

현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다.

즉, 현재 상태에서 선택할 수 있는 방법 중에 최선의 선택을 계속 하다보면 전체 문제에 대한 최선의 선택지가 나올것이라고 가정한다.

 

예를들어 아래와 같이 1개의 문제에서 5가지의 시점이 존재한다고 가정해본다.

¹ best

² best

³ best

⁴ best

⁵ best

1 ~ 5 총 5가지 시점에서 각 시점의 최선의 해를 선택하여 전체를 풀어나간다.

→ 위와 같이 풀어 나가다 보면 전체를 푸는 가장 최선의 해가 나올것이라는것이다. 라고 가정하면서 푸는 알고리즘

 

그리디 알고리즘의 단점

전체 시점을 총 아울렀을 때 항상 최적의 해를 보장하지는 않는다.

코딩 테스트에서는 항상 최적의 해, 최고의 값의 출력을 요구한다.

그리디 알고리즘을 사용하면 최적의 해가 나올 수도, 나오지 않을 수도 있다.

(그리디 알고리즘으로 풀었을 때 최적의 해 도출 가능/불가능한 문제가 존재하기 때문)

따라서 실제로 문제를 풀 때 그리디 알고리즘을 적용해도 되는지, 안되는지를 먼저 판단해야 한다.

 

핵심 이론

아래와 같이 3 단계를 반복하면서 문제를 해결한다.

1. 해 선택
   현재 상태에서 가장 최선이라고 생각되는 해를 선택
2. 적절성 검사
   현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지를 검사
   (전체 문제를 푸는데 적절한 해인지 검사)
3. 해 검사
   현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사
   
   • 전체 문제를 해결하지 못한다면 1. 해 선택 으로 돌아가 같은 과정을 반복
   • 전체 문제를 해결했다면 더이상 그리디 알고리즘을 수행하지 않고 탐색 프로세스 종료

 

문제 유형

Do it! 문제 032 / 036	출저	난이도	시간제한	문제풀이 링크
동전 개수의 최솟값 구하기	백준 온라인 저지 11047번	실버 1	1초	유투브 http://www.youtube.com/watch?v=nCcOTgrhgRU 블로그
최솟값을 만드는 괄호 배치 찾기	백준 온라인 저지 1541번	실버 2	2초	유투브 http://www.youtube.com/watch?v=s14vkkAvLRI 블로그