그리디 알고리즘(백준 알고리즘 11399)

♣ 정의

매 선택에서 가장 최적인 답을 선택해서 적합한 결과를 만들자는 의미의 알고리즘

즉 각 부분에서의 최적의 답을 모두 모았을 때 종합적으로도 최적의 결과가 나오는 문제에 적절한 알고리즘. 

 

 

그리디 알고리즘의 두 가지 특성을 가지는 문제를 푸는 데 적합한 방법임

: 탐욕선택속성, 최적부분구조

 

서울 - 대구 - 부산 경로로 갈 때 가장 짧게 갈 수 있는 경로를 찾는 문제를 예로 들 수 있음

서울 - 대구의 최적 거리는 200km이고 대구 - 부산의 최적 거리는 80km로 종합적으로 280km를 가는 것이 가장 짧은 경로

 

1. 탐욕선택속성 

각 단계에서 ‘최선의 선택’을 했을 때 전체 문제에 대한 최적해를 구할 수 있는 경우를 의미함. 위에서는 서울-대구로 가는 경로 중 가장 적합한 200km를 선택하는 최선의 선택을 하고 대구-부산으로 가는 경로 중 가장 적합한 80km를 선택하는 최선의 선택을 하면 전체적으로도 가장 최선의 결과인 280km가 나옴.

또한 각 단계의 선택이 다음 단계의 선택에 영향을 주지 않아야 함. 서울-대구로 갈 때의 경로 선택이 대구-부산으로 갈 때의 경로 선택에 영향을 주지 않음. 

 

2. 최적부분구조

서울-대구를 가는 가장 적합한 경로와 대구-부산을 가는 가장 적합한 경로를 합치면 서울-대구-부산 경로의 가장 최적의 경로가 됨. 즉 전체 문제를 작은 부분 문제로 나누어 각 부분 문제에서 최적의 해를 구한 후 이를 조합하여 전체 문제의 최적해를 구하는 것을 의미함. 

 

♣ 그리디 알고리즘의 절차

1. Selection Procedure

현재 상태에서 최적의 상태를 선택하기. 이 선택은 바뀌지 않음

 

2. Feasibility Check

선택한 항목이 조건을 만족시키는지 확인하기

 

3. Solution Check

모든 선택을 완료한 후 이 선택의 모음이 최적해인지 확인하기

 

♣ 문제 적용(백준 11399번)

 

돈을 뽑는 시간이 적게 걸리는 사람일수록 앞에 세우는 게 유리하다. 모든 사람들이 거쳐가는 시간이 되기 때문에 그 시간이 짧을수록 전체 시간도 짧아진다. 

 

1. Selection Procedure

돈을 뽑는 시간이 가장 짧은 사람부터 선택한다. 이 사람이 돈을 뽑는 시간이 몇 명의 사람에게 적용되는지를 계산하여 전체 시간에 더한다. 

 

2. Feasibility Check

1단계 실행 후, 그 다음으로 시간이 짧은 사람을 선택한다. 

 

3. Solution Check

모두 더한 시간의 합이 최소의 시간과 같은지 확인한다. 

 

 

♣ 주의점

그리디 알고리즘을 사용하면 각 부분에서는 최선의 선택이지만 종합적으로는 최적의 결과가 아닌 경우가 종종 있음. 

따라서 그리디 알고리즘을 사용한 후에 결과가 실제로 최적해인지 검증해야 함. 

 

♣ DP ?

블로그 중 그리디 알고리즘과 DP를 비교한 내용이 있었음. DP 문제는 한 번도 안 풀어봤는데 앞으로 공부하면서 그리디 알고리즘과 비교해봐야겠다 .

 

 

♣ 참고

https://ko.wikipedia.org/wiki/%ED%83%90%EC%9A%95_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

탐욕 알고리즘 - 위키백과, 우리 모두의 백과사전

https://lucy1215.tistory.com/12

[알고리즘] 그리디 알고리즘 (Greedy Algorithm)

 

https://januaryman.tistory.com/406

[Section2] [코딩테스트 준비] 탐욕 알고리즘 (Greedy)

https://adjh54.tistory.com/212

[Java/알고리즘] 그리디 알고리즘(탐욕법, Greedy Algorithm) 이해하기