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

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

그리디 알고리즘 자체가 문제 출제의 폭이 매우 넓기 때문에, 다익스트라 알고리즘과 같은 특이 케이스를 제외하고는 단순 암기를 통해 모든 문제를 대처하기 어렵다.

특정한 문제를 만났을 때 단순히 현재 상황에서 가장 좋아 보이는 것만을 선택해도 문제를 풀 수 있는지를 파악할 수 있어야 한다.

그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제된다.

 

[1-1] 거스름돈

문제

카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다.

손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라.

단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

문제 해설

가장 큰 화폐 단위부터 돈을 거슬러 주는 것

n = 1260
count = 0

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

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

print(count)

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

 

[1-2] 큰 수의 법칙

문제 풀이

반복되는 수열에 대해 파악

2 4 5 4 6일 때

가장 큰 수 : 6

두 번째로 큰 수 : 5

M : 8, K : 3

ex) 6 6 6 5 | 6 6 6 5

특징 : K + 1로 나뉘는 것을 알 수 있다.

M // (K+1) : 반복되는 횟수

한 칸에 K개 있다.

나머지만큼 가장 큰 수가 추가로 더해진다.

int(M/ (K+1)) * K + M % (K+1)

# N, M, K를 공백으로 구분하여 입력받기
n, m, k = map(int, input().split())
# N개의 수를 공백으로 구분하여 입력받기
data = list(map(int,input().split()))

data.sort() # 입력받은 수 정렬
first = data[n-1] # 가장 큰 수
second = data[n-2] # 두 번째로 큰 수

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

result = 0
result += (count) * first # 가장 큰 수 더하기
result += (m-count) * second # 두 번째로 큰 수 더하기

print(result)

 

[1-3] 숫자 카드 게임

각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수를 찾는 것

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


result = 0

# 한 줄씩 입력받기 확인
for i in range(n):
    data = list(map(int, input().split()))
    # 현재 줄에서 '가장 작은 수' 찾기
    min_value = min(data)

    # '가장 작은 수'들 중에서 가장 큰 수 찾기
    result = max(result, min_value)

print(result)

 

 

 

---

참고 자료

• 이것이 취업을 위한 코딩 테스트다