1. 이진 탐색
•
정의) 데이터가 정렬되어 있는 상태에서 원하는 값 찾아내는 알고리즘
•
특징)
◦
중앙값 비교를 통한 대상 축소 방식
▪
대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾음
◦
시간 복잡도 : O(logN)
•
과정) 오름차순 정렬일 때 (내림차순이라면 조건을 반대로 하면 됨)
1.
현재 데이터셋의 중앙값을 선택
2.
중앙값 > 타깃 데이터일 때 중앙값 기준으로 왼쪽 데이터 셋을 선택
3.
중앙값 < 타깃 데이터일 때 중앙값 기준으로 오른쪽 데이터 셋을 선택
4.
중앙값 == 타깃 데이터일 때 탐색을 종료
•
코드) 재귀로 구현 low high. 2 3 4
int target;
int[] arr;
int binarySearch(int low, int high) {
if (low > high) return -1;
mid = (low + high) / 2;
if (target < arr[mid]) return binarySearch(low, mid-1);
else if (target > arr[mid]) return binarySearch(mid+1, high);
else return mid; // 타깃 찾았으니 탐색 종료
}
Java
복사
•
코드) 반복문으로 구현
int target;
int[] arr;
int binarySearch() {
int low = 0;
int high = N-1;
while (low <= high) {
mid = (low + high) / 2;
if (arr[mid] > target) high = mid - 1;
else if (arr[mid < target) low = mid + 1;
else return mid;
}
return -1;
}
Java
복사
•
팁)
◦
중복값이 존재하는 배열 안에 특정 원소 반복 횟수 = key 초과의 값이 처음 나오는 위치 - key 이상의 값이 처음 나오는 위치
◦
이분탐색이 멈추는 조건이 low > high인 이유
▪
low와 high이 동일한 순간이 탐색 범위가 1만큼인 순간인데,
▪
이 때, 탐색한 그 하나의 값이 타깃과 일치하지 않으면 타깃보다 작던 크던 low > high이 됨
▪
왜냐하면, 그 값이 타깃보다 작으면 low가 +1될 테고, 그 값이 타깃보다 크면 high이 -1이 되기에 뭐가 되든 low와 high은 역전됨
◦
이분탐색으로 특정 타겟이 아닌 최솟값 혹은 최댓값을 찾아야 할 때
▪
ex. 백준 7795번) 타깃보다 작은 수 몇 개인지 구하기 5 → {1,2,5,6,7}
int res = 0;
while (L <= R) {
int mid = (L + R) / 2;
if (A[mid] < target) { // mid가 타깃보다 작음
res = mid;
L = mid + 1; // mid보다 큰 쪽 탐색
} else { // mid가 타깃보다 크거나 같음
R = mid - 1; // mid보다 작은 쪽 탐색
}
}
return res;
Java
복사
•
mid가 타깃보다 작을 때
◦
정답을 현재 mid의 위치로 갱신
◦
타깃이 mid보다 크므로, 탐색 범위를 mid보다 큰 쪽으로 변경
•
mid가 타깃보다 크거나 같을 때 → 핵심 : 같을 때 탐색을 마치지 않는다.
◦
타깃이 mid보다 작으므로, 탐색 범위를 mid보다 작은 쪽으로 변경
▪
실제론 타깃과 mid가 같은데도, 타깃을 mid보다 작다고 취급한 이유는 우리가 찾아야 하는 건 타깃 그 자체가 아닌 타깃보다 작은 값 중 가장 큰 수이기 때문임.
▪
물론, 이 문제에 한해선 사실 타깃을 발견했을 때 탐색을 멈추고, 타깃 - 1을 정답으로 내놓아도 됨. 하지만 아예 이분법적으로 탐색하는 법을 배우기 위해 일단 따라 더 생각해보자. 매개 변수 탐색을 풀 때 도움이 되는 사고를 배울 수 있음.
▪
여기서 타깃보다 작은 쪽을 더 탐색해서 얻을 수 있는 건, 타깃보다 작은 숫자만 있는 곳에서 이분 탐색을 실행하면 결국 계속 큰 쪽을 탐색하려 하다보니 작은 숫자들 사이에서 가장 큰 숫자 하나만 탐색 구간에 들어갔을 때 탐색이 종료됨
▪
결국 원하는 결과를 얻을 수 있음. 이 원리를 아래 문제에서 더 활용해보겠음.
▪
ex. 매개변수 탐색) yes, yes, … no, no… 형태에서 yes 몇 개인지 구하기
•
최초로 “no”가 나오는 곳을 타깃으로 생각한다.
int res = 0;
while (L <= R) {
int mid = (L + R) / 2;
if (A[mid] == "yes") { // mid가 yes임
res = mid;
L = mid + 1; // mid보다 큰 쪽 탐색
} else { // mid가 no임
R = mid - 1; // mid보다 작은 쪽 탐색
}
}
return res;
Java
복사
•
mid가 yes일 때 == mid가 타깃(no가 나오는 최초 지점)보다 작을 때
◦
정답을 현재 mid의 위치로 갱신
◦
타깃이 mid보다 크므로, 탐색 범위를 mid보다 큰 쪽으로 변경
•
mid가 no일 때 == mid가 타깃(no가 나오는 최초 지점)보다 크거나 같을 때
◦
타깃이 mid보다 작으므로, 탐색 범위를 mid보다 작은 쪽으로 변경
▪
ex. 백준 2343번) no no, …, yes, yes… 형태에서 최초로 yes가 나오는 곳 찾기 (no 개수 + 1)
•
최초로 “yes”가 나오는 곳을 타깃으로 생각한다.
int res = 0;
while (L <= R) {
int mid = (L + R) / 2;
if (A[mid] == "no") { // mid가 no임
res = mid;
L = mid + 1; // mid보다 큰 쪽 탐색
} else { // mid가 yes임
R = mid - 1; // mid보다 작은 쪽 탐색
}
}
return res + 1;
Java
복사
2. 매개변수 탐색 (parametric search)
•
정의) 최적화 문제를 결정 문제로 바꾸어 푸는 기법
◦
최적화 문제 : 최솟값/최댓값을 요구하는 문제 (ex. 지금까지 푼 문제 중 가장 어려운 문제의 난이도는?)
◦
결정 문제 : 답변이 true/false 형태로 나오는 문제 (ex. 너 실버 1 문제 풀 수 있니?)
◦
최적화 문제를 결정 문제로 바꿀 수 있음 (ex. 모든 난이도에 대해 ‘너 이 난이도의 문제 풀 수 있니?’를 물어보기)
•
특징)
◦
특정 파라미터를 기준으로 조건을 만족하는 부분과 만족하지 않는 경계점 탐색
▪
ex. 실버5~1까지 차례대로 물었을 때, 실버5~2까진 풀수 있다고 답했는데 실버 1은 못풀었다고 답하면 그 사이가 경계점임
•
과정)
1.
정답(구해야 하는 값)을 매개변수로 만들고, yes/no 문제로 바꿔보기
2.
모든 값에 대해서 yes/no를 채웠다고 생각했을 때, 정렬된 상태인지 확인하기
•
yes. yes. yes. / no. no 처럼 정렬되어야 함
3.
yes/no를 결정하는 문제로 해결하기
•
매개변수가 가능한 범위를 전부 배열에 넣어두고 그 배열에서 이분 탐색한단 느낌으로 짜면 됨.
// 매개변수가 가능한 범위 : 2,3,...10, 20
private static int[] parameters; // {2,3,...,10,20으로 초기화}
private static long binarySearch() {
long result = 0;
long left = 0; // 매개변수 범위의 맨 앞값 인덱스
long right = parameters.length - 1; // 매개변수 범위의 맨 뒷값 인덱스
while (left <= right) {
long mid = (left + right) / 2;
if (isPossible(parameters[mid])) {
result = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
Java
복사
•
아마, 실제로 배열을 만들어 푼다면 메모리 초과가 뜰 확률이 높은데, 그럴 땐 배열 만들지 않고 start, end, mid를 잘 활용해서 매개변수 배열의 값 다루듯 쓰면 됨 (왠만하면 이 방식으로 풀 길 권장. 너무 이해가 안될 때만 위의 배열 만드는 방식으로 풀어보기)
// 매개변수가 가능한 범위 : 2,3,...10, 20
private static long binarySearch() {
long result = 0;
long left = 2; // 매개변수 범위의 맨 앞값
long right = 20; // 매개변수 범위의 맨 뒷값
while (left <= right) {
long mid = (left + right) / 2;
if (isPossible(mid)) {
result = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
Java
복사
•
팁)
◦
“~의 최댓값/최솟값을 구하시오” 문제에 대해 매개 변수 탐색 시도해볼 가치가 있음
◦
최적화 문제를 결정 문제로 바꾸기 == 질문의 앞뒤를 바꿔서 정답을 매개변수로 두게 하기)
▪
ex. 백준 2343번)
•
최적화 문제
◦
Q) (모든 그룹이 들어갈 수 있는) 최소 (크기)는 몇 이니? → 9~45
◦
A) 17
•
결정 문제
◦
Q) 어떤 (크기)에 (모든 그룹이 들어갈 수 있니)?
◦
A) O/X
▪
ex. 백준 2805번)
•
최적화 문제
◦
Q) (원하는 길이 M만큼을 얻을 수 있는) 최대 (높이)는 얼마니?
◦
A) 5
•
결정 문제
◦
Q) 어떤 (높이)로 잘랐을 때 (원하는 길이 M만큼을 얻어갈 수 있니)?
◦
A) O/X
참고