알고리즘 / 자료구조’ 시리즈

[이.취.코] Chap 3. 그리디 - 개념

  • 0
  • 0
0
0

1. 당장 좋은 것만 선택하는 그리디

그리디(Greedy) 알고리즘(탐욕법)은 단순하지만 강력한 문제 해결 방법이다.

탐욕적이라는 말은 현재 상황에서 지금 당장 좋은 것만 고르는 방법을 의미한다. 매 순간 가장 좋아 보이는 것만 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

다른 알고리즘과 비교했을 때 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형이라는 특징이 있다.

사전 지식 없이도 풀 수 있는 문제도 있겠지만, 많은 유형을 접해보고 문제를 풀어보며 훈련을 해야 한다.

보통 코딩테스트에서 출제되는 그리디 알고리즘 유형의 문제는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다. 특정한 문제를 만났을 때 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지를 파악할 수 있어야 한다.

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 가장 큰 순서대로, 가장 작은 순서대로와 같은 기준을 알게 모르게 제시해준다. 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로, 그리디 알고리즘은 자주 정렬 알고리즘과 짝을 이뤄 출제된다.

A. 예제 1. 거스름돈

a. 문제
  • 거스름돈(500원, 100원, 50원, 10원)이 무한하고 가정.
  • 손님에게 거슬러 줘야 할 돈이 N원.
    • N은 항상 10의 배수
  • 거술러줘야 할 동전의 최소 개수를 구하라.
b. 문제 해설

가장 큰 화폐 단위부터 돈을 거슬러 주는 것이라는 간단한 아이디어만 떠올릴 수 있으면 문제를 해결할 수 있다.

화폐의 종류만큼 반복을 수행해야 한다. 화폐의 종류가 K개라고 할 때 d.책 답안의 소스 코드의 시간 복잡도는 O(K)다.

이 알고리즘의 시간 복잡도는 동전의 총 종류에만 영향을 받고, 거슬러 줘야 하는 금액의 크기와는 무관하다는 것을 알 수 있다.

c. 내 답안

n = 1260
count = 0

for i in [500, 100, 50, 10]:
  count = count + (n // i)
  n = n - (n // i) * i

print(count)

d. 책 답안

n = 1260
count = 0
coin_types = [500, 100, 50, 10]

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

print(count)

e. 회고

반성

  • coin_types = [500, 100, 50, 10]
    • coin_types를 선언하지 않고 하드 코딩한 점.
  • n %= coin
    • 좀 더 간단한 방법이 있음에도 돌아간 점.

결론

  • 코딩 습관을 조금만 더 고치자.

B. 그리디 알고리즘의 정당성

탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 떄는 매우 효과적이고 직관적이다.

그리디 알고리즘으로 문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다. 거스름돈 문제를 그리디 알고리즘으로 해결할 수 있는 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문이다.

대부분의 그리디 알고리즘 문제에서는 이처럼 문제 풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출할 수 있다.

코딩 테스트 문제 유형을 바로 파악하기 어렵다면 그리디 알고리즘을 의심하고, 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 고민하자. 그리디 알고리즘으로 해결 방법을 찾을 수 없다면, 다이나믹 프로그래밍이나 그래프 알고리즘 등으로 해결을 고민하자.

기업의 코딩 테스트를 안정적으로 통과하려면 다음 문제에 대해 문제별 아이디어를 떠올리고 코드로 작성하기까지 30분 이내로 소요되어야 한다.

참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

#코딩테스트 #파이썬 #나동빈 #한빛미디어 #그리디 #개념

0분전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.