그리디 (Greedy)
•
탐욕적(Greedy) 즉, 현재 상황에서 지금 당장 좋은 것만 고르는 방법
◦
현재의 선택이 나중에 미칠 영향은 신경쓰지 않음.
그리디 알고리즘 유형 문제의 특징
1.
일반적으로 그리디 알고리즘 문제는 유형이 다양하기 때문에 암기로만은 해결하기 힘들다.
•
최단 경로 찾기와 같은 문제는 플로이드 워셜 or 다익스트라 같은 특정 알고리즘을 사전에 숙지하고 있어야 하기도 함.
2.
문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력 즉, 창의력이 요구된다.
•
단순히 현재 상황에서 가장좋아 보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는 지의 검토가 필요
→ 해법의 정당성 분석이 중요!
3.
기준에 따라 가장 좋은 것을 선택하는 알고리즘으로, 그 기준이 알게 모르게 같이 제시된다.
•
ex) 가장 큰 순서대로, 가장 작은 순서대로..
→ 이러한 기준들은 정렬 알고리즘으로 만족시킬 수 있는 기준이므로,
그리디는 자주 정렬 알고리즘과 쌍을 이룸.
예제 : 거스름돈
당신은 음식점에서 카운터를 보고 있는 알바생이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 고객에게 줄 거스름돈이 N원일 때 필요한 동전의 최소 개수를 구하라. 단, 거스름돈 N은 항상 10의 배수이다.
해결에 필요한 핵심 아이디어 : 가장 큰 화폐 단위의 동전부터 사용해야 최소 개수로 거스름돈을 줄 수 있다!
해결 시나리오
1.
다음 변수들이 필요
•
거스름 금액(n) / 필요한 동전의 최소 개수(count) / 동전 종류를 담을 리스트(list) → 총 3가지
2.
거스름돈에 필요한 동전의 최소 개수 계산
•
가장 큰 단위의 동전(500)부터 시작
•
거스름 금액을 500으로 나눈 몫의 값은 카운트
•
그 나머지 값을 거스름 금액(n)으로 새롭게 저장
•
위 과정을 반복
3.
필요한 동전의 최소 개수(count)를 출력
답안
시간 복잡도 : O(n)
•
동전 종류 수 만큼 반복되야 하므로, 동전의 종류에만 영향을 받는다!
그리디 알고리즘의 정당성
•
그리디 알고리즘 유형은 그 풀이의 정당성 확인이 매우 중요!
•
거스름돈 문제와 같은 경우, 가장 큰 단위의 동전이 나머지 단위의 동전의 배수이기 때문에 그리디 알고리즘을 적용해도 정당하다.
◦
배수가 아닐 경우? (동전 종류가 500원, 400원, 100원)
▪
거스름돈 : 1200원
▪
그리디 방식 → 필요한 동전 개수 : 4개 (500*2, 100*2)
▪
최적의 해 → 필요한 동전 개수 : 3개 (400*3)
본 글은 ‘이것이 코딩 테스트다 with 파이썬’을 읽고 공부한 내용을 바탕으로 작성되었습니다.
다음의 컨텐츠들을 이용하시면 더 많고 자세한 내용을 얻을 수 있습니다.
