[문제해결기법] 7. 이분 탐색

1. 탐색

 

오름차순으로 정렬된 N개의 정수 배열 A[0], ..., A[N-1]이 있다. X가 주어졌을 때, A[i] = X라면 i를 리턴하는 함수 find(N, X)를 작성하시오. 이 함수는 내부적으로 compare(i, val)을 호출하는데, 이는 A[i]=val이면 0, A[i] < val이면 1, A[i] > val이면 -1을 리턴하는 함수이다. N은 최대 100이다.

 

int find(int sub, int N, int X) {
	int start = 0, end = N-1, t; 
	while (start <= end){
		int mid = (start+end)/2;
		int v = compare(mid, X); 
		if (v > 0) start = mid + 1;  // 기준값보다 작으면 start를 당기기
		else if (v) end = mid - 1; // 기준값보다 크면 end를 당기기
		else return mid;
	}
	return -1;
}

 

 

예를 들어, A[] = {3, 4, 7, 9, 23, 110}이고 X = 4일 때,

start = 0, end = 5. 첫 mid 값은 5/2 = 2.

compare(2, 4) : A[2] = 7 > 4이고, 리턴값은 -1. end = mid - 1 = 1

start = 0, end = 1. mid 값은 1/2 = 0.

compare(0, 4) : A[0] = 3 < 4이므로, 리턴값은 1. start = mid + 1 = 1

start = 1, end = 1. mid 값은 2/2 = 1.

compare(1, 4) : A[1] = 4 == 4이므로, 리턴값은 0. 따라서 return mid (= 1).

 

 

2. 경비실

 

수직선 위에 n채의 집이 있고, 각 집 i의 좌표는 정수 xi로 표현할 수 있다. 여기에 k개의 경비실을 놓으려고 하는데, 경비실은 정수 좌표 위에 놓을 수 있다. 같은 좌표 위에 집과 경비실이 동시에 올 수 있다. 경비실을 놓을 때 중요한 것은 경비실에서 가장 먼 집의 거리를 최소화하는 것이다. n채의 집에 k개의 경비실을 효율적으로 배치했을 때, 경비실에서 집까지 가장 먼 거리를 구하는 프로그램을 작성하시오.

 

집 개수 n & 경비실 개수 k를 입력받고, 집의 좌표를 입력받은 후

집에서 가장 가까운 경비실까지의 최대 거리의 최솟값을 구하는 문제이다.

 

brute force

첫번째 집에서 마지막 집까지의 거리 = M

(M,k)개 조합을 모두 해본다 -> O(M^k)

 

착안점

경비실이 k개라면, 집에서 경비실까지의 최대 거리는 M/2k 보다 클 수 없다. 즉, 같은 간격으로 놓기만 하면 됨

경비실이 하나 더 늘어나면 최대 거리는 확실히 줄어든다.

모든 집에서 경비실까지의 거리가 d가 되게 경비실을 놓을 수 있다면,

d+e가 되게도 놓을 수 있다. (e는 양수)

 

풀이

집들을 x좌표 기준으로 정렬한다. 맨 왼쪽(처음)집부터 오른쪽으로 읽어나가면서,

k개의 경비실을 놓아서 가장 먼 집까지의 거리가 d가 되는지를 점검한다.

맨 왼쪽 집을 생각해보면 경비실은 이 집 좌표에서 d만큼 오른쪽에 떨어진 곳에 있을 것이다.

이 경비실로부터 거리가 d 이내인 집을 모두 제거한 다음,

남은 집에 대해서 똑같은 과정을 반복하면 필요한 경비실의 수가 나온다.

 

만약 경비실 수가 k개 이하라면, d값(거리)을 줄여서 답인지 점검한다.

만약 경비실 수가 k개 초과라면, d값(거리)을 늘려서 답인지 점검한다. (이진탐색)

 

이 문제는 답을 구하기는 어렵지만, 답의 후보를 주었을 때 이 답이 참인지 거짓인지 O(n)시간에 판정 가능하다.

일단 답이 d라면 d 이상은 무조건 답임.

따라서 조건을 만족하는 최소의 d를 찾아야 한다.

 

 

3. Heron's method

 

sqrt(2)의 값은?

1은 아님. (1^2 = 1. 2보다 작다)

2/1 = 2도 아님. (2^2 = 4. 2보다 크다)

(1+2/1) / 2 = 3/2도 아님. 하지만 답에 조금 더 근접함

그렇다면, (3/2 + 2/(3/2)) / 2 = 17/12 는 답에 더 근접함

 

x < sqrt(2) 라면, 2/x > sqrt(2) 이므로

(x + 2/x) / 2는 보다 더 sqrt(2)에 근접해 있다.

 

 

 

4. 크루스컬의 공 (BOJ 1396)

https://www.acmicpc.net/problem/1396

난이도 플레1..ㅋㅋ

예제 입력을 보면,

가중그래프 G=(V, E, W)가 주어지고, 여기에 Q개의 질의 (u,v)가 주어진다.

