Greedy 알고리즘(탐욕법)
탐욕적이라는 말은 현재 상황에서 지금 당장 좋은 것만을 고르는 방법을 의미한다.
예제 거스름돈
Q
당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라.
단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.
A
가장 큰 화폐 단위로부터 돈을 거슬러 주는 것!
코드
N = int(input())
a = [500, 100, 50, 10] #화폐단위 리스트 선언
b = N
k = 0
a.sort(reverse = True) #내림차순 정렬
for i in a:
k += b // i
b = N % i
print(k)
가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위 동전들을 종합하여 다른 해가 나올 수 없기 때문에 정당하다. 이처럼 그리디 알고리즘 문제에서는 최소한의 아이디어 떠올리고 정당한지 검토해야 한다.
실전문제1 큰 수의 법칙
Q
통계분야의 큰 수의 법칙이 아니라 다르게 정의하고 있다. 다양한 수로 이루어진 배열이 있을 때, 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙을 말한다. 단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 K번 초과하여 더해질 수 없다. 단, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다.
배열의 크기가 N, 숫자가 더해지는 횟수 M, K가 주어질 때 결과를 출력하시오.
입력조건
첫째 줄에 N, M, K의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
둘째 줄에 N개의 자연수가 주어지며, 각 자연수는 공백으로 구분한다.
A
배열 중 가장 큰 수와 두번째로 큰 수만 저장해서 이용하면 된다. 반복되는 수열에 대해서 파악하면 쉽다.
코드
n, m, k = map(int, input().split())
array = list(map(int, input().split()))
array.sort() #오름차순으로 정렬
count = 0
result = 0
while True:
if count % k == 0 and count != 0:
count += 1
result += array[-2]
elif m > count:
count += 1
result += array[-1]
elif m == count:
break
print(result)
틀린 코드
n, m, k = map(int, input().split())
list1 = list(map(int, input().split()))
list1.sort() #오름차순으로 정렬
b1 = list1[-1] #리스트1에서 가장 큰 수 구하기
b2 = list1[-2] #리스트1에서 두번째로 큰 수 구하기
result = 0
while True:
if m <= 0:
break
if m > 0:
result += ((b1 * k) + b2)
m -= (k + 1) #한번에 이정도를 빼면 m이 마이너스가 될 수 있어서 틀렸다.
print(result)
실전문제2 숫자카드게임
Q
숫자카드게임은 여러 개의 숫자카드 중에서 가장 높은 숫자가 쓰인 카드 한장을 뽑는 게임이다. 게임 룰은 다음과 같다.
1)숫자가 쓰인 카드들이 N X M 형태로 놓여 있다. 이때 N은 행의 개수, M은 열의 개수를 의미한다.
2)먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.
3)그다음 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.
게임 룰에 맞게 카드를 뽑는 프로그램을 만드시오.
입력조건
첫째 줄에 숫자카드들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 각각 자연수로 주어진다.
둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다.
A
각 행마다 가장 작은 수를 찾은 뒤 그 수들 중에서 가장 큰 수를 찾기
코드
n, m = map(int, input().split()) #입력받기
array = [0] * n #2차원 리스트 생성
for i in range(n):
array[i] = list(map(int, input().split()))
k = []
for i in range(n):
k.append(min(array[i])) #k리스트에 각 행마다 최소값 넣기
print(max(k))
실전문제3 1이 될 때까지
Q
어떠한 수 N이 1이 될 때까지 다음의 두 과정 중 하나를 반복적으로 선택하여 수행하려고 한다. 단, 두번째 연산은 N이 K로 나누어떨어질 때만 선택할 수 있다.
(1) N에서 1을 뺀다.
(2) N을 K로 나눈다.
N과 K가 주어질 때, N이 1이 될 때까지 1번 혹은 2번 과정을 수행해야 하는 최소 횟수를 구하는 프로그램을 작성하시오.
입력조건
첫째 줄에 N과 K가 공백으로 구분되며 각각 자연수로 주어진다.
A
최대한 많이 나누기를 수행하면 된다. 그리디 알고리즘 문제는 많이 생각하기보다는 간단한 아이디어 생각하고 이를 코드로 만드는 것이 중요하다.
코드
n, k = map(int, input().split()) #n과 k 입력받기
count = 0
while n > 1: #1일때는 종료시키도록 반복문 생성
if n % k == 0:
n /= k
count += 1
else:
n -= 1
count += 1
print(count)
