Link Search Menu Expand Document
그리디 알고리즘 (Greedy Algorithm)
Table of contents
  1. 예제 - 거스름돈
  2. 이것이 코딩테스트다 - 실전 문제
    1. 큰 수의 법칙 (p.92)
    2. 숫자 카드 게임 (p.96)
    3. 1이 될 때까지 (p.99)

그리디 알고리즘은 탐욕법이라고도 한다. 단순 무식하게 탐욕적으로 문제를 푸는 알고리즘이기 때문이다. 이 알고리즘은 현재 상황에서 지금 당장 좋은 것만 고르는 방법으로 미래를 생각하지 않고 지금 이 순간 좋아보이는 것만 선택한다.

그리디 알고리즘의 문제는 보통 가장 큰 순서대로, 가장 작은 순서대로 등과 같은 문제에서의 기준에 따라 푸는 경우가 많다. 따라서 정렬 알고리즘을 이용하면 쉽게 풀 수 있는 경우가 많다.

예제 - 거스름돈

거스름돈 문제는 그리디 알고리즘을 설명할 때 사용하는 대표적인 예시이다. 거스름돈으로 사용할 동전의 종류는 500원, 100원, 50원, 10원짜리가 있다. 이 때 거스름돈 N원을 만들 수 있는 동전의 최소 개수를 구하는 것이 문제이다. 이 경우 최소의 개수를 돌려줘야 하기 때문에 가장 큰 화폐 단위부터 돈을 거슬러 주는 것 이 핵심이다.

거스름돈 예제 풀이

n = 1260
count = 0

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

for coin in coin_types:
	# 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
	count += n // coin
	n %= coin

print(count)
# 6 (500원 2개, 100원 2개, 50원 1개, 10원 1개)

이것이 코딩테스트다 - 실전 문제

책 풀이는 input으로 받는 풀이이지만, 개인적으로는 프로그래머스에서 진행하는 코딩테스트 방식이 익숙해 함수로 만들어서 풀었다. 그러다보니 배열을 넣거나 그런 점이 조금 억지스럽지만, 그래도 책 풀이와 과정이 거의 똑같은 것으로 보아 알고리즘은 제대로 구현한 듯 하다.

큰 수의 법칙 (p.92)

  • 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙
  • 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 특징
  • 배열의 크기 N, 숫자가 더해지는 횟수 M, K가 주어질 때 큰수의 법칙에 따른 결과 출력

N=5, M=8, K=3이고, 배열은 [2, 4, 5, 4, 6]일 때 46 출력

def solution(n, m, k) :
    input_list = [2, 4, 5, 4, 6]
    input_list.sort(reverse=True)

    x = m % k
    answer = (input_list[0] * (m-x)) + (input_list[1] * x)
    return answer


solution(5, 8, 3)
# 46
  • 가장 큰 수를 만들려면 가장 큰 수를 최대한 많이 더해야 한다. 하지만 중간에 K번을 초과할 수 없다는 조건이 있으므로 K번이 될 때마다 그 다음으로 큰 수를 한 번 더하고 다시 가장 큰 수를 더하면 된다. 다시 말해, 가장 큰 수를 가장 많이 더하는 것
  • 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5 + 6 + 6 = 42
  • 숫자가 더해지는 횟수 M을 연속해서 더할 수 있는 횟수 K로 나누면 2번째로 큰 수를 더하는 횟수를 알 수 있다. 그 수를 x라고 한다면 전체 횟수 M에서 x를 빼면 가장 큰 수를 더하는 횟수를 알 수 있다.
  • 배열을 오름차순으로 정렬해 가장 큰 수(0번째)를 m-x만큼 더하고, 두 번째로 큰 수(1번째)를 x만큼 더하면 결과값을 구할 수 있다.

숫자 카드 게임 (p.96)

  1. 숫자가 쓰인 카드들이 N X M 형태로 놓여 있다. 이 때 N은 행의 개수를 의미하며, M은 열의 개수를 의미
  2. 먼저 뽑고자 하는 카드가 포함되어 있는 행 선택
  3. 그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드 뽑기
  4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략 세우기

3 x 3 형태 ⇒ 첫 번째 행 [3, 1, 2], 두 번째 행 [4, 1, 4], 세 번째 행 [2, 2, 2]일 때 2를 출력

def solution (m, n) :
    data = [[3, 1, 2], [4, 1, 4], [2, 2, 2]]
    min_list = [min(data[i]) for i in range(len(data))]

    answer = max(min_list)
    return answer

solution (3, 3)
# 2
  • 최종적으로 뽑는 카드는 고른 행에서 가장 낮은 숫자의 카드이므로 각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수를 찾아야 한다
  • 행 마다 루프를 돌면서 가장 작은 수들을 넣은 리스트를 만들고, 그 안에서 다시 가장 큰 값을 찾아서 리턴하면 된다.

1이 될 때까지 (p.99)

  • 어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행한다.
    1. N에서 1을 뺀다
    2. N을 K로 나눈다
  • 단, 두 번째 연산은 N이 K로 나누어질 때만 선택할 수 있다.
  • 이때 N을 1로 만드는 최소 횟수를 구해라

N=25, K=5일 때 2를 출력

def solution(n, k) :
    count = 0

    while n != 1 :
        if n % k == 0 :
            n = n // k
            count = count + 1
        else :
            n = n -1
            count = count + 1

    return count

solution(25, 5)
# 2
  • N을 1로 만들어야 하므로 1이 될때까지 무한루프를 돌린다
  • 똑같은 수를 1로 만든다면 1씩 빼는 것보다 나누는 것이 훨씬 빠르다. (K가 2 이상이라는 조건이 있으므로) 다시 말해, 최대한 많이 나누는 것이 핵심이다.
  • 따라서 먼저 N이 K로 나누어지는지 확인해서 나누어진다면 일단 나누고, 나눌 수 없다면 나눌 수 있을 때까지 1을 빼면 된다. 그리고 모든 연산은 수행될 때마다 횟수를 하나씩 체크해야 한다. 그래서 마지막으로 1이 되었을 때, 즉 루프가 종료되었을 때 횟수를 센 값인 count를 리턴하면 된다.

Page last modified: Jan 12 2021 at 11:01 PM.