이 질의에 대한 답은 정수 c인데,

이는 w(e) <= c인 edge만 이용하여 u와 v를 이을 수 있는 최솟값이다.

 

참고 : 크루스컬 알고리즘(Kruskal Algorithm)
가중치가 있는 무방향 그래프를 최소 신장 트리로 만드는 알고리즘.
(최소 신장 트리 = 가중치가 최소이고 사이클이 없는 무방향 그래프)
사이클이 없으므로 간선의 수 = (정점 수 - 1)
크루스컬 알고리즘은 Greedy에 속하며, 매번 순환이 되지 않도록 가중치가 가장 적은 다음 간선을 선택.
시간복잡도 O(E log N)

 

풀이 1. 크루스컬 알고리즘 * Q

각 질의마다 크루스칼 알고리즘을 돌리면서, u와 v가 연결되는 순간 이 때 edge의 가중치 값이 답 c이다.

크루스칼 알고리즘에 O(|E| log |N|).

edge의 가중치 정렬에 O(|E| log |N|).

edge를 읽으며 처리하는데에 O(|E|)

질의를 총 Q번 돌리므로 총 O( Q|E| log |N| )

 

동일한 그래프에 대해 크루스컬 알고리즘을 Q번 실행시키는 것 보다 더 좋은 방법이 있을까?

 

풀이 2. 이분탐색

lo = 0, hi = 가중치 최댓값, c는 구간 (lo, hi]에 존재.

mid = (lo + hi) / 2.

w(e) <= mid 인 edge만으로 u, v를 연결할 수 있는지?

-> 크루스컬 알고리즘을 가중치가 최대mid인 edge들만 사용하면 알 수 있다.

 

만약 u와 v를 연결할 수 있다면, c는 (lo, mid] 안에 있다.

그렇지 않다면, c는 (mid, hi] 안에 있다.

 

풀이2 검토 -> 노드가 |V|개일 때,

크루스칼 알고리즘에 O(|E| log |N|).

크루스컬 알고리즘을 log |E| 번 돌리면 = O(|E| log |V|). 이 때 edge 가중치가 변하지 않으므로 재정렬할 필요 X.

질의가 Q개이므로 총 O( Q|E| log |N| ).

어라 똑같잖아?

 

이진탐색 보완

Q개의 질의를 하나씩 처리하지 말고, 질의의 같은 단계를 동시에 진행하면?

예를 들어 Q = 4일 때,

처음에는 Q1~Q4까지 모두 lo, hi가 같다. mid도 같고,

크루스칼 알고리즘을 한 번 돌려서 가중치가 mid인 에지까지 읽으면 종료. (1번으로 4개의 질의 처리)

 

두번째에는 Q1,Q2는 답이 mid보다 커야하고, Q3,Q4는 답이 mid보다 작아야한다고 하자.

크루스칼 알고리즘을 한번 더 돌리는데

이 때 읽고있는 에지의 가중치가 (lo+mid)/2인 시점, (mid+hi)/2인 시점에서 각각 Q1, Q2 그리고 Q3,Q4를 검토.

 

세번째에서도 mid값이 같은 질의끼리 모은 뒤,

한번의 크루스칼 알고리즘으로 mid 값을 처리.

 

시간복잡도

이분 탐색을 모두 log |E| 번 진행하는건 마찬가지이지만,

매 단계마다 크루스컬 알고리즘은 1번만 진행하며,

한번 수행하면서 질의의 중간값을 지나갈 때 마다 범위를 갱신하기 때문에

크루스컬 알고리즘의 총 수행시간은 O( Q+|E| ). = 에지를 다 읽고 Q개의 질의 범위 업데이트

전체 시간복잡도는 O( (Q+|E|) log |E| ).

 

 

5. 민혁이의 게임 파티 (BOJ 16976)

https://www.acmicpc.net/problem/16976

플레2..

N개의 노드가 주어지고 각 노드에는 1~M까지의 수가 쓰여있다.

1번부터 Q번까지 번호가 매겨진 에지들이 주어진다.

노드에 쓰인 숫자 각각마다 1번 에지부터 i번 에지까지를 이용해서 같은 숫자인 노드들을 모두 연결할 수 있는

최소의 i 값을 구하는 문제.

풀이 : 이진탐색

 

수 i가 쓰인 노드가 A,B,C라고 하면

이 질문은 A,B,C가 모두 연결되는 최초의 시점을 묻는 것이다.

노드 A와 노드 B가 연결되어있고, A와 C가 연결되어있다면, B와 C도 연결되어있는 상태이다.

따라서 질문을 다음과 같이 바꾼다.

 

1번부터 mid번까지의 에지로 A와 B를 연결할 수 있는가?

1번부터 mid번까지의 에지로 A와 C를 연결할 수 있는가?

 

i가 같은 노드에 대해 질문을 이렇게 한 뒤, 질의의 답 중 최댓값이 A,B,C 모두가 연결되는 시점이 된다.

모든 질문의 개수는 노드의 개수보다 많지 않다.