[TIL/10.19] Algorithm: 그리디 알고리즘

그리디 알고리즘

현재 상황에서 지금 당장 좋은 것만 고르는 방법이다.

 

 

특징

• 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시해준다.
• 대체로 정렬 알고리즘과 짝을 이루어 출제된다.

 

예제

대표적인 문제로 거스름돈 문제가 있다.

 

카운터에는 거스름돈으로 사용할 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  # 돈을 coin으로 나눈 몫 = coin 갯수
    n %= coin  # 나머지 금액 계산

print(count)

💡 가장 큰 화폐 단위부터 돈을 거슬러 줘야 한다.

 

실전문제 1 - 큰 수의 법칙

<문제>
동빈이의 큰수의 법칙은 다양한 수로 이루어진 배열이 있을 때 주어진 수들을 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가 주어질 때 동빈이의 큰 수의 법칙에 따른 결과를 출력하시오.

 

<입력 조건>

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

<출력 조건>

• 첫째 줄에 동빈이의 큰수의 법칙에 따라 더해진 답을 출력한다.

<입력 예시>                                                                             <출력 예시>

• 5 8 3                                                                                      46
  2 4 5 4 6

 

💡   가장 큰 수와 두 번째로 큰 수만 저장하면 된다. 연속으로 더할 수 있는 횟수는 최대 K번이므로 '가장 큰 수를 K번 더하고 두 번째로 큰 수를 한 번 더하는 연산'을 반복하면 된다.

# 주어진 수들을 M번 더하여 가장 큰 수를 만든다.
# 특정 숫자가 연속해서 K번을 초과하여 더해질 수 없다.
# 중복되는 숫자는 서로 다른 것으로 간주한다.

# 배열의 크기 n, 숫자가 더해지는 횟수 M, 최대 연속 횟수 K
n, m, k = map(int, input().split())
# 자연수 배열
arr = list(map(int, input().split()))

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

sum = 0
while True:
    # k 횟수만큼 더함
    for _ in range(k):
        if m == 0:  # 남은 횟수
            break
        sum += first
        m -= 1  # 더해지는 횟수 -1
    # 두 번째로 작은 수를 한 번 더함
    if m == 0:
        break
    sum += second
    m -= 1

print(sum)

M이 10,000이하 일 때는 이 방식으로 가능하지만, M이 크기가 100억 이상이 된다면 TLE가 뜰 수도 있다. 

그러므로 두번째 풀이는, 가장 큰 수와 두 번째로 큰 수를 더하는 걸 하나로 묶어서 생각한다!

예를 들어서 N = 5, M = 8, K = 3 라면, 

(6 + 6 + 6 + 5) + (6 + 6 + 6 + 5) = (6 * 3) * 2 + (5 * 2)
= 6 * ((8 / 4) * 3) + 5 * (8 - ((8 / 4) * 3))

위의 예시를 통해 다음과 같은 식을 만들 수 있다.

✔ 큰 수 더하는 횟수는 (K * (M / (K+1)) + (M % (K+1)))

✔ 그 다음 큰 수 더하는 횟수는 M - (K * (M / (K+1)) + (M % (K+1)))

 

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

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

# 가장 큰 수가 더해지는 횟수
# 반복되는 수열의 길이 K+1만큼 나눈 몫 m / (k+1)이 반복되는 횟수.
count = int(m / (k + 1)) * k
# k+1로 나눈 나머지 만큼의 크기는 가장 큰 수를 더해주어야 함
count += m % (k + 1) 

sum = 0
sum += (count) * first  # 횟수만큼 가장 큰 값을 더해준다.
sum += (m - count) * second  # 가장 큰 수를 더해주는 횟수를 제외하고 두번째로 큰 수를 더해준다.

print(sum)

 

백준 11047번

<문제>

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

 

<입력>

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄의 동전의 가치가 오름차순으로 주어진다.

 

<출력>

첫째 줄 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

💡 coins안에 있는 수 중 K를 나눌 수 있는 가장 큰 수를 찾고 몫은 answer에 더해주고, 나머지는 K에 부여한다.

# 1. 계산대 안에 있는 돈의 수와 거슬러 줄 돈을 구합니다.
N, K = map(int, input().split()) # N : 화폐 종류수, K : 거슬러 줄 돈

# 2. 계산대에 있는 화폐들을 리스트의 형태로 입력받습니다.
coins = []
for _ in range(N):
    coins.append(int(input()))
coins.sort(reverse=True)
# coins = [50000, 10000, 5000, 1000, 500, 100, 50, 10, 5, 1]

