[BAEKJOON] 탐욕법 뽀개기 | 파이썬 | 백준 Lv16. 그리디 알고리즘 문제풀이

BAEKJOON 백준 코딩테스트 단계별로 풀어보기 > LEVEL16. 그리디 알고리즘https://www.acmicpc.net/step/33

그리디 알고리즘 단계

 

탐욕법이란(Greedy)란

매 순간 현재 상황에서 최선의 답(가장 좋아보이는 답)을 고르는 것이다. 현재의 답이 나중에 미칠 영향을 생각하지 않는다.

그리디 알고리즘으로 문제를 풀기 위해서는 문제 해결을 위한 최소한의 아이디어가 필요하다.

* 문제 풀이에 필요한 최소한의 아이디어는 주로 주어진 문제 조건을 통해 얻을 수 있음

 

 

11047. 동전(0)

총 N 종류의 동전을 갖고 있을 때 갖고 있는 동전들을 이용해 M원을 만들어야한다. 이때 필요한 동전 수의 최솟값을 구하여라.

 

내 풀이) 메모리 30864kb / 시간 72ms

n, k = map(int, input().split())
coins = []
for i in range(n):
    coins.append(int(input()))

answer = 0 # 정답 동전의 수
total = 0 # 확인을 위한 동전들의 총 금액
for coin in coins[::-1]: # 최소 개수를 구해야하기 때문에 가장 단위가 큰 동전부터 고려하는 것이 탐욕법
    if (k - total) >= coin:
        answer = answer + (k-total)//coin 
        total = total + (k-total)//coin * coin
    else:
        pass
    
    if total == k:
        print(answer)
        break

이 문제의 아이디어는 최소 개수를 구하기 위해 가장 단위가 큰 동전부터 고려해야 한다 이다.

동전의 단위가 오름차순으로 입력되기 때문에 뒤에서부터 반복문을 돌면서 해당 금액에 동전이 몇개 쓰이는지 확인한다.

 

 

1931. 회의실 배정

N개의 회의의 시작 시간과 종료 시간이 주어진다. 여기서 특정 회의 시작 시간과 종료 시간이 같을수도 있다.

회의실에서는 한번에 하나의 회의만 진행 가능하며 이전 회의가 완벽히 끝나야지만 다음 회의가 진행된다. 회의실에서 진행할 수 있는 최대 회의 수를 구하여라.

 

내 코드1) 메모리 57780kb / 시간 4416ms

n = int(input())
meetings = []
for i in range(n):
    meetings.append(list(map(int, input().split())))
    
meetings.sort(key=lambda x: (x[1], x[0])) # 더 많은 회의 진행을 위해 빨리 끝나는 회의 -> 빨리 시작하는 회의 순으로 정렬

answer = 1
end_time = meetings[0][1] # 첫번째 회의 끝나는 시간
for meeting in meetings[1:]:
    if end_time <= meeting[0]: # 앞의 회의 끝나는 시간이 다음 회의 시작하는 시간보다 이를 때 다음 회의 진행 가능
        answer += 1
        end_time = meeting[1]
        
print(answer)

접근하는 방법이 잘 생각이 안나서 구글링을 조금 하였는데.. 이번 문제의 포인트는 정렬이다!

더 많은 회의 진행을 위해 빨리 끝나는 회의 우선으로 진행해야한다. 그래야 다음 회의를 진행할 수 있기 때문!

가장 먼저 끝나는 회의를 시작으로, 다음 회의 시작시간이 현재 시간(이전 회의 끝나는 시간)보다 늦을 때만 회의를 진행할 수 있다.

 

내 코드2) 메모리 57780kb / 시간 400ms

import sys

n = int(sys.stdin.readline())
meetings = []

for _ in range(n):
    meetings.append(list(map(int, sys.stdin.readline().split())))

meetings = sorted(meetings, key=lambda x: (x[1], x[0]))

answer = 1
end_time = meetings[0][1] 
for meeting in meetings[1:]:
    if end_time <= meeting[0]: 
        answer += 1
        end_time = meeting[1]
        
print(answer)

시간이 너무 오래걸리길래 input() 메서드 대산 sys 라이브러리를 이용하였다. sys.stdin.readLine() 이용하는 것이 확실히 속도가 좋다.

 

 

11399. ATM

ATM 기기는 1대밖에 없고 N명의 사람들이 기다리고있다. N명의 사람들의 돈을 인출하는 시간(기기 사용시간)이 주어진다.

앞의 사람들의 사용시간 동안 뒷사람은 기다려야 하고 한 사람의 인출까지 시간에는 이 기다리는 시간과 기기 사용시간 모두 포함한다.

각 사람이 돈을 인출하는데 필요한 시간의 합이 최소가 될때 그 최솟값이 얼마인가

 

내 코드) 메모리 30864kb / 시간 112ms

import sys
n = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
times = []

for i, num in enumerate(nums):
    times.append((i, num))
times.sort(key=lambda x:x[1]) # 사람 인덱스, 소요 시간

answer = 0
for i in range(1, len(times)+1):
    nums = list(map(lambda x: x[1], times[:i])) # 앞사람들 대기시간 + 본인 인출시간
    answer += sum(nums)

print(answer)

역시나 sys.stdin.readline()으로 시간을 조금 줄일 수 있었다. 프로그래머스에서는 필요없는 전략,,

먼저 사람의 인덱스와 인출시간을 저장하여 인출시간 오름차순으로 정렬한다. 이때의 순서가 대기시간 합이 최소가 되는 순서가 된다.

뒤의 사람일수록 앞 사람의 인출시간 누적이 본인의 대기시간이 됨으로 적은 인출시간을 앞으로 배치하는 것이 이번 문제의 핵심인듯 하다.

