Algorithm/이분탐색

BOJ 20444 - 색종이와 가위

https://www.acmicpc.net/problem/20444 20444번: 색종이와 가위 첫 줄에 정수 n, k가 주어진다. (1 ≤ n ≤ 231-1, 1 ≤ k ≤ 263-1) www.acmicpc.net 색종이를 자를 때에는 한 변에 평행하도록 n번의 가위질을 했을 때 k개의 색종이 조각을 만들 수 있을까? n번의 가위질 (1 ≤ n ≤ 2^31-1) k개의 색종이 조각 (1 ≤ k ≤ 2^63-1) : long형 변수 아이디어 0.1초라는 적은 시간에 넓은 탐색 범위 안에서 최적의 조건을 찾아야 하므로 이분탐색으로 먼저 접근해보았다. n번의 가위질을 했을 때 k개의 색종이 조각을 만들 수 있는 지 판단해야 한다. 하나씩 해보니 아래와 같은 규칙을 발견했다. 가위질 수 = (가로로 자르는 횟..

BOJ 3079 - 입국심사

문제 https://www.acmicpc.net/problem/3079 3079번: 입국심사 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109) www.acmicpc.net 상근이와 친구들 M명 (1 ≤ M ≤ 10억) 입국심사대 N개 (1 ≤ N ≤ 10만) k번 심사대에 앉아있는 심사관이 한 명을 심사를 하는데 드는 시간은 Tk (1 ≤ Tk ≤ 10억) 모든 사람이 심사를 받는데 걸리는 시간이 최소가 되도록 아이디어 ' 최소 '라는 키워드가 나와서 이분탐색으로 먼저 접근해보았다. 원래 문제 N개의 심사대에 M명의 사람이 심사받을 때 모든 사람..

BOJ 6236 - 용돈 관리

https://www.acmicpc.net/problem/6236 6236번: 용돈 관리 현우는 용돈을 효율적으로 활용하기 위해 계획을 짜기로 하였다. 현우는 앞으로 N일 동안 자신이 사용할 금액을 계산하였고, 돈을 펑펑 쓰지 않기 위해 정확히 M번만 통장에서 돈을 빼서 쓰기로 www.acmicpc.net N일 동안 사용 (1 ≤ N ≤ 100,000) 통장에서 M번만 출금 (1 ≤ M ≤ N) i번째 날에 이용할 금액 (1 ≤ 금액 ≤ 10000) 현우가 통장에서 인출할 최소 금액 K 값은? 아이디어 ' 최소 ' 키워드가 나왔으므로 이분 탐색으로 먼저 접근해보았다. 원래 문제 N일동안 통장에서 M번만 출금할 때 한번에 인출할 최소 금액 K 값은? 최소 금액 K를 매개 변수로 설정하고 문제를 뒤집어서 Y..

BOJ 2343 - 기타 레슨

문제 https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 블루레이 N개의 강의 (녹화 순서 준수) (1 ≤ N ≤ 100,000) 블루레이 M개 (모두 같은 크기) (1 ≤ M ≤ N) 기타 강의 길이 리스트 - 분 단위로(자연수)

BOJ 2110 - 공유기 설치

문제 https://www.acmicpc.net/problem/2110 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 수직선 위 N개의 집 (2 ≤ N ≤ 200,000) 각 집의 좌표 xi (0 ≤ xi ≤ 10억) 공유기 C개 (2 ≤ C ≤ N) 아이디어 집이 5개이고 공유기가 3개인 경우 C개의 공유기를 몇몇 집에 설치할 것인데 가장 인접한 공유기 사이의 거리를 최대가 되도록 설치할 것이다. ' 최대 ' 라는 키워드가 나왔으므로 이분탐색을 먼저 생각..

BOJ 2512 - 예산

https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 지방의 수 N (3

BOJ 1654 - 랜선 자르기

https://www.acmicpc.net/problem/1654 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 길이가 제각각인 K개의 랜선 (1

BOJ 2805 - 나무 자르기

https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net '최댓값'이라는 키워드 나왔으므로 이분 탐색 고려해보기. 원래 문제 원하는 길이 M만큼 얻을 수 있는 최대 절단기 높이는 얼마인가? 매개변수 설정 후 뒤집은 문제 정답인 절단기 높이를 매개변수 H로 설정 어떤 절단기 높이(H)로 잘랐을 때, 원하는 길이 M만큼을 얻을 수 있는가? Yes/No 문제로 변신 위의 Yes/No 문제를 한 번 물어보는 데 걸리는 시..

매개 변수 탐색 (Parametric Search)

Up-Down 게임 - A가 1~1000 사이 어떤 자연수를 선택 - B는 A에게 "생각한 숫자가 X 이상이야?" 라는 질문 가능 - A는 맞으면 1, 아니면 0 대답 - 최소 횟수로 질문하려면? 방법 1) Linear Search 1부터 1000까지 전부 물어보기 "생각한 숫자가 1 이상?" "생각한 숫자가 2 이상?" ... "생각한 숫자가 1000 이상?" -> 마지막 Yes인 대답이 정답! 최악의 경우 1000번 질문해야 한다. 더 빠른 방법은 없을까? 방법 2) Binary Search A가 생각한 숫자를 매개변수로 생각해서 이분탐색으로 찾기 L=1, R=1000인 구간 L~R에서 이분탐색! 탐색할 범위의 중앙 값과 찾아야 할 숫자 K를 비교를 통해 정답이 가능한 구간 [L, R]을 좁혀나가면서..

BOJ 2470 - 두 용액

https://www.acmicpc.net/problem/2470 서로 다른 두 용액을 더해서 합이 최대한 0에 가깝게 만드는 문제 아이디어 각 용액의 범위가 -10억 ~ 10억 이므로 두 용액을 합친 값의 범위는 -20억 ~ 20억이므로 int형 변수로 처리 가능하다. 가장 먼저 생각난 방법은 이중 for문으로 두 용액을 섞을 수 있는 모든 경우를 다 비교해보는 것이다. 이렇게 하면 시간 복잡도가 O(N^2)이 된다. 이러면 N의 최댓값이 10억이니까 100억이 되버리므로 시간이 초과된다. 왼쪽 용액(left)을 골랐을 때 오른쪽 용액을 뭘 골라야 더해서 0에 가장 가까울까를 생각해보면 정렬이 된 용액들 중 A[left]를 고른 후 A[left+1 ~ N] 범위 내에서 -A[left]와 가장 가까운 수..