개념
- 정렬이 보장되어 있는 배열에서 특정 기준을 가지고 배열을 이분하면서 탐색하는 방법
- 시간복잡도 : O(log N)
활용 방안
항상 전형적인 변수 세팅을 가지고 시작
- L : 탐색할 가치가 있는 왼쪽 끝 index
- R : 탐색할 가치가 있는 오른쪽 끝 index
- result : 탐색한 x의 위치
로직
- L과 R 사이의 가운데 지점의 값을 확인하면서 L과 R을 계속해서 옮겨주고,
최종적으로 x와 일치하는 값, 혹은 x와 가장 가까운 값을 찾아냄 - L > R 이 되어버리면 탐색할 가치가 있는 구간이 더이상 없다는 뜻
효율성
- 구간의 길이는 N → ½ N → ¼ N → ... → 1 의 방식으로 점점 좁아짐
- 총 비교 횟수는 구간의 변화 횟수인 O(log N)
- 예를 들어 N이 10만이라면 약 16번만 비교해도 되는 미친 효율
자주 하는 실수
- 3위 : L과 R의 범위나 result 초기값을 잘못 설정하는 경우
- 2위 : L, R, M, result 등의 변수 정의를 헷갈려서 부등호 등을 잘못 사용하는 경우
- 1위 : 이분 탐색은 잘했는데, 맨 처음에 정렬을 하지 않은 경우!!!
문제 풀이
- 난이도 : 2
- N <= 20,000
- M <= 20,000
- 정답의 최대치 = N * M = 4억 → int 타입으로 해결 가능!
static int N, M;
static int[] A, B;
static void input() {
N = scan.nextInt();
M = scan.nextInt();
A = new int[N + 1];
B = new int[M + 1];
for (int i = 1; i <= N; i++) {
A[i] = scan.nextInt();
}
for (int i = 1; i <= M; i++) {
B[i] = scan.nextInt();
}
}
static int lower_bound(int[] A, int L, int R, int X) {
// A[L...R] 에서 X 미만의 수 중 제일 오른쪽 index를 return
// 그런 게 없다면 L - 1 return
int res = L - 1;
while (L <= R) {
int mid = (L + R) / 2;
if (A[mid] < X) {
res = mid;
L = mid + 1;
} else {
R = mid - 1;
}
}
return res;
}
static void solve() {
Arrays.sort(B, 1, M + 1);
int ans = 0;
for (int i = 1; i <= N; i++) {
// A[i] 를 선택했을 때, B 에서는 A[i] 보다 작은 게 몇 개 있는지 count
ans += lower_bound(B, 1, M, A[i]);
}
System.out.println(ans);
}
public static void main(String[] args) {
int TT = scan.nextInt();
for (int tt = 1; tt <= TT; tt++) {
input();
solve();
}
}
Parametric Search
개념 : 배열에 0과 1만 존재하며 오름차순이 보장되지만 배열의 내용은 모름
예시 : Up-Down 게임
- A는 1 ~ 1000 사이의 자연수를 선택
- B는 A에게 숫자가 X 이상인지를 물어볼 수 있음
- A는 맞으면 1, 아니면 0이라고 대답해야 함
- 이런 상황에서 최소 횟수로 질문하려면 어떻게 해야 할까?
- 최악의 경우에는 1000번을 질문해야 함
- 대신에 이진 탐색을 하면서 가능한 곳들을 전부 1로 만들고, 나머지는 전부 0으로 만들면 효율적으로 풀 수 있음
그러므로 우리는 문제를 풀 때・・・ (⭐️ 핵심!)
- 정답을 Parameter로 바꾸고, 문제를 Yes or No 게임으로 바꿔버리면 됨
- 모든 값에 대해 Yes or No를 체크하는 문제를 풀어라!
주의할 점
- 문제를 거꾸로 풀어야 하는 유형이기 때문에 Parametric Search 유형인지 알 수 있는 통찰력 필요
- 최근 코딩 테스트에 상당히 자주 출몰하고 있음!
자주하는 실수
- 3위 : L, R, result 초기값을 잘못 설정한 경우
- 2위 : L, R, M, result 변수 정의를 헷갈려서 부등호 등을 잘못 사용하는 경우
- 1위 : 매개 변수에 대한 결정이 N N N N Y Y Y Y 형태가 아님에도 무턱대고 이분 탐색을 하려는 경우!
문제 유형을 판별할 수 있는 키워드
- ~의 최대값을 구하시오
- ~의 최소값을 구하시오
Parametric Search 문제 풀이
- 난이도 : 2
- 1 <= N <= 100만
- 1 <= M <= 20억
- 0 <= 각 나무 높이 <= 10억
int 가능?
- 정답의 범위 : 0 ~ 10억
- 잘린 나무 길이의 합 <= 나무 높이의 총합 = 100만 * 10억 = 10¹⁵
- 정답 자체는 int 타입에 저장되지만 연산하는 과정에 int 범위를 초과하므로 long 타입을 사용해야 함
원래 문제
- 원하는 길이 M만큼 얻을 수 있는 최대 높이 H는 얼마인가?
- Parametric Search로 풀려면 문제의 조건과 타겟을 뒤집어야 함
뒤집은 문제
- 어떤 높이 H로 잘랐을 때, 원하는 길이 M만큼 얻을 수 있는가? Yes or No
- 즉, 여기서 매개 변수는 H가 됨
시간복잡도
- O(뒤집은 문제 * log 20억) = O(N log X) = O(31N) = O(N)
- N이 100만이니 31N은 3100만
- O(N log X)인 이유
- H를 정해서 결정 문제 풀기 = O(N)
- 정답 범위를 이분 탐색하면서 풀기 = O(log X)
- 위 둘을 합하면 O(N log X)
static boolean determination(int H) {
// H 높이로 나무들을 잘랐을 때, M 만큼을 얻을 수 있으면 true, 없으면 false return
long sum = 0;
for (int i = 1; i <= N; i++) {
if (A[i] > H) {
sum += A[i] - H;
}
}
return sum >= M;
}
static void solve() {
long L = 0, R = 2000000000, ans = 0;
while (L <= R) {
int mid = (int) ((L + R) / 2);
if (determination(mid)) {
ans = mid;
L = mid + 1;
} else {
R = mid - 1;
}
}
System.out.println(ans);
}
public static void main(String[] args) {
input();
solve();
}
- 난이도 : 3
- 2 <= N <= 200,000
- 2 <= C <= N
- 1 <= 좌표 <= 10억
- C개의 공유기를 몇몇 집에 설치하되, 인접한 공유기 사이의 거리를 최대화할 것
int 가능?
- 제일 멀리 설치해도 10억 이하 → int 가능
원래 문제
- C개의 공유기를 설치했을 때의 최대 인접거리 D는 얼마인가?
뒤집은 문제
- 어떤 거리 D만큼 거리를 둘 때, 공유기 C개를 설치할 수 있는가? Yes or No
❖ 참고 사항 : 문제를 뒤집을 때, 뒤집은 문제가 더 쉬운지 여부도 판별해야 함
시간복잡도
- O(뒤집은 문제 * log 10억) = O(N log X) ≅ O(30N) = O(N)
static boolean determination(int D) {
// D 만큼 거리 차이를 두면서 C 개의 공유기를 설치할 수 있는지 여부
int cnt = 1, last = A[1];
for (int i = 2; i <= N; i++) {
if (A[i] - last < D) continue;
last = A[i];
cnt++;
}
return cnt >= C;
}
static void solve() {
Arrays.sort(A, 1, N + 1);
int L = 1, R = 1000000000, ans = 0;
while (L <= R) {
int mid = (L + R) / 2;
if (determination(mid)) {
ans = mid;
L = mid + 1;
} else {
R = mid - 1;
}
}
System.out.println(ans);
}
public static void main(String[] args) {
input();
solve();
}
'Algorithm > 유형별 풀이 template' 카테고리의 다른 글
Two Pointers (0) | 2022.07.14 |
---|---|
Sort Application (0) | 2022.07.11 |
Brute Force (0) | 2022.07.10 |