⭐ 이진 탐색
정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다.
📌 이진 탐색의 시간 복잡도
- 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 log2n에 비례한다.
- 예를 들어 초기 데이터 개수가 32개일 때, 이상적으로 1단계를 거치면 16개가량의 데이터만 남는다.
- 2단계를 거치면 8개가량의 데이터만 남는다.
- 3단계를 거치면 4개가량의 데이터만 남는다.
- 다시 말해 이진 탐색은 탐색 범위를 절반씩 줄이며, 시간 복잡도는 O(logN)을 보장한다.
📝 코드 구현 : 재귀함수를 이용한 이진 탐색
import java.util.*;
public class Main {
// 이진 탐색 소스코드 구현(재귀 함수)
public static int binarySearch(int[] arr, int target, int start, int end) {
if (start > end) return -1;
int mid = (start + end) / 2;
// 찾은 경우 중간점 인덱스 반환
if (arr[mid] == target) return mid;
// 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
else if (arr[mid] > target) return binarySearch(arr, target, start, mid - 1);
// 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
else return binarySearch(arr, target, mid + 1, end);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 원소의 개수(n)와 찾고자 하는 값(target)을 입력받기
int n = sc.nextInt();
int target = sc.nextInt();
// 전체 원소 입력받기
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
// 이진 탐색 수행 결과 출력
int result = binarySearch(arr, target, 0, n - 1);
if (result == -1) {
System.out.println("원소가 존재하지 않습니다.");
}
else {
System.out.println(result + 1);
}
}
}📝 코드 구현 : 반복문을 이용한 이진 탐색
import java.util.*;
public class Main {
// 이진 탐색 소스코드 구현(반복문)
public static int binarySearch(int[] arr, int target, int start, int end) {
while (start <= end) {
int mid = (start + end) / 2;
// 찾은 경우 중간점 인덱스 반환
if (arr[mid] == target) return mid;
// 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
else if (arr[mid] > target) end = mid - 1;
// 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
else start = mid + 1;
}
return -1;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 원소의 개수(n)와 찾고자 하는 값(target)을 입력받기
int n = sc.nextInt();
int target = sc.nextInt();
// 전체 원소 입력받기
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
// 이진 탐색 수행 결과 출력
int result = binarySearch(arr, target, 0, n - 1);
if (result == -1) {
System.out.println("원소가 존재하지 않습니다.");
}
else {
System.out.println(result + 1);
}
}
}📌 Lower/Upper Bound
Lower Bound
찾고자 하는 값이 처음 나타나는 위치
ex) [1, 2, 2, 2, 3]에서 2의 lower bound는 인덱스 1
static int lowerBound(int[] arr, int target) {
int left = 0;
int right = arr.length;
while (left < right) {
int mid = (left + right) / 2;
if (arr[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}Upper Bound
찾고자 하는 값보다 큰 첫 번째 원소의 위치
ex) [1, 2, 2, 2, 3]에서 2의 upper bound는 인덱스 4
static int upperBound(int[] arr, int target) {
int left = 0;
int right = arr.length;
while (left < right) {
int mid = (left + right) / 2;
if (arr[mid] > target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}이진 탐색의 Lower/Upper bound 사용 예시
- 중복 원소 처리
정렬된 배열에서 특정 값이 여러 번 등장할 때 첫 위치나 마지막 위치를 찾아야 하는 경우
- 범위 쿼리
특정 범위 내의 원소 개수 찾기
ex) 점수가 80점 이상 90점 미만인 학생 수
- 근사값 찾기
배열에 없는 값의 가장 가까운 위치 찾기
ex) 이상적인 삽입 위치 찾기
⭐ 파라메트릭 서치(Parametric Search)
-
파라메트릭 서치란 최적화 문제를 결정 문제('예' 혹은 '아니오')로 바꾸어 해결하는 기법
- 예시: 특정한 조건을 만족하는 가장 알맞은 값을 빠르게 찾는 최적화 문제
-
일반적으로 코딩 테스트에서 파라메트릭 서치 문제는 이진 탐색을 이용하여 해결할 수 있다.
🔎 <문제> 떡볶이 떡 만들기
📝 문제 해결 아이디어
- 적절한 높이를 찾을 때까지 이진 탐색을 수행하며 높이 H를 반복해서 조정하면 된다.
- '현재 이 높이로 자르면 조건을 만족할 수 있는가?'를 확인한 뒤에 조건의 만족 여부('예' 혹은 '아니오')에 따라서 탐색 범위를 좁혀서 해결할 수 있다.
- 절단기의 높이는 0부터 10억까지의 정수 중 하나이다.
이렇게 큰 탐색 범위를 보면 가장 먼저 이진탐색을 떠올려야 한다.
- 이러한 이진 탐색 과정을 반복하면 답을 도출할 수 있다.
- 중간점의 값은 시간이 지날수록 '최적화된 값'이 되기 때문에, 과정을 반복하면서 얻을 수 있는 떡의 길이 합이 필요한 떡의 길이보다 크거나 같을 때마다 중간점의 값을 기록하면 된다.
📝 답안 예시
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 떡의 개수(N)와 요청한 떡의 길이(M)
int n = sc.nextInt();
int m = sc.nextInt();
// 각 떡의 개별 높이 정보
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
// 이진 탐색을 위한 시작점과 끝점 설정
int start = 0;
int end = (int) 1e9;
// 이진 탐색 수행 (반복적)
int result = 0;
while (start <= end) {
long total = 0;
int mid = (start + end) / 2;
for (int i = 0; i < n; i++) {
// 잘랐을 때의 떡의 양 계산
if (arr[i] > mid) total += arr[i] - mid;
}
if (total < m) { // 떡의 양이 부족한 경우 더 많이 자르기(왼쪽 부분 탐색)
end = mid - 1;
}
else { // 떡의 양이 충분한 경우 덜 자르기(오른쪽 부분 탐색)
result = mid; // 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result에 기록
start = mid + 1;
}
}
System.out.println(result);
}
}🔎 <문제> 정렬된 배열에서 특정 수의 개수 구하기
📝 문제 해결 아이디어
📝 답안 예시
import java.util.*;
public class Main {
public static int lowerBound(int[] arr, int target, int start, int end) {
while (start < end) {
int mid = (start + end) / 2;
if (arr[mid] >= target) end = mid;
else start = mid + 1;
}
return end;
}
public static int upperBound(int[] arr, int target, int start, int end) {
while (start < end) {
int mid = (start + end) / 2;
if (arr[mid] > target) end = mid;
else start = mid + 1;
}
return end;
}
// 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
public static int countByRange(int[] arr, int leftValue, int rightValue) {
// 유의: lowerBound와 upperBound는 end 변수의 값을 배열의 길이로 설정
int rightIndex = upperBound(arr, rightValue, 0, arr.length);
int leftIndex = lowerBound(arr, leftValue, 0, arr.length);
return rightIndex - leftIndex;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 데이터의 개수 N, 찾고자 하는 값 x 입력받기
int n = sc.nextInt();
int x = sc.nextInt();
// 전체 데이터 입력받기
int[] arr = new int[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.nextInt();
}
// 값이 [x, x] 범위에 있는 데이터의 개수 계산
int cnt = countByRange(arr, x, x);
// 값이 x인 원소가 존재하지 않는다면
if (cnt == 0) System.out.println(-1);
// 값이 x인 원소가 존재한다면
else System.out.println(cnt);
}
}⭐ 순차 탐색
리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법
📝 코드 구현
import java.util.*;
public class Main {
// 순차 탐색 소스코드 구현
public static int sequantialSearch(int n, String target, String[] arr) {
// 각 원소를 하나씩 확인하며
for (int i = 0; i < n; i++) {
System.out.println(arr[i]);
// 현재의 원소가 찾고자 하는 원소와 동일한 경우
if (arr[i].equals(target)) {
return i + 1; // 현재의 위치 반환 (인덱스는 0부터 시작하므로 1 더하기)
}
}
return -1; // 원소를 찾지 못한 경우 -1 반환
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.println("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.");
// 원소의 개수
int n = sc.nextInt();
// 찾고자 하는 문자열
String target = sc.next();
System.out.println("앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.");
String[] arr = new String[n];
for (int i = 0; i < n; i++) {
arr[i] = sc.next();
}
// 순차 탐색 수행 결과 출력
System.out.println(sequantialSearch(n, target, arr));
}
}Reference
(이코테 2021 강의 몰아보기) 5. 이진 탐색
[알고리즘] Lower bound, Upper bound
출처: https://12bme.tistory.com/120 [길은 가면, 뒤에 있다.:티스토리]
항상 궁금해하기