#48. Algorithm38_python) 그리디 개념 및 예제

그리디 : 당장 좋은 것만 선택하는 알고리즘

 

 

• 어떤 문제가 있을 때 단순하고 '탐욕적으로 문제를 푸는' 알고리즘
• 탐욕적 : 현재 상황에서 가장 좋은 것만 고르는 방법
• 매 순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않음
• 매우 다양한 유형이 있기 때문에 안기한다고 잘 풀 수 있는 유형이 아님
• 많이 접해보고 문제를 풀어보며 훈련을 해야 함
• 창의력, 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구함

---

예제

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

Step1) 테스트

n = 1260
count = 0

# 잔돈 종류 리스트
coin_types = [500, 100, 50, 10]

for coin in coin_types:
    count = count + n // coin     # 몫
    print(count)
    n %= coin                     # 나머지
    print(n)
    print()

print(count)


>>>
2
260

4
60

5
10

6
0

6

Step1) 테스트 : 성공

 

n = int(input("거스름 돈 : "))
count = 0

# 잔돈 종류 리스트
coin_types = [500, 100, 50, 10]

# 잔돈 큰 단위부터 차례로 확인
for coin in coin_types:
    count += n // coin        # 몫 : 큰 단위부터 동전 갯수
    n %= coin                 # 나머지 : 큰 단위 동전으로 지불한 나머지 금액

print(count)


>>>
거스름 돈 : 1260
6

---

예제

• 그리디 알고리즘을 모든 알고리즘 문제에 적용할 수 있는 건 아님
• 대부분의 문제는 그리디 알고리즘을 이용했을 때 '최적의 해'를 찾을 수 없을 가능성이 다분함
• 그리디 알고리즘으로 문제의 해법을 찾았을 때에는 그 해법이 정당한지 검토 필요
• 대부분의 그리디 알고리즘 문제에서는 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 함

---

<참조>

• 이것이 취업을 위한 코딩 테스트다 with 파이썬(나동빈, 한빛미디어)