그리디 알고리즘

그리디 알고리즘이란

그리디 알고리즘이란 전에 선택했던 것과 미래에 다가올 선택에 관계없이 현재 가장 최고의 것을 선택하는 알고리즘이다. 직접적으로 명시된 제약조건을 빠르게 해결하는데 사용하고 순간순간 최적의 선택으로 솔루션에 도달한다. 그리디를 사용할 때는 항상 지금 사용하는 그리디 해결법이 최적인지 생각해야 한다. 그 순간에만 최적의 방법일 수 있고 다른 부분 문제에서는 최적의 방법이 아닐 수 있기 때문이다.

 

다음은 그리디 알고리즘으로 접근하는 것이 항상 옳은 해가 아니라는 예이다.

그리디는 항상 최적의 해가 아니다

 

그리디 설계법

1. 그 순간에 최적 상태를 고려하여 원소들을 뽑아낸다.

2. 현재 사용한 방법이 다른 부분 문제에 대하여 최적인지 고려한다.

 

예제

다음은 정해진 시간동안 최대로 들을 수 있는 강의 수를 찾는 문제이다. 주어진 강의는 다음과 같다.

	1번 강의	2번 강의	3번 강의	4번 강의	5번 강의	6번 강의
시작	1	2	4	1	5	8
끝	3	5	7	8	9	10

1. 1 ~ 3 고르기 -> +1

2. 2 ~ 5 고르기 -> 불가능 (1번 고르기에서 3에서 끝나기 때문에)

3. 4 ~ 7 고르기 -> +1

4. 1 ~ 8 고르기 -> 불가능 (3번 고르기에서 7에서 끝나기 때문에)

5. 5 ~ 9 고르기 -> 불가능 (3번 고르기에서 7에서 끝나기 때문에)

6. 8 ~10 고르기 -> +1

결과 : 3개