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

코딩테스트/알고리즘 기초

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

ggulgood 2022. 4. 21. 06:19

그리디(Greedy)

단순하지만 강력한 문제 해결 방법

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

제시 포인트:

'가장 큰 순서대로'

'가장 작은 순서대로'

-> 정렬 알고리즘 + 그리디 알고리즘

예제 1. 거스름돈

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

* 문제 해설

가장 큰 화폐 단위부터 돈을 거슬러 주는 아이디어 is good

화폐의 종류가 K개라 한다면, 시간 복잡도는 O(K)

n = int(input()) # 거슬러 줘야 할 돈 입력 받기
cnt = 0

coin_types = [500, 100, 50, 10]

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

print(cnt)

시간 측정 코드를 추가해서 기록해본다면

import time
start_time = time.time() # 측정 시작

n = int(input()) # 거슬러 줘야 할 돈 입력 받기
cnt = 0

coin_types = [500, 100, 50, 10]

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

print(cnt)

end_time = time.time() # 측정 종료
print("time :", end_time - start_time) # 수행 시간 출력

예제 2. 큰 수의 법칙

동빈 개발자 tip:

다양한 수로 이루어진 배열이 있을 때 주어진 수들을 M번 더하여 가장 큰 수를 만든다.

단, 배열의 특정한 인덱스(번호)에 해당하는 수가 연속해서 K번을 초과하여 더해질 수 없는 것이 이 법칙의 특징

* 문제 해설

예를 들어 순서대로 2, 4, 5, 4, 6 으로 이루어진 배열이 있을 때 M = 8, K = 3 이라 가정.

이 경우 6 + 6 + 6 + 5 + 6 + 6 + 6 + 5 = 46 이 됨

ㄷ서로 다른 인덱스에 해당하는 수가 같은 경우에도 서로 다른 것으로 간주.

예를 들어 3, 4, 3, 4, 3 으로 이루어진 배열이 있을 때 M = 7, K =2

이 경우 두번째 원소 4와 네 번째 원소 4를 번걸아 두 번씩 더하는게 가능,

즉 4 + 4+ 4 + 4+ 4+ 4 + 4 = 28

# 첫째 줄에 자연수를 공백으로 구분하여 입력받기
n, m, k = map(int, input().split())

# 둘째 줄에 n개의 자연수를 공백으로 구분하여 입력 받기, 1이상 10000 이하의 수
num = list(map(int, input().split()))

# 정렬로 큰 수와 두번 째로 큰 수를 겟
num.sort()
first = num[n - 1] # 제일 큰 수
second = num[n - 2] # 두번 째로 큰 수

result = 0

# 입력으로 주어지는 K는 항상 M보다 작거나 같음
# 큰 수의 법칙 적용
while True:
    for i in range(k):
        if m == 0: # m이 0이라면 반복문 탈출
            break
        result += first
        m -= 1 # 더할 때마다 하나씩 빼서
    if m == 0:
        break
    result += second # 두 번째로 큰 수를 한 번 더하기
    m -= 1

print(result)

조금 더 나아가 반복되는 수열에 대해 파악해본다면

가장 큰 수와 두 번째로 큰 수가 더해질 때는 특정한 수열 형태로 일정하게 반복해서 더해지는 특징이 있다.

그렇다면 반복되는 수열의 길이는 (K+1) 이 된다.

즉, M / (K+1) 의 몫이 수열이 반복되는 횟수

여기에 K를 곱해주면 가장 큰 수가 등장하는 횟수가 된다.

이 때 M이 (K+1)로 나누어 떨어지지 않는 경우도 고려해야 함

그러므로 가장 큰 수가 더해지는 횟수는

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) # 최종 답안 출력

예제 3. 숫자 카드 게임

게임의 룰:

1. 숫자가 쓰인 카드들이 N X M 형태로 놓여있다. N은 행의 개수, M은 열의 개수

2. 먼저 뽑고자 하는 카드가 포함되어 있는 행을 선택

3. 선택된 행에 포함된 카드들 중 가장 숫자가 낮은 카드를 뽑는다

4. 처음에 카드를 골라낼 행을 선택할 때, 이후에 해당 행에서 가장 숫자가 낮은 카드를 뽑을 것을 고려하여 최종적으로 가장 높은 숫자의 카드를 뽑을 수 있도록 전략을 세워야 한다

카드들이 N X M 형태로 놓여있을 때 게임의 룰에 맞게 카드를 뽑는 프로그램을 만드시오.

* 문제 해설

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

# 첫째 줄에 자연수를 공백으로 구분하여 행의 개수 N과 열의 개수 M을 입력받기
n, m = map(int, input().split())

result = 0

# 둘째 줄에 N줄에 걸쳐 각 카드가 적힌 숫자가 주어진다.
# 출력: 첫째 줄에 게임의 룰에 맞게 선택된 카드에 적힌 숫자를 출력한다.
# 한 줄씩 입력받아 확인
for i in range(n):
    data = list(map(int, input().split()))
    min_value = min(data)
    result = max(min_value, result)

print(result)

출처: [이것이 취업을 위한 코딩 테스트다 with 파이썬] 서적

저작자표시