그리디(Greedy) 개념 정리

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

현재 상황에서 지금 당장 좋은 것만 고르는 방법 → 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형

그리디 알고리즘 유형 문제는 창의력, 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구한다.

그리디 알고리즘은 모든 알고리즘에 적용할 수 있는 것이 아니다. 대부분의 문제는 그리디 알고리즘을 이용했을 때 ‘최적의 해’를 찾을 수 없는 가능성이 다분하다. 하지만, 정확한 답을 찾을 수 있다는 보장이 있을 때는 매우 효과적이고 직관적이다. 따라서, 그리디 알고리즘으로 해법을 찾았을 때는 항상 ‘검토’를 하자.

 

예제 3-1 거스름돈

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

exchange = int(input('얼마의 돈을 내었나요?'))

count = 0
money_list = [500,100,50,10]
for i in money_list:
	temp = exchange//i
	exchange = exchange - temp*i
	count += temp
	print(f'{i} 동전의 개수는 {temp}입니다.')

print(f'최종 동전 개수는 {count}입니다.')

예제 3-1 해결방법

‘가장 큰 화폐 단위부터’ 돈을 거슬러 주는 것이다. 시간 복잡도를 O(K)임을 확인하고 넘어가자

---

 

큰 수의 법칙

동빈이는 큰 수의 법칙을 다음과 같이 정의했다. 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만드는 법칙이다. 단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없다.

 

예제 3 -2

배열의 크기 N, 숫자가 더해지는 횟수 M, 그리고 k가 주어질 때 동빈이의 큰 수의 법칙을 구현하라. 입력 조건은 다음과 같다

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

다시, 해결방법 생각해보자! 일단 k번만큼 max가 더해짐. 그리고 k와 상관없이 max의 다음 값을 1번 더함.

#랜덤 숫자부여
import random

n = random.randint(2,1000)
k = 1
m = 2
while k<=m:
    m = random.randint(1,10000)
    k = random.randint(1,10000)

num_list = []
for i in range(n):
    num_list.append(random.randint(1,10000))

#임의 지정
n, m, k = input('숫자를 입력하세요').split()
print(n,m,k)

num_list = []
for i in range(int(n)):
    num_list.append(int(input('숫자를 입력하세요 : ')))

print(num_list)

#가장 큰 수를 찾는 방법 다시
k = int(k)
m = int(m)
count = 0

a = max(num_list)
num_list.remove(a)
b = max(num_list)

while m!=0:
    count = count + a*k
    m = m - k
    count = count + b
    m = m - 1

print(count)

while 문을 쓰지 않고, 책의 풀이 방법대로 해보자! [6665]를 하나의 묶음으로 생각하면?! m = 11, k =8

11//9 = 1 (수열의 반복 횟수)

11%9 = 2 (나머지 제일 큰 수의 합 개수)

m = 11, k =3

11//4 = 2 (수열의 반복 횟수)

11//4 = 3 (수열의 반복 횟수)

n, m, k = map(int,input().split())
data = list(map(int,input()split()))

data.sort()
first = data[n-1]
second = data[n-2]

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

result = 0
result += count * first
result += (m-count) *second

print(result)

---

숫자 카드 게임

예제 3-3

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

1. 숫자가 쓰인 카드들이 N*M개 형태로 놓여있다. N은 행의 개수, M은 열의 개수 이다.
2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택한다.
3. 그다음 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑아야 한다.
4. 따라서 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세우어야 한다.

게임의 룰에 맞게 카드를 뽑는 프로그램을 만드시오

입력조건

• 첫째 줄에 숫자들이 놓인 행의 개수 N과 열의 개수 M이 공백을 기준으로 하여 각각 자연수로 주어진다. (1≤N, M≤100)
• 둘째 줄부터 N개의 줄에 걸쳐 각 카드에 적힌 숫자가 주어진다. 각 숫자는 1이상 10,000 이하의 자연수이다.

출력조건

• 첫째 줄에 게임의 룰에 맞게 선택한 카드에 적힌 숫자를 출력한다.

n,m = map(int,input('N,M을 입력하시오 : ').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)

이 문제는 ‘각 행마다 가장 작은 수를 찾은 뒤에 그 수 중에서 가장 큰 수를 찾는 문제’이다. 아니.. 내가 잘 못 이해한 듯! 나는 가장 작은 수를 찾은 뒤, 그 열에서 가장 높은 숫자를 찾는 문제로 인식했음 ㅠㅠ