[알고리즘] 그리디 알고리즘이란?

❇️이 글은 '이것이 코딩테스트다' 교재를 학습하며 작성했습니다.

그리디 알고리즘은 현재 상황에서 가장 좋아보이는 것만을 선택하는 알고리즘이다.

 

1. 거스름돈 문제

당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구해라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

 

해결방법

돈을 가장 큰 화폐 단위부터 거슬러주면 된다.

n=1260
count = 0

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

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

print(count)

 

하지만, 이 알고리즘은 큰 단위의 화폐가 작은 단위의 화폐의 배수이기 때문에 정당한 알고리즘이다.

만약, 주어진 화폐가 500, 400, 100이라면 이 알고리즘은 800원을 500, 100, 100, 100 이렇게 주겠지만 최적의 답은 400원짜리 두 개를 주는 것이다. 

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

 

2. 큰 수의 법칙

가장 큰 수가 K번 더해지고, 두 번째로 큰 수가 한 번 더해지는 과정이 반복된다.

책에서는 반복문을 활용하는 방법과 가장 큰 수가 더해지는 횟수, 두 번째로 큰 수가 더해지는 횟수를 구해 더했지만 나는 한 번에 수식을 구해 구현했다.

N,M,K = map(int, input().split())
num_list=list(map(int, input().split()))

num_list.sort()
first = num_list[N-1] #가장 큰 수
second = num_list[N-2] #두 번째로 큰 수

result = (first*K + second)*(M//(K+1)) + (M%(K+1))*first
print(result)

3. 숫자 카드 게임

 

 

문제 해설

각 행마다 가장 작은 수를 찾고, 그 수 중에서 가장 큰 수를 출력하면 된다.

N,M = map(int, input().split())
min_list = []

for i in range(N):
  data = list(map(int, input().split()))
  min_list.append(min(data))

print(max(min_list))

 

4. 1이 될 때까지

 

N, K = map(int, input().split())
result = 0

while N > 1:  # N이 1이 될 때까지 반복
    if N % K == 0:  # N이 K로 나누어 떨어지면
        N //= K  # N을 K로 나눈 몫으로 업데이트
        result += 1  # 결과값 1 증가
    else:  # 그렇지 않으면
        N -= 1  # N에서 1을 뺌
        result += 1  # 결과값 1 증가

print(result)