[알고리즘] 그리디 & 구현 / Python 파이썬

그리디 알고리즘이란

• 그리디 알고리즘(탐욕법)은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미합니다.
• 일반적인 그리디 알고리즘은 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구합니다.
• 그리디 해법은 그 정당성 분석이 중요합니다. 단순히 가장 좋아보이는 것을 반복적으로 선택해도 최적의 해를 구할 수 있는지 검토합니다.

• [문제 상황] 루트 노드부터 시작하여 거쳐 가는 노드 값의 합을 최대로 만들고 싶음
  • Q. 최적의 해는 무엇인가?

• 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많음
• 하지만 코딩 테스트에서 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서 이를 추론할 수 있어야 풀리도록 출제됨

 

 

 탐욕 알고리즘 문제를 해결하는 방법

1. 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택한다.
2. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다.
3. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

 

 

 탐욕 알고리즘을 적용하려면 문제가 다음 2가지 조건을 성립하여야 한다.

• 탐욕 알고리즘이 잘 작동하는 문제는 대부분 탐욕스런 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)이라는 두 가지 조건이 만족된다.
• 탐욕스런 선택 조건은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이며, 최적 부분 구조 조건은 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것이다.

1. 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
2. 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

 

---

 

문제 : 거스름 돈

 

문제 설명

• 당신은 음식점의 계산을 도와주는 점원입니다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정합니다.
  손님에게 거슬러 주어야 할 돈이 N원일 때 거슬러 주어야 할 동전의 최소 개수를 구하세요.
  단, 거슬러 줘야 할 돈 N은 항상 10의 배수입니다.

 

문제 해결 아이디어

• 최적의 해를 빠르게 구하기 위해서는 가장 큰 화폐 단위부터 돈을 거슬러 주면 됨
• N원을 거슬러 줘야 할 때 가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러 준다
  • 이후에 100원, 50원, 10원짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 주면 됨
• N = 1,260일 때의 예시를 확인

 

n = 1260
count = 0

#큰 단위의 화폐부터 차례대로 확인하기
array = [500,100,50,10]

for c in range(len(array)):
    count += n // array[c] #해당 돈을 각 화폐로 나눈 몫 카운트
    n %= array[c] # 다음 수로 넘어가기위해 나머지 저장

print(count)

화폐의 종류가 K라고 할 때, 소스코드의 시간복잡도는 O(K)이다.

 

주의점

(1) 문제를 처음 접했을 때 다양한 아이디어를 고려해야 한다.
(2) 동전의 단위가 서로 배수 형태가 아니었다면 탐욕법을 사용하지 못했을 것
(만약 무작위로 주어졌다면 다이나믹 프로그래밍으로 해결할 수 있음)

 

 

 

 

 

 

 

 

References

- 이것이 코딩테스트다 그리디& 구현

https://www.youtube.com/watch?v=2zjoKjt97vQ

- [알고리즘] 탐욕 알고리즘(Greedy Algorithm)

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%83%90%EC%9A%95%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-greedy-algorithm/