파라메트릭 서치 알고리즘

[JavaScript/section 7] 12 - 마구간 정하기

2022.10.12

📌 12 - 마구간 정하기(결정 알고리즘) N개의 마구간이 수직선상에 있습니다. 각 마구간은 x1, x2, ..., xN의 좌표를 가지며, 마구간간에 좌표과 중복되는 일은 없습니다. 각 마구간에는 한 마리의 말만 넣을 수 있고, 가장 가까운 두 말의 거리가 최대가 되게 말을 마구간에 배치하고 싶습니다. C마리의 말을 N개의 마구간에 배치했을 때 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 출력해보자! 입력설명 첫 줄에 자연수 N과 C가 공백을 사이에 두고 주어진다. 둘째 줄에 마구간의 좌표가 차례로 주어진다. 출력설명 첫 줄에 가장 가까운 두 말의 최대 거리를 출력한다. 입력예제 5 3 1 2 8 4 9 출력예제 3 👍 풀이 방법 가장 가까운 두 말의 거리가 최대가 되는 그 최대값을 구하는 문제..

Algorithm/인프런(inflearn)

[JavaScript/section 7] 11 - 뮤직 비디오

2022.10.10

📌 11 - 뮤직 비디오(결정 알고리즘) DVD에는 총 N개의 곡이 들어가는데, DVD에 녹화할 때에는 라이브에서의 순서가 그대로 유지되어야 한다. 즉 1번 노래와 5번 노래를 같은 DVD에 녹화하기 위해서는 1번과 5번 사이의 모든 노래도 같은 DVD에 녹화해야 한다. 또한, 한 노래를 쪼개서 두 개의 DVD에 녹화하면 안된다. M개의 DVD에 모든 동영상을 녹화하기로 했다. 이 때 DVD의 크기를 최소로 하려고 한다. 그리고 M개의 DVD는 모두 같은 크기여야 제조원가가 적게 들기 때문에 꼭 같은 크기로 해야 한다. 위 문제를 정리해보면 M개의 같은 크기를 가지고 있는 DVD에 음악을 담아야 하는데, 그 크기가 가장 최소가 되는 값을 찾는 문제이다. 특정한 상황에서 최적의 값을 구해야 하므로 이분 탐..

[JavaScript/section 7] 12 - 마구간 정하기

[JavaScript/section 7] 11 - 뮤직 비디오

티스토리툴바