이분 탐색
백준 22871번 : 징검다리(large)
https://www.acmicpc.net/problem/22871 22871번: 징검다리 건너기 (large) $N$개의 돌이 일렬로 나열 되어 있다. $N$개의 돌에는 수 $A_{1} A_{2} ... A_{i} ... A_{N}$로 부여되어 있다. 가장 왼쪽에 있는 돌에서 출발하여 가장 오른쪽에 있는 돌로 건너가려고 한다. 항상 오른쪽으 www.acmicpc.net 이분 탐색 카테고리 문제를 풀다가 접하게 된 문제다. 연산시간 때문에 하루종일 이 문제만 붙잡고 고민했다. 최적화 하려는 변수가 M이라면 보통 이분탐색 문제는 O(log M) 시간안에 해결이 가능하거나 그 보다 오래 걸리더라도 주어진 시간 안에 해결이 가능했다. 관련하여 문제를 풀면서 고민한 것들을 글에 풀어서 써보겠다. N개의 징검다리..
백준 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 2110번에서 알게된 내용들을 적용해서 생각보다 쉽게 푼 문제다. M명의 사람들은 입국하기위해 입국심사를 받는다. 심사대는 총 N개가 있고 심사대마다 심사에 소요되는 시간이 정해져있다. M명의 사람들을 모두 통과시키는 최소한의 시간을 구하는 문제이다. 앞서 푼 문제에서 배운 이분 탐색의 요령을 그대로 적용했다. 구하려는 값은 시간이기 때문에 가능한 범위 안에서 조건(시간 안에 사람들..
백준 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 우아한 테크코스 코딩테스트를 준비할겸 기초 알고리즘을 복습하기 위해 접했던 이분 탐색 문제다. 기존에 풀었던 이분 탐색 문제와 달리 바로 해결 아이디어가 떠오르지 않아서 질문 게시판을 참고해서 해결했다. 일직선(1차원) 좌표상의 특정 좌표에 집이 존재하고 주어진 개수만큼의 공유기를 집에 설치하고자 한다. 공유기는 한 집에 1개만 설치가능하며 주어..