그리디 알고리즘

1.개념

모든 경우의 수를 전부 탐색해 보지 않고, 어떤 기준(전략)으로 순서대로  하나씩 선택해 나가는 방식.

최적의 해를 구하는 방식을 그리디 알고리즘이라고 한다.

 

예를 들어, 5개의 도시를 모두 한번씩만 거쳐서 여행하는 경로 중 가장 짧은 경로를 찾고 싶다고 가정하자.

가능한 모든 조합을 살표보는 방법은 5 x 4 x 3 x 2 x 1 = 120 가지 조합을 살펴봐야 한다.

10개의 도시라면 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1 = 3628800 가지 조합을 살펴봐야 한다. 너무 많다.

 

그리디 알고리즘은 어떤 적절한 기준(전략)으로 도시를 순서대로 하나씩 선택해 나가는 방식이다.

예를 들어, 임의의 도시를 하나 찍은 다음, 그 도시에서부터 시작하여, 현재 도시에서 출발하는 가장 짧은 도로로 연결된 도시를 선택하는 방식으로 도시들을 선택할 수도 있다.

 

단, 그리디 알고리즘을 사용하면, 최종 결과가 최적의 선택이라는 보장은 없고, 특별한 경우에만 가능하다.

그 순간마다 최적의 해를 구하기 때문에, 결과적으로 항상 최적해는 아니다. 

 

1) 최적해를 구할 수 있는 문제

- 수행시간이 훨씬 빠르다.

- 그에 따른 정당성이 있다.

 

2) 최적해를 구할 수 없는 문제

- 최적해가 아니어도 근사해를 찾을 때 사용한다.

- 이때는 다른 알고리즘이 더 좋은 결과인 경우가 많다.

 

2.최종 결과가 최적의 선택이 될 수 있으려면

• greedy choice property : a globally optimal solution can be arrived at by making a locally optimal (greedy) choice.
• optimal substructure : A problem exhibits optimal substructure if an optimal solution to the problem contains within its optimal solutions to subproblems.

3.그리디 알고리즘 적용 예

 

백준 11047 :: 동전 0 (거스름돈 문제) https://www.acmicpc.net/problem/11047)

백준 2931 :: 회의실 배정 (활동 선택 문제) https://www.acmicpc.net/problem/1931)