[알고리즘] 이분탐색 - 백준 1920, 2295, 1654

[실전 알고리즘] 0x13강 - 이분탐색

바킹독님의 블로그를 바탕으로 정리한 글입니다.

---

이분탐색은 업다운 게임을 생각하면 이해가 편하다. 1에서 50 사이의 숫자를 찾으려면 25를 부르는게 가장 합리적인 것이다. 가장 기본적인 형태의 이분탐색은 이 업다운 게임의 기조를 띄고 있다. 특정 범위를 줄여가면서 특정 조건을 만족하는 데이터를 찾는 것이다. 구현적으로는 이미 STL에 잘 구현되어있기에 어려운 부분이 전혀 없다.

 

하지만 이분탐색은 응용이 들어가게 되면 굉장히 어렵고 특히 코딩테스트에서 가장 어려운 문제로 꼽히기도 한다. 일단 STL의 사용법, 언제 이분 탐색을 적용해야할지에 집중하면서 공부해보자.

---

백준 1920번으로 보는 이분 탐색

이분탐색은 범위를 절반으로 줄여나가면서 값을 찾는 알고리즘이다. 일반적인 선형 탐색은 O(N) 시간이 든다. 이분탐색은 범위를 절반씩 줄이므로 O(log N)이면 해결이 가능하다. 

일반적인 구현은 정렬이 된 배열에 대해 적용이 가능하다. 일단 문제로 바로 보자.

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

 

배열 4 1 5 2 3에 5가 있는지 찾으면 된다. N개의 숫자로 이루어진 배열에 대해 M개의 숫자를 찾으려면 O(MN) 만큼의 시간이 든다.

하지만 정렬을 하게되면 정렬하는데 O(N log N), 이분 탐색을 적용하는데 O(M log N) 시간이 들게 된다.

가장 정석적인 풀이는 먼저 정렬을 하고, 중앙점 mid를 찾는다. 찾고자하는 수 target이 mid보다 크다면 mid + 1  ~ 끝까지 다시 탐색하고 target이 mid보다 작다면 처음 ~ mid - 1 까지 탐색하면 된다.

vector <ll> A(N);
    for (ll i = 0; i < N; i++) cin >> A[i];
    sort(A.begin(), A.end());

    cin >> M;
    vector <ll> X(M);
    for (ll i = 0; i < M; i++) cin >> X[i];

    vector <ll> res(M, 0);
    //X의 원소들이 A에 있는지 체크한다.

    for (int x = 0; x < M; x++) {
        int flag = 0;
        int first = 0, last = N-1;
         while(first <= last){
            int mid = (first + last + 1) / 2;
            if (A[mid] == X[x]) {
                res[x] = 1;
                flag = 1;
                break;
            }
            else if (A[mid] > X[x]) {
                last = mid - 1;
            }
            else {
                first = mid + 1;
            }
         }
         if (!flag) res[x] = 0;
  }

찾지 못하는 경우도 생각해서 flag를 두었다.

 

STL을 활용하면 코드는 한 줄로 끝난다.

cout << binary_serach(A.begin(), A.end(), t);

binary_search 함수는 O(log N)에 범위 내에 원소가 들어있는지 여부를 반환한다. 단 범위는 반드시 오름차순으로 정렬되어 있어야 한다.

---

백준 10816번으로 보는 이분 탐색

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

다음은 조금 다른 문제이다. M개의 숫자가 각각 몇 번 등장했는지를 구해야 한다. 하나의 숫자가 어디에 등장하는지는 이분 탐색으로 구할 수 있고, 그 정보로 몇 번 등장했는지는 선형 탐색으로 좌우로 이동하면서 구할 수 있긴하다.

 

그런데 최악의 경우 모든 숫자가 같은 숫자라면 O(N) 시간이 걸린다. 비효율적인 것이다.

 

사실 어떤 숫자가 몇 번 등장했는지 구하려면 그 숫자가 처음 등장한 위치와 마지막으로 등장하는 위치만 구하면 O(1)로 구할 수 있다. 이분 탐색을 활용해서 그 위치를 구할 수 있지 않을까?

 

