Binary Search 배열에서 원하는 값의 위치를 O(log N) 만에 찾는 방법 ⇔ 순차탐색 O(N) 배열 내 원소가 정렬된 경우에만 사용 가능 정렬되지 않은 배열의 경우, 찾고자 하는 숫자의 개수가 적다면 순차탐색이 빠를 수 있음 아래는 찾고자 하는 값이 없는 경우 -1을, 있는 경우에는 해당 위치를 반환해주는 Binary Search 코드이다. up/down 게임과 유사한 방식으로 원하는 값의 위치를 찾아가는 것을 볼 수 있다. int binary_search(int target){ int low=1, mid, high=n; while(low

문제 문제 바로가기> BOJ 2110번: 공유기 설치 2110번: 공유기 설치 첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 www.acmicpc.net 풀이 #include #include #define INF 1000000001 #define MAX_HOME 200001 using namespace std; int N, C; int home[MAX_HOME]; void input() { cin >> N >> C; for (int i = 0; i > home[i]; sort(hom..

문제 문제 바로가기> BOJ 2343번: 기타 레슨 2343번: 기타 레슨 강토는 자신의 기타 강의 동영상을 블루레이로 만들어 판매하려고 한다. 블루레이에는 총 N개의 강의가 들어가는데, 블루레이를 녹화할 때, 강의의 순서가 바뀌면 안 된다. 순서가 뒤바뀌는 경 www.acmicpc.net 풀이 매개 변수 탐색을 이용해서 가능한 블루레이의 크기 중 최소를 구하는 문제다. 주의할 점은 상한(high)을 설정하는 부분이다. 처음에 high를 10,001으로 설정했는데 바로 틀렸다,, 생각해보니, 각 강의의 길이가 10,000분을 넘지 않는 것이지, 블루레이의의 크기는 당연히 10,000분을 넘을 수 있기 때문!! 이 부분을 주의해 줘야 할 것 같다! 각 강의당 길이가 10,000분이므로, 10000*1000..