나동빈님의 '이것이 코딩테스트다 with 파이썬'저서를 참고하며 작성하였습니다
▷그리디 알고리즘이란?
탐욕법으로 번역되는 해당 알고리즘은 현재 주어진 상황에서 가장 좋은 것만 고르는 방법이다. 문제를 보고 해당 문제를 풀 수 있는 아이디어를 떠올리는 것이 중요하다. 코테에서 많이 출제되는 유형이지만 아이디어를 생각하는 것이 중요하기 때문에 사전에 알고리즘을 외우지않아도 충분히 풀 수 있는 문제유형이다. 아이디어를 떠올린 후에는 가장 좋아보이는 걸 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토해야한다.
▷ 그리디 알고리즘 풀이법
즉 그리디 알고리즘은,
1. 최소한의 아이디어를 생각해내고,
2. 아이디어의 정당성을 분석해야한다. 다른 말로 내가 생각해낸 아이디어로 해를 구하고자 할때 최적의 해를 항상 보장할 수 있는지 검토해야한다.
▷ 거스름돈 예시
예를 들어보자.
손님에게 돈을 받으면 직원이 손님에게 최소의 동전의 사용하여 거스름돈을 거슬러 줘야한다고 생각해보자. 몇개의 동전이 최소 동전 개수가 될지 풀기위해 우리는 '가장 큰 단위부터 가능한만큼 거슬러주자'라는 아이디어를 생각해낼 수 있다. 만약 1500원 물건에 대해 손님이 1320원을 냈다면 우리는 가장 큰 단위인 500원 부터 500+500+100+100+100+10+10으로 거슬러줄 수 있다. 즉 최소동전개수는 7개이다.
그렇다면 '가장 큰 단위부터 가능한만큼 거슬러주자'라는 아이디어가 항상 최소동전개수가 7개가 되도록 만들어줄 수 있는가? 이에 대한 대답은 '만들어줄 수 있다. 왜냐하면 작은 단위의 돈의 배수가 큰 단위의 수가되기 때문이다.' 만약 동전의 단위가 500,400,20원이라면 해당 아이디어로는 최적의 해를 구할 수 있는 정당성이 만족되지 않을 것이다.
이처럼 그리디 알고리즘은 아이디어, 정당성을 항상 고려해두는 것이 중요하다. 만일 문제를 봤을 때 문제의 유형을 단번에 알지 못하겠다면 그리디 알고리즘으로 풀 수 있진 않은지 확인해보자!
다음 포스팅에서 그리디알고리즘을 적용한 문제를 풀어보고자 한다.
'python > 알고리즘 문제풀이' 카테고리의 다른 글
| 구현- 완전탐색 (0) | 2021.06.27 |
|---|---|
| 그리디 알고리즘 (2) / 큰수의법칙, 숫자카드게임, 1이될때까지 (0) | 2021.06.26 |
| 시간복잡도/ BigO표기법 (0) | 2021.06.24 |
| [프로그래머스 | 파이썬3] 키패드 누르기 (1) | 2021.05.21 |
| [프로그래머스 | 파이썬3] 로또의 최고 순위와 최저 순위 (1) | 2021.05.20 |