# 3. 만약 '계산대 안에 있는 화폐'보다 '거슬러 줄 돈'이 크다면
# 돈을 거슬러 줍니다.
answer = 0
for coin in coins:
    if K >= coin:
        answer += K // coin 몫만큼 더하기
        K %= coin 나머지 할당
        if K <= 0: # 만약 K가 0이면 반복문을 탈출합니다.
       		break
print(answer) # 거슬러 준 동전 + 화폐의 수

 

백준 2875번

문제

백준대학교에서는 대회에 나갈 때 2명의 여학생과 1명의 남학생이 팀을 결성해서 나가는 것이 원칙이다. (왜인지는 총장님께 여쭈어보는 것이 좋겠다.)

백준대학교는 뛰어난 인재들이 많아 올해에도 N명의 여학생과 M명의 남학생이 팀원을 찾고 있다. 대회에 참여하려는 학생들 중 K명은 반드시 인턴쉽 프로그램에 참여해야 한다. 인턴쉽에 참여하는 학생은 대회에 참여하지 못한다.

백준대학교에서는 뛰어난 인재들이 많기 때문에, 많은 팀을 만드는 것이 최선이다.

여러분은 여학생의 수 N, 남학생의 수 M, 인턴쉽에 참여해야하는 인원 K가 주어질 때 만들 수 있는 최대의 팀 수를 구하면 된다.

입력

첫째 줄에 N, M, K가 순서대로 주어진다. (0 ≤ M ≤ 100, 0 ≤ N ≤ 100, 0 ≤ K ≤ M+N),

출력

만들 수 있는 팀의 최대 개수을 출력하면 된다.

 

💡

여학생(n)과 남학생(m)을 합한 값이 인턴쉽에 참여해야하는 인원(k)보다 크거나 같고,

여학생의 수(n)가 2보다 크거나 같아야 하고 남학생의 수(m) 또한 1보다 크거나 같을 때 수행

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

while True:
    N = N - 2
    M = M - 1
    if N < 0 or M < 0 or (N+M) < K:
        break
    team = team + 1
print (team)

백준 11399번

문제

인하은행에는 ATM이 1대밖에 없다. 지금 이 ATM앞에 N명의 사람들이 줄을 서있다. 사람은 1번부터 N번까지 번호가 매겨져 있으며, i번 사람이 돈을 인출하는데 걸리는 시간은 Pi분이다.

사람들이 줄을 서는 순서에 따라서, 돈을 인출하는데 필요한 시간의 합이 달라지게 된다. 예를 들어, 총 5명이 있고, P1 = 3, P2 = 1, P3 = 4, P4 = 3, P5 = 2 인 경우를 생각해보자. [1, 2, 3, 4, 5] 순서로 줄을 선다면, 1번 사람은 3분만에 돈을 뽑을 수 있다. 2번 사람은 1번 사람이 돈을 뽑을 때 까지 기다려야 하기 때문에, 3+1 = 4분이 걸리게 된다. 3번 사람은 1번, 2번 사람이 돈을 뽑을 때까지 기다려야 하기 때문에, 총 3+1+4 = 8분이 필요하게 된다. 4번 사람은 3+1+4+3 = 11분, 5번 사람은 3+1+4+3+2 = 13분이 걸리게 된다. 이 경우에 각 사람이 돈을 인출하는데 필요한 시간의 합은 3+4+8+11+13 = 39분이 된다.

줄을 [2, 5, 1, 4, 3] 순서로 줄을 서면, 2번 사람은 1분만에, 5번 사람은 1+2 = 3분, 1번 사람은 1+2+3 = 6분, 4번 사람은 1+2+3+3 = 9분, 3번 사람은 1+2+3+3+4 = 13분이 걸리게 된다. 각 사람이 돈을 인출하는데 필요한 시간의 합은 1+3+6+9+13 = 32분이다. 이 방법보다 더 필요한 시간의 합을 최소로 만들 수는 없다.

줄을 서 있는 사람의 수 N과 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어졌을 때, 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000)

 

출력

첫째 줄에 각 사람이 돈을 인출하는데 필요한 시간의 합의 최솟값을 출력한다.

 

 

💡  인출 시간이 적은 순으로 정렬

n = int(input()) 
peoples = list(map(int, input().split())) 

peoples.sort()  
answer = 0  

for x in range(1, n+1):
    answer += sum(peoples[0:x])  # 리스트의 0번째 수부터 x번째 수까지를 더해줍니다.
print(answer)

 

참고

• 이것이 취업을 위한 코딩 테스트다 with 파이썬
• https://runa-nam.tistory.com/57#--%--%EB%AC%B-%EC%A-%-C%--%EC%B-%--%EC%B-%-C