CodeLog
Greedy Algorithm(그리디 알고리즘) 개념, 추천 문제 본문
저번 포스팅 #1 에서 언급했듯이 이번 포스팅은 알고리즘 유형 학습 중 첫 번째 알고리즘인 '그리디 알고리즘(Greedy Algorithm)'의 개념과 문제를 풀기 전 알아야 하는 사전 지식에 대하여 작성해보려 한다.
1. 그리디 알고리즘(탐욕법, 탐욕 알고리즘)
그리디 알고리즘은 Greedy(탐욕, 욕심쟁이)라는 이름처럼 지금 당장 최적인 답을 선택하는 과정을 반복하여 결과를 도출하는 알고리즘이다.
그리디 알고리즘은 말 그대로 각 단계에서 미래를 생각하지 않고, 그 순간 가장 최선의 선택을 하는 기법이기 때문에 종합적인 결과에 대해서는 최적의 해를 보장할 수 없다. (지역적(local)으로는 최적의 선택이지만 이를 반복하더라도 전체적(global)으로는 최적의 해가 아닐 수 있음)
2. 그리디 알고리즘의 장점
최적의 해를 보장할 수 없음에도 Greedy 알고리즘을 사용하는 이유는 해당 알고리즘의 계산 속도가 매우 빠르기 때문이다.
<3. 그리디 알고리즘의 활용>부분에서 언급할 그리디 알고리즘을 적용하여 최적해를 구할 수 있는 문제 유형들에서는 Dynamic Programming 등 타 알고리즘보다 빠른 속도로 최적해를 도출할 수 있다.
따라서 <3. 그리디 알고리즘의 활용> 부분에서 그리디 알고리즘을 적용할 수 있는 문제 유형에 대해 이해한다면 그리디 알고리즘을 이용하여 효율적으로 최적해를 찾을 수 있을 것이다.
3. 그리디 알고리즘의 활용
앞서 말했듯이 그리디 알고리즘은 종합적인 결과에서 최적의 해를 보장할 수 없다.
따라서 그리디 알고리즘을 적용하여 해결할 수 있는 문제 유형을 알아두는 것이 그리디 알고리즘을 활용하는 데 큰 도움을 줄 것이다.
그리디 알고리즘을 적용하여 최적해를 구할 수 있는 문제는 다음 두 조건을 만족한다.
1. greedy choice property: 현재 선택이 이 후의 선택에 영향을 주지 않음
2. optimal substructure: 매 순간의 최적의 해가 문제 전체에 대한 최적의 해여야 함
그리디 알고리즘을 적용하여 최적해를 구할 수 있는 간단한 문제인 동전 문제를 예시로 해당 두 조건을 설명하겠다.
( 동전 문제 )
지불해야 하는 값이 x 원 일 때 1원, 50원, 100원, 500원 동전을 이용해 값을 지불하시오.(사용되는 동전의 수가 최소가 되어야 함)
해당 문제는 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현이 가능하다.
그리디 알고리즘으로 문제를 해결할 때 500원의 개수, 100원의 개수, 50원의 개수, 1원의 개수 총 4번의 선택을 하게 되는데 각 선택에서 지불해야 하는 남은 금액을 최대로 채울 수 있는 개수를 선택하면 된다.
각 선택이 이전 선택에 관계없이 나머지 금액을 최대로 채울 수 있는 동전의 갯수를 선택하기 때문에 현재 선택이 이후의 선택에 영향을 주지 않는다는 greedy choice property 조건을 만족하며, 500원 ->100원->50원->10원, 큰 동전에 먼저 선택권을 부여하기 때문에 매 순간 나머지 금액을 최대로 채우는 선택이 결국 가장 최소의 동전 개수를 도출한다는 점에서 optimal substructure 조건을 만족한다고 할 수 있다.
만약 4870원이라는 금액을 지불해야 하는 경우
1) 4870//500, 즉 9개의 500원 동전으로 4500원(해당 금액을 넘지 않으면서 500원으로 지불할 수 있는 최대 금액)을 지불한다.
2) (4870-4500)//100, 즉 3개의 동전으로 300원을 지불한다.
3) (370-300)//50, 즉 1개의 동전으로 50원을 지불한다.
4) (70-50)//10, 즉 2개의 동전으로 20원을 지불한다.
4 단계를 거치며 4870원이라는 금액을 지불하기 위해 사용해야 하는 최소 동전 수는 15개임을 구할 수 있다.
-> 동전 문제에 대한 소스코드(python)
def min_coin_count(value, coin_list):
total_coin_count = 0
details = list()
coin_list.sort(reverse=True)
for coin in coin_list:
coin_num = value // coin
total_coin_count += coin_num
value -= coin_num * coin
details.append([coin, coin_num])
return total_coin_count, details다음 두 조건을 만족하는 경우 그리디 알고리즘을 통해 최적 해를 구할 수 있다.
위 조건이 만족하지 않아도 그리디 알고리즘을 근사 알고리즘으로 사용하는 경우가 있다.
앞서 말했듯이 그리디 알고리즘은 계산 속도가 매우 빠른 알고리즘 중 하나이다. 또한 local, 지역적으로 최적의 선택을 반복하기 때문에 global, 전체적인 최적해를 보장하지는 못하더라도 어느 정도까지 최적에 가까운 해를 구할 수 있다. 이렇듯 어느 정도 적합한 수준의 해답을 알려주기 때문에 근사 알고리즘으로 그리디 알고리즘을 사용하는 경우가 있지만 '어느 정도'까지 최적해에 가까운 해를 구할 수 있는지를 보장하기 위해 증명이 필요하다.
4. 그리디 알고리즘 문제 공식
추후 그리디 알고리즘 추천 문제를 풀면서 그리디 알고리즘 문제에 접근하고, 해결하는 나만의 공식, 방법을 기록하기 위한 파트이다. 알고리즘 추천 문제를 거의 다 풀 때쯤 추가할 예정이다.
5. 그리디 알고리즘 추천 문제
다음 포스팅부터 그리디 알고리즘에 대한 문제를 풀이할 예정이다.
풀이할 문제 목록은 다음과 같다. (수록된 모든 문제는 백준 온라인 저지 사이트의 문제이다.)
해당 문제 리스트는 다음 블로그와 사이트의 그리디 알고리즘 추천 문제를 참고하여 작성되었다.
(plzrun.tistory.com/entry/알고리즘-문제풀이PS-시작하기, www.acmicpc.net/step/33, https://covenant.tistory.com/131)
해당 포스트의 내용은 다음 사이트를 참고하여 작성되었다.
https://ko.wikipedia.org/wiki/%ED%83%90%EC%9A%95_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
https://namu.wiki/w/%EA%B7%B8%EB%A6%AC%EB%94%94%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98
https://ratsgo.github.io/data%20structure&algorithm/2017/11/22/greedy/
설명에 잘못된 부분이 있거나 질문 사항이 있으시다면 언제든지 댓글 남겨주세요 :)
다음은 그리디 알고리즘 문제 풀이로 돌아오겠습니다-!
'Algorithm > Greedy Algorithm' 카테고리의 다른 글
| [그리디 알고리즘] 백준 11000번 강의실 배정 (0) | 2020.08.28 |
|---|---|
| [그리디 알고리즘] 백준 1783번 병든 나이트 (1) | 2020.08.26 |
| [그리디 알고리즘] 백준 10610번 30 (0) | 2020.08.26 |
| [그리디 알고리즘] 백준 2875번 대회 or 인턴 (0) | 2020.08.26 |
| [그리디 알고리즘] 백준 11047번 동전0 (0) | 2020.08.26 |
