이분 탐색

[Silver II] 과자 나눠주기 - 16401 문제 링크 성능 요약 메모리: 144000 KB, 시간: 740 ms 분류 이분 탐색, 매개 변수 탐색 제출 일자 2024년 1월 19일 14:22:10 문제 설명 명절이 되면, 홍익이 집에는 조카들이 놀러 온다. 떼를 쓰는 조카들을 달래기 위해 홍익이는 막대 과자를 하나씩 나눠준다. 조카들이 과자를 먹는 동안은 떼를 쓰지 않기 때문에, 홍익이는 조카들에게 최대한 긴 과자를 나눠주려고 한다. 그런데 나눠준 과자의 길이가 하나라도 다르면 조카끼리 싸움이 일어난다. 따라서 반드시 모든 조카에게 같은 길이의 막대 과자를 나눠주어야 한다. M명의 조카가 있고 N개의 과자가 있을 때, 조카 1명에게 줄 수 있는 막대 과자의 최대 길이를 구하라. 단, 막대 과자는 ..

[Gold IV] 구간 나누기 2 - 13397 문제 링크 성능 요약 메모리: 69560 KB, 시간: 12 ms 분류 이분 탐색, 매개 변수 탐색 제출 일자 2024년 1월 18일 12:25:15 문제 설명 N개의 수로 이루어진 1차원 배열이 있다. 이 배열을 M개 이하의 구간으로 나누어서 구간의 점수의 최댓값을 최소로 하려고 한다. 구간은 다음과 같은 조건을 만족해야 한다. 하나의 구간은 하나 이상의 연속된 수들로 이루어져 있다. 배열의 각 수는 모두 하나의 구간에 포함되어 있어야 한다. 구간의 점수란 구간에 속한 수의 최댓값과 최솟값의 차이이다. 예를 들어, 배열이 [1, 5, 4, 6, 2, 1, 3, 7] 이고, M = 3인 경우가 있다. 이때, [1, 5], [4, 6, 2], [1, 3, 7..

[Silver I] 기타 레슨 - 2343 문제 링크 성능 요약 메모리: 76292 KB, 시간: 52 ms 분류 이분 탐색, 매개 변수 탐색 제출 일자 2024년 1월 17일 17:28:28 문제 설명 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경우에는 강의의 흐름이 끊겨, 학생들이 대혼란에 빠질 수 있기 때문이다. 즉, i번 강의와 j번 강의를 같은 블루레이에 녹화하려면 i와 j 사이의 모든 강의도 같은 블루레이에 녹화해야 한다. 강토는 이 블루레이가 얼마나 팔릴지 아직 알 수 없기 때문에, 블루레이의 개수를 가급적 줄이려고 한다. 오랜 고민 끝에 강토는 M개의..

[Silver II] 랜선 자르기 - 1654 문제 링크 성능 요약 메모리: 69240 KB, 시간: 16 ms 분류 이분 탐색, 매개 변수 탐색 제출 일자 2024년 1월 16일 11:23:28 문제 설명 집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다. 이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.) 편의..

Binary Search 이분 탐색(Binary Search)은 탐색 알고리즘 중 가장 효율적인 알고리즘으로, O(log n)의 시간 복잡도를 가지고 있습니다. 이는 균형잡힌 BST에서 탐색을 하는 것과 견줄 수 있습니다. 이분 탐색을 사용하기 전에 두 가지 조건이 선행되어야 합니다. 컬렉션은 상수의 시간 안에 인덱스 조작을 수행할 수 있어야 합니다. 이는 컬렉션이 RandomAccessCollection이어야 한다는 것을 의미합니다. RandomAccess는 인덱스를 통해 컬렉션의 요소에 직접 액세스하는 기능을 말하는데, 이는 O(1)의 시간 복잡도로 원하는 위치에 있는 요소에 접근할 수 있도록 해줍니다. 인덱스를 사용하여 컬렉션 내부에서 요소를 조회, 수정, 삭제하거나 새 요소를 삽입할 수 있는 경우..

[Silver I] 보석 상자 - 2792 문제 링크 성능 요약 메모리: 75352 KB, 시간: 204 ms 분류 이분 탐색, 매개 변수 탐색 제출 일자 2024년 1월 15일 16:08:28 문제 설명 보석 공장에서 보석 상자를 유치원에 기증했다. 각각의 보석은 M가지 서로 다른 색상 중 한 색상이다. 원장 선생님은 모든 보석을 N명의 학생들에게 나누어 주려고 한다. 이때, 보석을 받지 못하는 학생이 있어도 된다. 하지만, 학생은 항상 같은 색상의 보석만 가져간다. 한 아이가 너무 많은 보석을 가져가게 되면, 다른 아이들이 질투를 한다. 원장 선생님은 이런 질투심을 수치화하는데 성공했는데, 질투심은 가장 많은 보석을 가져간 학생이 가지고 있는 보석의 개수이다. 원장 선생님은 질투심이 최소가 되게 보석..

[Gold IV] 공유기 설치 - 2110 문제 링크 성능 요약 메모리: 72236 KB, 시간: 116 ms 분류 이분 탐색, 매개 변수 탐색 제출 일자 2024년 1월 16일 10:46:25 문제 설명 도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다. 도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다. C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오..

[Silver II] 나무 자르기 - 2805 문제 링크 성능 요약 메모리: 155812 KB, 시간: 608 ms 분류 이분 탐색, 매개 변수 탐색 문제 설명 상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다. 목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예..