그리디(Greedy) 알고리즘

✅ Greedy Algorithm

그리디 알고리즘(Greedy Algorithm;탐욕법)은 최적해를 구하는 근사적인 방법으로, 문제를 해결하는 과정에서 현재 상태에서 가장 좋아 보이는 선택을 하는 방법론이다. 그리디 알고리즘은 매 순간마다 최선의 선택을 함으로써 전체적으로 최적해에 도달하려고 시도하지만, 항상 최적해를 보장하지는 않으며, 특정 문제에서는 그리디 알고리즘이 최적해를 보장하는 경우가 있다.

쉽게 말하자면 문제를 해결하는 과정에서 순간순간마다 최적의 결정을 하는 방식! 근데 항상 최적의 답을 구하지는 않다!로 이해하면 될 것 같다. 그리디 알고리즘은..아이디어와 창의력이 중요하므로 다양한 유형을 접하는게 좋다!

 

📌 거스름돈 문제

❓문제

카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원 동전이 무한히 존재한다. 손님에게 거슬러 줄 돈이 n원일 때, 거슬러 줘야할 동전의 최소 개수는? 단, 거슬러 줘야 할 돈 n은 항상 10의 배수이다.

❗️풀이

우선 문제를 보자마자 가장 큰 돈의 단위인 "500원"부터 거슬러줘야 한다를 떠올려야 한다. 왜냐면 동전은 무한히 존재하니까!

# 거슬러 줘야 할 금액
n = int(input().strip())

# 동전 종류
coin_types = [500, 100, 50, 10]

# 동전 개수 카운트
count = 0

# 각 동전 종류마다 최대한 많은 동전을 사용해야 함
for coin in coin_types:
    count += n // coin  # 현재 동전으로 줄 수 있는 최대 개수
    n %= coin  # 나머지 금액

print(count)

 

📌 큰 수의 법칙

❓문제

다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드려고 한다. 단, 배열의 특정한 인덱스에 해당하는 수가 연속해서 k번을 초과하여 더해질 수 없다. 그러나, 서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주한다. 배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 K가 주어질 때 해당 큰 수의 법칙에 따른 결과를 출력하시오

• 첫째 줄에 N (2 ≤ N ≤ 1,000), M (1 ≤ M ≤ 10,000), K (1 ≤ K ≤ 10,000)의 자연수가 주어진다.
• 둘째 줄에 N개의 자연수가 주어진다. 각 자연수는 공백으로 구분된다. 각 자연수는 1 이상 10,000 이하의 수로 주어진다.
• 입력으로 주어지는 K는 항상 M보다 작거나 같다.

❗️풀이

문제 속에 힌트가 있다(어...? 고3시절 많이 들었던 말..)

리스트를 내림차순으로 정렬해서 가장 큰 수와 두 번째로 큰 수만 저장하면 된다! 가장 큰 수를 K번 더하고, 그 다음 큰 수를 1번 더하는 패턴을 반복하면 문제가 풀린다.

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

# 내림차순 정렬
numbers.sort(reverse=True)

first = numbers[0]
second = numbers[1]

# 가장 큰 수가 더해지는 횟수 계산
count_first = (M // (K + 1)) * K + (M % (K + 1))
count_second = M - count_first

# 결과 계산
result = count_first * first + count_second * second

print(result)

 

 

📌 숫자 카드 게임

❓문제

여러 개의 숫자 카드 중에서 가장 높은 숫자가 쓰인 카드 한 장을 뽑는 게임이다. 룰은 다음과 같다.

1. 숫자 카드들이 n*m 형태로 놓여 있다. 첫째 줄에 숫자 카드들이 놓은 행의 개수 N과 열의 개수 M이 공백을 기준으로 자연수로 주어진다. (1 ≤ N,  M ≤ 100, 숫자는 1이상 10,000 이하 자연수) 
2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.
3. 그 다음 선택된 행에 포함된 카드 중 가장 숫자가 낮은 카드를 뽑는다.
4. 처라서 처음 카드를 골라낼 행을 선택할 때, 이후 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려해 최종적으로 가장 높은 숫자 카드를 뽑도록 전략을 세워야 한다.

❗️풀이

문제는 ???뭐야???라는 생각이 들지만, 은근 간단하다. 그냥..min과 max를 사용해서 for문을 돌면 된다!

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
cards = [list(map(int, input().split())) for _ in range(n)]
temp = []

for card in cards:
	temp.append(min(card))

print(max(temp))

 

 

📌 1이 될 때까지

❓문제

어떤 수 N이 1이 될 때까지 다음 두 과정 중 하나를 반복적으로 선택해 수행한다. 단, 두 번째 연산은 N이 K로 나누어 떨어질 때만 선택할 수 있다.

1. N에서 1을 뺸다.

2. N을 K로 나눈다.

첫째 줄에 N(2 ≤N ≤100,000)과 K(2 ≤K ≤100,000)가 공백으로 구분되며 각각 자연수로 주어진다. 이 때 입력으로 주어지는 N은 항상 K보다 크거나 같다. 첫째 줄에 N이 1이 될 때까지 1번 혹은 2번을 수행하야 하는 횟수의 최솟값을 출력한다.

❗️풀이

이건 아이디어 떠올리기가 쉬웠다. 횟수가 최소가 되어야하니까 배수일수록 유리하다. 그니까~N이 K의 배수가 될 때까지 빼주면 된다!

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

while n != 1:
	if n % k == 0:
		n //= k
	else:
		n -= 1
	
	cnt += 1

print(cnt)

 

 

창의력이 부족한 나에게는 그리디 알고리즘 너무 어렵당...

 

[참고: 이것이 취업을 위한 코딩 테스트다 with 파이썬]