문제 https://www.acmicpc.net/problem/2343 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 문제 접근 나이브한 접근법으로는 블루레이의 크기를 1씩 올려가며 몇 개의 블루레이 디스크가 나올 수 있는지를 확인하는 것이다. 1씩 증가시켜 확인할 때 M개의 블루레이 디스크로 나뉘어질 수 있다면 해당 크기를 반환하고 종료하는 코드를 구현하면 될 것이다. 하지만 해당 방식을 사용하면 매우 비효율적일 수 있다. 당장 강의의 수가 10만까지 올라갈 수 있고, 각 강의의 길이가 1만분까지로 되어 있을 때..

문제 https://www.acmicpc.net/problem/2805 2805번: 나무 자르기 첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보 www.acmicpc.net 문제 접근 $N$과 $M$이 매우 크기 때문에 일반적인 완전탐색 알고리즘으로는 해결할 수 없다. 따라서 다른 방식을 찾아야 한다. 적어도 $O(logN)$이 되어야 할 것이다. 적어도 M미터의 나무를 가져가야 하는데 목재 절단기의 높이 $H$를 이분 탐색으로 확인할 수 있다. 가져가려하는 나무의 길이 M은 모든 나무의 높이 합까지 될 수 있기 때문에 절..

문제 https://www.acmicpc.net/problem/17266 17266번: 어두운 굴다리 인하대학교 후문 뒤쪽에는 어두운 굴다리가 있다. 겁쟁이 상빈이는 길이 조금이라도 어둡다면 가지 않는다. 따라서 굴다리로 가면 최단거리로 집까지 갈수 있지만, 굴다리는 어둡기 때문에 빙 www.acmicpc.net 문제 접근 나이브한 풀이로는 완전 탐색을 사용하는 방법이 있다. 가장 심플한 풀이 방식으로 가로등의 높이로 있을 수 있는 모든 범위($1 \leq h \leq N$)에 대하여 길의 모든 부분이 밝혀질 수 있는지를 체크하는 방법을 사용하는 것이다. 하지만 해당 방식을 사용하면 적어도 $O(N^2)$의 시간이 걸리기 때문에 $h$가 10만까지 올라가는 특성 상 시간 초과가 나게 될 것이다. 다른 방..

문제 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 문제 접근 이분 탐색의 유형인데 주어진 집의 데이터를 가지고 이분 탐색을 진행하는 것이 아니다. 문제에선 두 공유기 사이의 최대 거리를 요구하고 있기 때문에 이분 탐색으로서 우리가 찾아야 하는 값은 바로 두 공유기 사이의 최대 거리이다. 따라서 가장 작은 범위는 각 집마다 공유기를 한 개씩 설치함으로서 얻어지는 0이 되며, 가장 큰 범위는 ..

이분 탐색이란? 이분 탐색(Binary Search)는 탐색 기법 중 하나로, 어떠한 데이터 리스트 L이 존재할 때 어떤 두 점을 지정하여 그 중간값을 보고 찾는 데이터와 비교하여 각 점의 위치를 옮기는 방법이다. 해방 방법을 사용하면 리스트의 길이가 N 일때, 매 번 2배씩 탐색 범위가 좁아지기 때문에 최종적으로 $O(logN)$이 된다. 일반적으로 탐색에 소요되는 시간이 $O(N)$임을 생각하면 효율적인 방법이다. 시간적으로 더 효율적인 대신에 하나의 제한 조건이 있다. 바로 데이터 리스트가 정렬되어 있어야 한다는 것이다. 이는 이진 탐색이 찾는 데이터와 현재 데이터를 비교하여 대소 유무에 따라 다음 위치를 결정하는 것이기 때문이다. 예시 문제 예시 문제로 백준의 숫자 카드가 있다. https://w..