이분 탐색
일반적으로 배열에서 어떤 수 k를 찾기 위해선 배열의 모든 성분을 하나하나 탐색해야 하므로 시간 복잡도는 O(n)이 된다. 하지만 배열이 정렬되어 있는 상태라면, 이분 탐색이라는 탐색 방법을 이용해 시간 복잡도가 O(log2(n))인 방법으로 탐색할 수 있다.
정렬되어 있는 배열의 범위 [l, r)에서 어떤 수 k가 존재하고 k를 찾고자 할 때, mid = (l + r) / 2에 대해 배열의 mid번째 성분이 k보다 작다면 k는 범위 [l, mid)에, k번째 성분보다 크다면 k는 범위 [mid + 1, r) 안에 존재한다. 따라서 이 과정을 [l, r) 안의 성분이 한 개 이하가 될 때까지 진행하거나, 혹은 배열의 mid번째 성분이 k일 때까지 진행하면 성분 k의 순서를 알 수 있다.
https://www.acmicpc.net/problem/2805
2805번: 나무 자르기
첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000) 둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보
www.acmicpc.net
https://www.acmicpc.net/problem/1654
1654번: 랜선 자르기
첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그
www.acmicpc.net