대기시간은 본인 앞의 사람들의 대기시간과 본인의 인출시간을 더한 것(sum(nums))이고 이 값들을 모두 더한 것(answer)이 총 대기시간이다. 

 

 

1541. 잃어버린 괄호

숫자와 +, - 연산자로 구성된 수식이 있다. 이에 괄호를 적절히 쳐서 식의 값을 최소로 만들려고 한다.

 

첫 번째 시도) 통과 못함

import sys
ex = sys.stdin.readline().strip()

ex_arr = []
k = 0
answer = 1000000000
oprs = [] # 연산자들

for i in range(len(ex)-1):
    if (ex[i] == '-') or (ex[i] == '+'): # 연산자를 만나면 이전에 나온 숫자 배열에 저장
        ex_arr.append(int(ex[k:i])) # 숫자가 한자리가 아닐 수도 있기 때문에 슬라이싱 이용하여 저장
        ex_arr.append(ex[i])
        k = i + 1
        oprs.append(len(ex_arr)-1) # 연산자 저장
ex_arr.append(int(ex[k:]))

ex_copy = ex_arr.copy()
for opr in oprs: # 가장 먼저 계산할 연산자 선택(괄호 안의 계산이라는 가정)
    ex_arr = ex_copy.copy()
    if ex_arr[opr] == '+':
        ex_arr[opr-1] = ex_arr[opr-1] + ex_arr[opr+1]
    else:
        ex_arr[opr-1] = ex_arr[opr-1] - ex_arr[opr+1]
        
    ex_arr = ex_arr[:opr] + ex_arr[opr+2:]
    tmp = ex_arr[0]
    for i in range(1, len(ex_arr)-1): # 나머지 연산 수행
        if ex_arr[i] == '+':
            tmp += ex_arr[i+1]
        elif ex_arr[i] == '-':
            tmp -= ex_arr[i+1]
    
    answer = min(answer, tmp)
    
print(answer)

모든 경우를 계산하여 완전탐색으로 풀려고 하였다.

주어진 식에서 먼저 숫자와 연산자를 분리한 뒤 각각 배열에 담고 각 연산자들을 순서대로 가장 먼저 실행 후 나머지 연산들을 실행하여 모든 경우를 계산한다.

실패한 이유는.. 이것저것 변수들을 많이 선언하다보니 일단 코드가 난잡하고.. 성공했다 하더라도 수행 시간이 좋지 않다.

 

내 코드) 메모리 30864kb / 시간 68ms

import sys
ex = sys.stdin.readline().strip()

ex = list(ex.split('-'))
answer = sum(map(int, ex[0].split('+'))) # 앞은 모두 +로 연결되어있음으로 더해줌
for e in ex[1:]:
    answer -= sum(map(int, e.split('+')))
print(answer)

구글링을 통해 다른 사람들의 방식을 참고했다 ㅠ

이 문제의 중요한 포인트는 괄호는 한번만 칠 수 있다는 점과 연산자는 +와 -밖에 없다는 점

전체적으로 마이너스 기준으로 (...)-(...) 이렇게 묶일 수 있고 최소가 되려면 앞의 합이 가장 작아야한다.

그러기 위해서는 처음 나오는 마이너스를 기준으로 계산하는 것이 앞의 합이 가장 작은 경우가 된다.

 

 

13305. 주유쇼

N개의 도시가 일직선 위에 있다. 각 도시에서 충전할 수 있는 기름의 리터당 가격과 도시 사이 도로의 길이 정보가 주어진다.

가장 왼쪽 도시에서 오른쪽 도시까지 갈 때 드는 기름의 최소 비용을 구하여라

첫 번째 시도) 17점

import sys
n = int(sys.stdin.readline())
roads = list(map(int, sys.stdin.readline().split()))
prices = list(map(int, sys.stdin.readline().split()))
min_price = min(prices[:-1])

answer = 0
for i in range(n): # 마지막 주유소는 필요없음
    if prices[i] > min_price:
        answer += (prices[i]*roads[i])
    else:
        answer += (prices[i]*sum(roads[i:]))
        break
print(answer)

주유 가격이 가장 최소인 도시를 만나면 그곳에서 남은 거리만큼 모든 주유를 하고 그 이전에는 해당 도시에서 다음 도시까지 필요한 만큼만 주유를 하면 된다고 생각

하지만 최소 가격을 만나기 전, 더 적은 비용으로 충전할 수 있는 반례가 있어서 실패

예로 도시별 주유 가격이 [5, 3, 4, 3, 2, ..]이고 도로 길이가 모두 1일때 주유 가격 2를 만나기 전까지 5+3+4+3 보다 5+3+3+3 이 더 저렴하게 됨

 

정답 코드) 메모리 30864kb / 시간 148ms

import sys
n = int(sys.stdin.readline())
roads = list(map(int, sys.stdin.readline().split()))
prices = list(map(int, sys.stdin.readline().split()))

answer = 0
min_price = prices[0]

for i in range(n-1):
    if min_price > prices[i]:
        min_price = prices[i]
    answer += min_price * roads[i]
    
print(answer)

다른 사람의 코드를 참고하여 풀었다.

내가 처음에 생각했던 방법과 유사하지만 내가 해결하지 못한 반례를 해결하였다.

나는 리스트를 처음 받았을 때 전체에서 최소 가격을 구하였지만 이 방법에서는 가격 리스트를 순회하며 최솟값을 갱신해준다.

예를 들어 [5, 3, 4, 3, 2, ..]에서 이전 방법에서는 5+3 다음 4가 더해졌었는데 이번 방법에서는 3이 계속 최솟값임으로 3이 더해진다.

 

 

문제를 푸는데 머리 쓰는 연습을 더 해야할 듯!