[이코테] 그리디(greedy)

코딩테스트 공부 해보자 해보자 한 게 언젠데 그걸 계속 미루고 지금가지 와버렸네.. 아우 이제 진짜 열심히 해보자 파이팅! 일단 이코테 교재에 있는 알고리즘을 다 정리하고 교재에 있는 문제들 풀어야겠다. 그 이후엔 하루에 풀 문제 개수를 정해놓고 백준 문제들을 풀어야겠다. 파이팅!

---

03 그리디 ->오늘 마스터하자!

04 구현

05 DFS/BFS

06 정렬

07 이진 탐색

08 다이나믹 프로그래밍

09 최단 경로

10 그래프 이론

---

그리디(Greedy)는 현재 상황에서 지금 당장 좋은 것만 고르는 알고리즘이다. 이 알고리즘은 매 순간 가장 좋아 보이는 것을 선택한다. 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

그리디 알고리즘은 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형이다. 최단 경로 문제들은 사용법을 이미 알고 있어야 풀 수 있는 것과 다르다. 그러나 그리디 알고리즘은 문제 출제의 폭이 매우 넓기 때문에 단순 암기를 통해 모든 문제를 해결하기가 어렵다. 많은 유형을 접해보고 훈련을 해야 한다. 

문제를 봤을 때 현재 상황에서 가장 좋은 것만 선택해서 문제를 풀 수 있는지 파악할 수 있어야 한다. 그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서  '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시한다. 정렬 알고리즘을 사용했을 때 이 기준을 만족시킬 수 있으므로 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제된다.

---

그리디 알고리즘 문제의 대표로 거스름돈 문제가 있다.

500원, 100원, 50원, 10원짜리 동전이 무한히 존재할 때 손님에게 거슬러 줘야 할 동전의 최소 개수는?

이런 문제는 그리디 알고리즘을 이용해서 풀 수 있다. 왜냐하면 '가장 큰 화폐 단위부터' 돈을 거슬러주면 되기 때문이다. 500원을 사용해서 최대로 거슬러주고, 그 다음 100원으로 최대한 거슬러주고, 50원, 10원의 순서대로 최대로 거슬러준다. 이렇게 거슬러주면 동전의 개수는 최소가 된다. 

 

1260원을 거슬러줘야 하는 경우 파이썬으로 코드를 짜보자.

n = 1260
count = 0

coins = [500, 100, 50, 10]

for coin in coins:
  while (n >= coin):
    n -= coin
    count += 1

print(count)

나는 이렇게 짰는데 책에는 아래의 코드가 나와있다.

n = 1260
count = 0

coins = [500, 100, 50, 10]

for coin in coins:
  count += n // coin
  n %= coin

print(count)

500원, 100원, 50원, 10원 각각을 몇 개씩 거슬러줄지 구할 때, 나는 while을 사용했다. 이와 달리 책에서는 직접 계산을 통해서 그 값을 구했다. 책처럼 하는 것이 시간 복잡도가 작기 때문에 이 방법을 사용하는게 좋겠다.

 

거스름돈 문제는 동전의 큰 단위가 항상 작은 단위의 배수이기 때문에 그리디 알고리즘으로 해결할 수 있다.