1. 그리디 알고리즘
•
그리디 알고리즘은 매 순간에서 가장 최선의 선택을 하여 답을 구하는 알고리즘이다.
•
그리디 알고리즘을 사용하려면 문제가 아래의 조건을 만족해야 한다.
매 순간에서의 최선의 선택 = 문제에서의 최적해
예시1) 그리디 알고리즘 사용 가능
[문제]
동전 1원, 2원, 4원을 가지고 N원을 만들어야 한다.
최소한의 동전의 개수로 N원을 만드는 경우를 출력하는 프로그램을 적성하시오. 답이 여러 가지인 경우 아무 경우나 출력하시오.
(단, N은 1,000,000 이하의 자연수이고, 시간 제한은 1초이다.)
시간 제한이 1초이므로, 약 1억 번의 연산을 넘기면 안 됨.
•
현재 상황에서 가능한 큰 수의 동전을 사용하는 그리디한 풀이로 해결할 수 있다.
•
시간 복잡도:
python
예시2) 그리디 알고리즘 사용 불가능
[문제]
동전 1원, 3원, 4원을 가지고 N원을 만들어야 한다.
최소한의 동전의 개수로 N원을 만드는 경우를 출력하는 프로그램을 적성하시오. 답이 여러 가지인 경우 아무 경우나 출력하시오.
(단, N은 1,000,000 이하의 자연수이고, 시간 제한은 1초이다.)
시간 제한이 1초이므로, 약 1억 번의 연산을 넘기면 안 됨.
•
이 경우는 매 순간에서의 최선의 선택이 문제의 최적해와 다르므로 그리디하게 풀 수 없다.
반례: N=6
•
그리디 접근: 4원 + 1원 + 1원 = 3개
•
최적의 해: 3원 + 3원 = 2개
•
아래와 같이 브루트 포스적인 풀이로 풀어도 시간 초과가 나게 된다.
◦
1a + 3b + 4c = N 을 만족하는 모든 순서쌍에 대해 살펴보는 풀이
◦
시간 복잡도:
python
2. 실제 문제에서 그리디 알고리즘
•
문제를 보고 그리디한 풀이가 가능한지 확인
◦
매 순간에서의 최선의 선택이 문제의 최적해와 일치하는지 확인
•
그리디한 풀이로 풀 수 없는 경우
◦
매 순간에서의 최선의 선택이 문제의 최적해와 일치하지 않는 경우에 해당
◦
브루트포스, DP, 수학과 같은 다른 방식의 접근이 필요함
심화 내용
예시2 의 문제를 브루트 포스적으로 풀 수 있다.