처음 등장하는 위치부터 생각해보자. 일단 똑같이 mid를 구한다.

1. mid가 target보다 작다면 target의 시작 위치는 mid보다 왼쪽에 있는 것이므로 end를 mid로 바꾸면 된다.
2. mid가 target과 같아도 target의 시작 위치는 mid보다 왼쪽에 있거나 mid에 있으므로 end를 mid로 바꾸면 된다.
3. mid가 target보다 크다면 target의 시작 위치는 mid보다 왼쪽에 있으므로 start를 mid+1로 바꾸면된다. 

마지막으로 등장하는 위치의 논리도 동일하다. 다만, upper은 target이 마지막으로 나온 위치 + 1을 찾아야 한다. 구현상 그게 더 편하기 때문이다. 따라서 mid가 target과 같거나 target이 더 큰 경우 start를 mid + 1로 설정하면 된다. 코드는 다음과 같다.

int lower_idx(int target, int len){
  int st = 0;
  int en = len;
  while(st < en){
    int mid = (st+en)/2;
    if(a[mid] >= target) en = mid;
    else st = mid+1;
  }
  return st;
}

int upper_idx(int target, int len){
  int st = 0;
  int en = len;
  while(st < en){
    int mid = (st+en)/2;
    if(a[mid] > target) en = mid;
    else st = mid+1;
  }
  return st;
}

 

사실 이 lower_idx, upper_idx와 동일한 역할을 하는 STL을 존재한다. lower_bound와 upper_bound가 반환하는 값은 lower_idx, upper_idx 함수와 완전히 동일하게 target이 시작하는 위치와 끝나는 위치 + 1이다. 그래서 STL을 써서 훨씬 쉽게 풀 수 있고, 사용법은 binary_search와 똑같이 첫 번째와 두 번째 인자로 범위를 주면 된다. 

 

lower_bound, upper_bound의 반환 자료형은 a가 배열이라면 포인터, vector라면 iterator이고, equal_range라는 함수는  lower_bound, upper_bound의 결과를 pair로 반환한다.

---

백준 2295: 세 수의 합

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

자연수 집합 U에 대해 세 원소를 더한 값 d가 U에 존재하도록 하는 최대 d를 구하면 된다.

일단 O(n^3)이면 모든 조합의 세 수의 합을 구할 수 있다. 이를 O(n)으로 U에 존재하는지 체크할 수 있고 선형 체크가 가능하다면 정렬 후 이분 탐색도 가능하므로 O(n^3 * log n)으로 답을 구할 수 있다.

 

n=1,000이니 O(n^3 * log n)은 시간초과가 날 것이 분명하고 다른 풀이를 생각해봐야 한다.

a + b + c = d 라는 식을 생각해보자. 이 식에서 한 가지 확실한 점은 d와 c는 무조건 다르다는 것이다. 따라서 식을 a + b = d- c = e와 같은 방식으로 정의할 수 있고, 이 식은 O(n^2 * log n)이면 풀 수 있다.

 

바로 구현해보자.

/** 이분탐색 2295 세 수의 합 **/
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int n;
int U[1050];
vector<int> sum2;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> U[i];
    }
    sort(U, U + n);

    // a + b를 저장한 배열 sum2 계산 및 정렬렬
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            sum2.push_back(U[i] + U[j]);
    sort(sum2.begin(), sum2.end());

    for (int i = n - 1; i > 0; i--)
    {
        for (int j = 0; j < i; j++)
        {
            if (binary_search(sum2.begin(), sum2.end(), U[i] - U[j]))
            {
                cout << U[i];
                return 0;
            }
        }
    }
}

마지막 이중 for문에서 주의해야할 점은 d-c가 최대가 아니라 d만 최대가 되면 된다는 뜻이다. c는 어떤 값이던 중요하지 않다. 이런식으로 이분탐색을 활용해서 2개의 값을 묶고, 이분 탐색을 적용 가능하게 변경하는 방식은 굉장히 자주 나오고 떠올리기 힘드니 잘 알아두자.

