1. 결정 알고리즘
뮤직비디오(결정알고리즘)
문제
지니레코드에서는 불세출의 가수 조영필의 라이브 동영상을 DVD로 만들어 판매하려 한다.
DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지되어야 한다.
순서가 바뀌는 것을 우리의 가수 조영필씨가 매우 싫어한다.
즉, 1번 노래와 5번노래를 같은 DVD에 녹화하기 위해서는 1번과 5번 사이의 모든 노래도 같은 DVD에 녹화해야한다.
또한 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안된다.
지니레코드 입장에서는 이 DVD가 팔릴 것인지 확신할 수 없기 때문에 이 사업에 낭비되는 DVD를 가급적 줄이려고 한다.
고민 끝에 지니레코드는 M개의 DVD에 모든 동영상을 녹화하기로 하였다.
이 때 DVD의 크기(녹화 가능한 길이)를 최소로 하려고 한다.
그리고 M개의 DVD는 모두 같은 크기여야 제조원가가 적게 들기 때문에 꼭 같은 크기로 해야 한다.입력 설명
첫째 줄에 자연수 N(1≤N≤1,000), M(1≤M≤N)이 주어진다. 다음 줄에는 조영필이 라이브에서
부른 순서대로 부른 곡의 길이가 분 단위로(자연수) 주어진다. 부른 곡의 길이는 10,000분을
넘지 않는다고 가정하자.
출력 설명
첫 번째 줄부터 DVD의 최소 용량 크기를 출력하세요.
입력 예제 1
9 3
1 2 3 4 5 6 7 8 9
출력 예제 1
17
해설
이 문제에서 각 노래는 쪼갤 수 없으며 결국 DVD의 길이를 범위로 두고 결정 알고리즘을 돌려야한다. DVD의 길이는 1부터 모든 노래의 길이의 합인 45까지로 여기서 핵심은 노래를 쪼갤 수 없으니까 검증 함수를 만들어서 돌리면서 카운팅을 해야하는 것이다. 또한 M개가 주어지니 M개의 갯수와 카운팅 함수의 결과를 비교하면서 갯수가 많으면 길이가 각 DVD의 길이가 짧다는 거니 탐색 범위를 위로 올리고 그와 반대면 탐색 길이를 아래로 내리되 DVD 갯수가 m이랑 같다는 것이니 그 중간점이 답이라는 것이다.
갯수를 세는 함수에서 중간점을 인수로 받는 이유는 일단 dvd의 길이를 중간점으로 잡고 갯수를 세기 때문이다. 캐패시티를 넘으면 전까지를 한데 묶어 갯수를 1을 올리고 출발점(sum)을 i로 잡고 시작한다.
개인적으로 많이 나오는 문제라고 느꼈지만 또한 어렵다고 느낀 문제이다. 이런 유형에 익숙해져야한다고 생각한다.
코드 구현
def Count(capacity):
cnt = 1
sum = 0
for i in lst:
# 누적합이 캐패시티 넘을 때
if (sum+i)>capacity:
# dvd 갯수 한 번 세주고
cnt+=1
# 현재 기준의 음악을 새로 잡아서 계산하자
sum = i
# 넘지 않으면 계속 더해준다.
else:
sum+=i
return cnt
n, m = map(int,input().split())
lst = list(map(int,input().split()))
plus_list = [0]*9
mx = max(lst)
s = 1 #1분이 최소
e = sum(lst)
res = 0
while s<=e:
middle = (s+e)//2
# 갯수를 출력, 미들을 총합의 기준으로 두고 제한
# 미들은 dvd의 용량
if Count(middle) > m:
s = middle + 1
# 갯수가 m이랑 같아도 가능
# 미들이 적어도 리스트의 가장 긴 노래보다 같거나 커야한다.
# 무작정 갯수가 m보다 작거나 같다고 허용하면 안됨, 그럼 노래 길이 문제가 생긴다.
elif middle >= mx and Count(middle) <= m:
# 여기서 답을 정해주어야함
res = middle
e = middle - 1
# 최솟값을 뽑으랬으니 미들 바로 위를 뽑아라
print(res)2. 그리디 알고리즘
침몰하는 타이타닉(그리디 알고리즘)
문제
유럽에서 가장 유명했던 유람선 타이타닉이 침몰하고 있습니다. 유람선에는 N명의 승객이 타고있습니다.
구명보트를 타고 탈출해야 하는데 타이타닉에 있는 구명보트는 2명 이하로만 탈 수 있으며,
보트 한 개에 탈 수 있는 총 무게도 M kg 이하로 제한되어 있습니다.
N명의 승객 몸무게가 주어졌을 때 승객 모두가 탈출하기 위한
구명보트의 최소개수를 출력하는 프로그램을 작성하세요.입력 설명
첫째 줄에 자연수 N(5<=N<=1000)과 M(70<=M<=250)이 주어집니다.
두 번째 줄에 N개로 구성된 몸무게 수열이 주어집니다. 몸무게는 50이상 150이하입니다.
각 승객의 몸무게는 M을 넘지는 않습니다. 즉 탈출을 못하는 경우는 없습니다.
출력 설명
첫째 줄에 구명보트의 최소 개수를 출력합니다.
입력 예제 1
5 140
90 50 70 100 60
출력 예제 1
3
해설
그리디 알고리즘 -> 정렬 후 기준에 맞춰 최대 혹은 최소를 조사하는 알고리즘으로 외워두면 편할 것이다.
일단 정렬이 우선되어야 차례차례 비교가 가능하다. 리버스를 할 수 도 있고 튜플을 통해 정렬할 수 도 있으니 유념하기 바란다.
이 문제의 경우 양 쪽 끝을 동시에 비교하는 방식으로 최대 2명이라는 조건이 존재하기 때문에 가능하다. 양쪽 끝 -> 투 포인터 생각이 가능 하지만 이 문제에서는 deque를 사용해서 pop(), popleft() 이 둘의 메서드를 적극 사용하는 모습을 보인다. 이 것은 BFS 구현 문제에서 끊임없이 pop()을 하면서 비교하는 느낌이다. 양 쪽을 더했을 때 리미트 중량을 넘어가면 앞 쪽만 pop()하고 양 쪽을 더한게 리미트보다 아래면 pop()과 popleft()를 하면서 동시에 뺀다.
주의할 점은 이 덱의 길이로 길이가 하나 남을 때는 비교가 힘들어지기에 조건문을 만들고 갯수 + 1과 브레이크를 걸어주는 것이 중요하다. 안 걸어주면 무한 루프 돈다.
코드 구현
import sys
from collections import deque
sys.stdin = open("input.txt", "rt")
n, m = map(int,input().split())
# 리스트는 pop하면 뒤에 자료들이 당겨지는 연산을 해서 비효율적이다.
# 이런게 시간을 잡아 먹으니 빼고 넣을 때는 deque를 쓰는게 좋다.
line = list(map(int, input().split()))
line.sort()
line = deque(line)
print(line)
# 그리디 -> 정렬 혹은 역정렬 -> 최대한 셀 수 있는 방안 구상
# 투 포인터로 양쪽 끝에서 더해야 최대로 셀 수 있다.
# 가우스 계산법과 같은 느낌
# 둘이 더한게 리미트를 넘어가면 오른쪽만 pop(len(line)-1) 하면 된다.
# 둘이 더한게 리미트 아래면 둘 다 pop
# 이후에 포인터를 옮긴다.
# s = 0
# e = n - 1
cnt = 0
limit = m
# line이란 deque에 원소가 존재하는 동안
# 핵심 그리디 알고리즘
# deque를 쓰는 방법을 외워두자
while line:
if len(line) == 1:
cnt+=1
break
if line[0] + line[-1]>limit:
line.pop()
cnt+=1
else:
# deque의 효율적인 메서드
line.popleft()
line.pop()
cnt+=1
print(cnt)