[알고리즘] 그리디(Greedy)

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

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

3장. 그리디(Greedy) 알고리즘

- 탐욕법: 현재 상황에서 지금 당장 좋은 것만 고르는 방법

- 예제 알고리즘: 플로이드 워셜 알고리즘, 다익스트라 알고리즘

- 정렬 알고리즘과 짝을 이뤄 출제된다

예제 3-1. 거스름돈

문제 해결: 가장 큰 화폐 단위부터 돈을 거슬러 주는 것

n = 1260
count = 0

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

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

시간복잡도: O(K) -> 화폐의 종류가 K개 일때

정당성 검사: 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문에 그리디 알고리즘으로 해결 가능. 만약 화폐의 단위가 서로 배수 형태가 아니라 무작위로 주어진 경우에는 그리디 알고리즘으로 해결할 수 없다.

---

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

 

 

실전문제 2. 큰 수의 법칙

문제 해결: 가장 큰 수를 K번 더하고 두 번째로 큰 수를 한 번 더하는 연산을 반복 -> m이 10000이하이면 시간초과가 나지 않지만 100억이상처럼 커진다면 시간 초과가 날 것이다.

 

1) 단순하게 푸는 답안 예시

n, m, k = map(int, input().split())
arr = list(map(int, input().split()))
answer = 0

# 배열 정렬
arr.sort()
first_max = arr[n - 1]
second_max = arr[n - 2]

while True:
    # 가장 큰 수를 K번 더하기
    for i in range(k):
        if m == 0:
            break
        answer += first_max
        m -= 1 # 더할 때마다 1씩 빼기
    if m == 0:
        break
    # 두 번째로 큰 수를 한 번 더하기
    answer += second_max
    m -= 1


print(answer)

2) 반복되는 수열에 대해서 파악

- M을 K + 1 로 나눈 몫이 수열이 반복되는 횟수가 된다

- 여기에 K를 곱해주면 가장 큰 수가 등장하는 횟수가 된다

- 가장 큰 수가 더해지는 횟수 : int(M / (K + 1)) * K + M % (K + 1)

count = int(m / (k + 1)) * k
count += m % (k + 1)

answer += (count) * first_max  # 가장 큰 수 더하기
answer += (m - count) * second_max  # 두번째로 큰 수 더하기

 

실전문제 3. 숫자 카드 게임

- 게임의 룰: 선택된 행에 포함된 카드들 중  가장 숫자가 작은 카드를 뽑고, 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 함

- 문제 해결: 각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수 찾기

n, m = map(int, input().split())

answer = 0

# 답안 1) min 함수를 이용
for i in range(n):
    data = list(map(int, input().split()))

    # 현재 줄에서 가장 작은 수 찾기
    min_card = min(data)
    # 가장 작은 수 들 중에서 가장 큰 수 찾기
    answer = max(answer, min_card)

# 답안 2) 2중 반복문 사용
for i in range(n):
    data = list(map(int, input().split()))
    min_card = 10001
    for a in data:
        min_card = min(min_card, a)
    answer = max(answer, min_card)

print(answer)

 

실전문제 4. 1이 될 때까지

- 어떠한 수 N이 1이 될때까지 1. N에서 1을 뺀다 2. N을 K로 나눈다 두 과정중 하나를 수행하는 최소 횟수 구하기

- 문제 해결 : N에 대하여 최대한 많이 나누기를 수행한다. -> 1을 빼는 것보다 2 이상의 수로 나누는 것이 숫자를 훨씬 많이 줄일 수 있기 때문에

 

답안1) 단순하게 푸는 답안

n, k = map(int, input().split())

answer = 0

# 답안 1) 단순하게 풀기
# N이 K 이상이라면 K로 계속 나누기
while n >= k:
    # N이 K로 나누어 떨어지지 않는다면 N - 1
    while n % k != 0:
        n -= 1
        answer += 1
    # K로 나누기
    n //= k
    answer += 1

# 마지막으로 남은 수에 대하여 1씩 빼기
while n > 1:
    n -= 1
    answer += 1
    
print(answer)

답안2) 더 빠르게 동작하는 답안

- N이 K의 배수가 되도록 효율적으로 한 번에 빼는 방식

n, k = map(int, input().split())

answer = 0

# 답안 2) 더 빠르게 동작하는 풀이
while True:
    # N == K로 나누어떨어지는 수가 될 때까지 1씩 빼기
    target = (n // k) * k
    answer += (n - target)
    n = answer
    
    # N이 K보다 작을 때 (더이상 나눌 수 없을 때) 반복문 탈출
    if n < k:
        break
    # K로 나누기
    answer += 1
    n //= k

# 마지막으로 남은 수에 대하여 1씩 빼기    
answer += (n - 1)

print(answer)