---

Parametric Search

parametric search는 최적화 문제를 결정 문제로 변환하여 이분 탐색을 사용하는 알고리즘이다. 상당히 난이도가 있는 문제들이며 parametric search를 떠올리는 과정도 힘들다. 

바로 문제로 보자.

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

 

길이가 제각각인 K개의 랜선을 잘라서 모두 N개의 같은 길이의 랜선을 만들기 위한 랜선의 최대 길이를 구하면 된다.

예시로 보자. 

4 11
802
743
457
539

K=4, N=11이고, 200으로 자르게되면 802 -> 200 * 4가 되는 방식이다. 

 

이 문제는 N개를 만들 수 있는 랜선의 최대 길이를 구하는 최적화 문제이다. 이를 결정 문제로 만든다는 뜻은 문제에서 요구하는 답이 인자로 들어가고, 조건의 참/거짓 여부를 판단하는 문제로 만드는 것이다.

 

즉, 기존 최적화 문제인 N개를 만들 수 있는 랜선의 최대 길이를 결정 문제인 랜선의 길이가 X일 때 랜선이 N개 이상인가? 를 판단하면 된다.

 

결정 문제로 보면,  X가 parameter이고 이 X 중 최대를 찾는 문제로 변경되었기 때문에 parametric search이다. X가 커지면 랜선의 개수는 줄어들게되므로 이분 탐색을 사용해서 최대 X 값을 찾을 수 있다. X가 1이면 랜선은 매우 많고 X가 100000...이면 랜선이 매우 적은 것이다.

 

X 값에 이분 탐색을 적용한다는 뜻은, st, mid, en을 놓고 범위를 줄여가며 랜선의 길이가 N 이상인지를 판단하는 것이다. 바킹독님 블로그의 글 하단쪽 그래프를 보면 큰 도움이 될것이다. 

 

바로 구현해보자. 

따로 함수를 두어 X에 대해 만들어지는 랜선이 N 이상인지를 구하는 기능을 구현해두면 좀 더 편할 것이다. 또, start = 1, end = 가장 긴 랜선의 길이로 두고 X=mid 일 때 랜선이 N개 이상이면 오른쪽 범위에 답이 존재하므로 start = mid, 아니라면 더 작은 X로 잘라야하므로 end = mid - 1로 두면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
using namespace std;
typedef long long ll;

ll getans(vector <ll> LAN, ll length) {
	ll count = 0;
	for (int i = 0; i < LAN.size(); i++) count += (LAN[i]/length);
	return count;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	//길이가 다른 K개의 랜선을 N개의 길이가 같은 랜선으로 만들어야 한다. 이미 자른 랜선은 붙일 수 없다.
	//N개보다 많이 만들어도 된다.
	//N개 이상을 만들 수 있는 최대 길이를 찾자.

	ll K, N;
	cin >> K>> N;
	vector <ll> LAN(K);
	for (ll i = 0; i < K; i++) cin >> LAN[i];
	sort(LAN.begin(), LAN.end());

	ll left = 1;
	ll right = LAN.back();

	while (left != right) {
		//랜선 길이의 범위가 한 칸이 되면 그 때 left가 x이다.
		//적당한 랜선 길이를 랜선 길이 범위의 중간으로 정해서 체크한다.
		long long mid = (left + right + 1) / 2;
		ll res = getans(LAN, mid);
		//mid 길이로 랜선을 N개 이상 만들었다면 mid 길이도 답이 될 수 있고 이보다 길게도 될 수 있으므로
		//랜선 길이 범위를 mid와 같거나 크게 설정한다.
		if (res >= N) {
			left = mid;
		}
		// N개 이상 만들지 못했다면 랜선 길이를 더 줄여야 하므로 랜선 길이 범위를 mid보다 작게 변경한다.
		else {
			right = mid - 1;
		}
	}
	cout << left;

}