Search

그리디 알고리즘

그리디 (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 파이썬’을 읽고 공부한 내용을 바탕으로 작성되었습니다. 다음의 컨텐츠들을 이용하시면 더 많고 자세한 내용을 얻을 수 있습니다.