[ 이것이 취업을 위한 코딩 테스트다 with 파이썬 ] Chapter 03 그리디 - 이론과 예제

1 _ 그리디 알고리즘 문제 유형

• 그리디 = 탐욕법
• 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 문제에서 '가장 큰 순서대로', '가장 작은 순서대로' 와 같은 기준을 제시해 주는 경우 사용
• 정렬 알고리즘과 자주 짝을 이루어 출제

 

 

---

2 _ 그리디 알고리즘 설명

2 - 1 ) 예제

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

 

2 - 2 ) 예제 해설

• 주요 포인트
  가장 큰 화폐 단위부터 돈을 거슬러 주는 것
• 문제 알고리즘
  거슬러 줘야 할 총 돈: N, 동전의 개수: Q, 계산 과정 중 남은 돈: R 이라 가정하자.

1. N = 500*Q1 + R1 // Q1: 500원의 개수, R1: 500원으로 거슬러 주고 여전히 남은 돈
2. R1 = 100*Q2 + R2 // Q2: 100원의 개수, R2: 100원으로 거슬러 주고 여전히 남은 돈
3. R2 = 50*Q3 + R3 // Q3: 50원의 개수, R3: 50원으로 거슬러 주고 여전히 남은 돈
4. R3 = 10*Q4 + R4 // Q4: 10원의 개수, R4: 10원으로 거슬러 주고 여전히 남은 돈

이때, R4 = 0 이어야 한다.
거슬러줘야 할 동전의 최소 개수 = Q1 + Q2 + Q3 + Q4

 

2 - 3 ) 예제 코드

• N = 1260원이라 가정

n = 1260
count = 0

coin_types = [500, 100, 50, 10]

for coin in coin_types:
    count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    n %= coin # 해당 화폐로 거슬러 준 후, 여전히 남은 돈을 n 에 대입 


print(count)

 

2 - 4 ) 예제 코드의 시간 복잡도

• O(K)
• 화폐의 종류만큼 반복해야 하므로, 화폐 종류를 K개라 하면 시간 복잡도는 O(K) 가 된다.

 

 

---

3 _ 그리디 알고리즘의 정당성

• 그리디 알고리즘은, 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때 매우 효과적이고 직관적이다.
• 그러므로 그리디를 이용한 해법이 정당한지 검토해보는 것은 중요하다.
• 예를 들어, 다음과 같은 경우는 그리디 알고리즘이 정당할 수 없다.  

 

화폐 단위가 500원, 400원, 100원인 경우가 있다고 가정하자. 우리는 800원을 거슬러 줘야한다.
이때, 그리디 알고리즘을 이용하면, 500원 1개, 100원 3개가 되므로 동전의 최소 개수는 4개가 된다.
하지만, 400원 2개는 800원이 되므로 사실상 동전의 최소 개수는 2개 이다.
이처럼 그리디 알고리즘을 적용시켰을 때, 그 해법이 정당하지 않을 수 있다.  

• 따라서 대부분의 그리디 알고리즘 문제에서는 최소한의 아이디어를 떠올리고, 이것이 정당한지에 대한 검토를 하여 답을 도출해야 한다.

 

 

---

위 내용은 저자 나동빈의 < 이것이 취업을 위한 코딩 테스트다 with 파이썬 > 을 읽고, 공부한 내용입니다.

https://book.naver.com/bookdb/book_detail.nhn?bid=16439154

이것이 취업을 위한 코딩 테스트다 with 파이썬