[TAVE/이코테] ch03 그리디 | 개념 정리 | 실전 문제

참고자료: 이것이 코딩테스트다

그리디(Greedy)

📌현재 상황에서 지금 당장 좋은 것만 고르는 방법으로 탐욕법이라고도 부른다.

👉🏻문제를 읽으면 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 문구로 기준을 알게 모르게 제시해준다. 정렬 알고리즘과 짝을 이뤄 출제된다.

예제 - 거스름돈

N = 1260

def charge(N):
    coin = [500, 100, 50, 10]
    answer = 0
    while(N):
        i = 0
        answer += N / coin[i]
        N = N % coin[i]
        i += 1
    return answer

👉🏻가장 큰 화폐 단위부터 돈을 거슬러주면 된다. 남은 돈(N)이 0이 될 때까지 반복한다. 각 화폐로 나눈 몫은 동전의 개수이므로 answer에 더해주고 나머지는 남은 돈이기 때문에 다시 N에 저장한다.

📌화폐의 종류만큼 반복을 수행한다. 때문에 화폐의 종류가 K개라면 시간 복잡도는 O(K)이다.

그리디 알고리즘의 정당성

📌최적의 해를 찾을 수 없을 가능성이 다분하다.

👉🏻해당 문제도 가지고 있는 동전 중에서 큰 단위가 작은 단위의 배수가 아닐 경우 그리디로 풀 수 없다. (ex) 500원, 400원, 100원인데 800원 거슬러줘야 할 때)

실전 - 큰 수의 법칙

n, m, k = 5, 8, 3
nums = [2, 4, 5, 4, 6]

def bigNum(n, m, k, nums):
    answer = 0
    nums = sorted(nums, reverse = True)
    if nums[0] == nums[1]:
        answer += nums[0] * k
    else: 
        while m > 0:
            if m < (k + 1):
                answer += nums[0] * m
                break
            else:
                answer += nums[0] * k
                answer += nums[1]
                m -= (k + 1)
    return answer

👉🏻내 풀이의 흐름은 다음과 같다. 이 문제는 배열의 숫자가 얼마나 있던 가장 큰 2개의 수만 알아내면 된다고 생각했다. 그 두가지 숫자만 번갈아 더하면 되기 때문이다.

1. 먼저 숫자 배열을 sorted와 reverse = True를 활용해 정렬한다. 그러면 큰 숫자들이 앞으로 오게 된다.
2. 정렬된 배열의 0번째와 첫 번째 숫자가 같은지 확인한다. 만약 같다면 가장 큰 숫자가 2개 이상이고 인덱스가 다르기 때문에 번갈아 더해줘도 된다. 즉 k번 더해주면 되기 때문에 nums[0]과 k를 곱한 값을 반환한다.
3. 다음으로 숫자가 같지 않은 경우를 보자. 숫자가 같지 않을 때는 nums[0]을 k번 더한 후에 nums[1]을 한번 더하는 것까지 1세트로 보면 이 세트를 m만큼 반복하면 된다. 세트를 반복하는 도중에 m이 끝나는 경우가 있을 수 있으므로 k + 1보다 작은 경우는 nums[0]을 m번 더한다.

실전 - 숫자 카드 게임

def NumCardGame():
    row, column = input('').split(' ')
    min_card_list = []
    for card in range(int(row)):
        row_card_list = list(map(int, input('').split(' ')))
        min_card_list.append(min(row_card_list))
    print(max(min_card_list))

👉🏻나는 아래와 같이 풀었는데 생각해보니 내 풀이는 완전한 그리디가 아닌 것 같다.

1. 각 행의 최소값을 min_card_list에 저장한다.
2. min_card_list의 최댓값을 반환한다.

✍🏻그리디는 그때 그때 마다 최적의 값을 찾아야 한다. 그런데 내 방식은 최솟값을 다 모으고 나서 한 번에 최댓값을 찾는 방식이므로 그리디가 아닌 것 같고 아래 풀이가 좀 더 그리디에 가까운 것 같다!

def NumCardGame2():
    row, column = input('').split(' ')
    min_card = 0
    for card in range(int(row)):
        row_card_list = list(map(int, input('').split(' ')))
        min_card = max(min_card, min(row_card_list))
    print(min_card)

NumCardGame2()

1. min_card의 값과 각 행의 최솟값을 비교해 큰 값으로 계속 갱신해준다.

실전 - 1이 될 때까지

def toOne():
    N, K = map(int, input().split())
    answer = 0
    while(N - 1):
        if N % K == 0:
            N = N / K
            answer += 1
        else:
            N -= 1
            answer += 1
    print(answer)

✍🏻N을 K로 나누는 방법이 N에서 1을 빼는 방식보다 더 빠르게 최적의 해를 구할 수 있는 방법이다. 때문에 최대한 뺄셈보다 나눗셈을 많이 해야하고 이 문제가 그리디인 이유는 여기에 있다.

👉🏻일단 if문으로 K로 나눌 수 있는지 판단해 나눌 수 있는 만큼 나누었다.

1. while문과 N-1을 사용해 반복문을 돌렸다. N이 1이 되는 순간 멈춰야하는데 1 - 1은 0(false)인 점을 사용해 반복문을 중단한다.
2. N을 K로 나누었을 때 나머지를 확인해 0이면 나누어 주고 아니면 1을 빼준다. 
3. 각 단계가 끝날 때마다 answer에 1을 더해주고 모든 단계가 끝나면 answer을 출력한다.