[python] Greedy Algorithm_백준 문제 풀이

Greedy Algorithm (탐욕 알고리즘)

'당장 눈 앞에 보이는 최적의 상황만을 쫓는 알고리즘'으로 가장 단순하고 난이도가 낮은 알고리즘이다.
항상 최적의 결과를 도출하는 것은 아니지만 어느 정도 최적의 해에 근사한 값을 빠르게 구할 수 있다. 또한 특정한 상황에 있어서는 그리디 알고리즘이 최적의 해를 보장할 수도 있다.
하지만 그런 특정한 상황, 탐욕 알고리즘에 해당하는 문제를 알기가 어렵다.

대표적인 문제 - 거스름돈 문제
거스름 돈을 줄 때 가장 적은 양의 화폐를 주는 것이 제일 편하다. 그런 경우 무조건 더 큰 화폐 단위부터 거슬러 준다는 알고리즘을 지키면 최적의 해를 보장할 수 있다.
이처럼 무조건 큰 경우대로, 혹은 무조건 작은 경우대로, 혹은 무조건 긴 경우대로, 혹은 무조건 짧은 경우대로 등 극단적으로 문제에 접근하기 때문에 정렬 기법이 함께 사용되는 경우가 많다.

백준 11047번 - 동전 0

이 문제는 동전의 개수를 최소화하는 문제이므로 단위가 큰 동전부터 최대한 거스름돈을 처리하면 된다. 그러기 위해 동전을 내림차순으로 정렬하거나, for문을 뒤에서부터 돌려주면 되고, 거스름돈이 0이 되면 빠져나오게 하여 종료시켰다.

import sys

input = sys.stdin.readline
N, K = map(int, input().split(' '))
coins = []
for n in range(N):
    coins.append(int(input()))
count = 0
for c in range(len(coins), 0, -1):
    if K // coins[c-1] > 0:
        x = int(K // coins[c-1])
        K -= coins[c-1]*x
        count += x
    if K == 0:
        break

print(count)

백준 1931번 - 회의실 배정

이 문제는 하나의 회의실에 최대한 많은 회의를 배정하는 문제다.
최대한 많은 회의를 배정하기 위해서는 시작 시간 기준이 아니라 끝나는 시간 기준으로 오름차순 정렬을 한 뒤, 가능한 회의들을 진행하는 방법으로 풀어야 한다.
처음에는 끝나는 시간 기준으로만 정렬했었는데, 그럴 경우 시작 시간과 끝나는 시간이 같은 경우는 체크하지 못하고 넘어갈 수 있다. 그래서 기준을 두개로 정렬해주니 해결되었다.
lambda 정렬 기억하기!!

import sys

input = sys.stdin.readline
N = int(input())
time_schedule = []
for n in range(N):
    time_schedule.append(list(map(int, input().split(' '))))
time_schedule.sort(key = lambda x: (x[1], x[0]))
end_time = 0
count = 0
for meeting in time_schedule:
    if meeting[0] >= end_time:
        end_time = meeting[1]
        count += 1
    else:
        continue
print(count)

백준 11399번 - ATM

시간이 적게 걸리는 사람부터 인출을 했을 때, 전체 평균 소요시간이 줄어들게 된다.

import sys
input = sys.stdin.readline
N = int(input())
times = list(map(int, input().split(' ')))
times.sort()

for n in range(1, N):
    times[n] = times[n-1] + times[n]

print(sum(times))

백준 1541번 - 잃어버린 괄호

수식을 최소로 하기 위해서는 '-' 뒤 '+'로 이루어진 식을 괄호로 묶어야 한다.

import sys

S = list(map(str, sys.stdin.readline().split('-')))
nums = []
for s in S:
    if '+' in s:
        tmp = list(map(int, s.split('+')))
        nums.append(sum(tmp))
    else:
        nums.append(int(s))

sum_ = nums[0]
for num in nums[1:]:
    sum_ -= num

print(sum_)

백준 13305번 - 주유소

이 문제는 기름 값이 최소가 되게 하는 것이다.
그러기 위해 기름 가격 기준으로 정렬을 해주어야 하며, 그 전 몇번째 마을인지를 기록하기 위해 [인덱스, 기름 가격]의 이차원 배열로 만들어서 정렬해주었다.
그 다음으로는 기름 가격이 낮은 마을부터 아직 안들린 위치를 tmp로 처리해서 낮은 마을부터 모든 뒤에 있는 마을을 갈 수 있는 양의 기름값을 구매하도록 계산했다.

import sys

input = sys.stdin.readline
N = int(input())
distance = list(map(int, input().split(' ')))
price = list(map(int, input().split(' ')))
prices = []
for p in range(len(price)):
    prices.append([p, price[p]])

prices.sort(key = lambda x:(x[1], x[0]))
tmp = N-1
result = 0
for price in prices:
    if tmp > price[0]:
        result += price[1] * sum(distance[price[0]:tmp])
        tmp = price[0]
        
print(result)