C언어 이진탐색

01. 개요

 

 만약 당신이 전교생의 데이터 중에 랜덤한 몇 명을 찾아야 한다면 일반적으로 1학년 1반부터 시작하여 그 학생이 나올 때까지 찾고, 다시 처음으로 돌아가 두 번째 학생을 같은 방법으로 찾는 식으로 수행할 것이다. 프로그래밍에서는 이것을 순차 탐색(Linear Search)이라고 명한다. 여기 이 문제를 순차 탐색에 맞게 조금 변형시켰다.

 

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

 

수 찾기

 

문제

N개의 정수 A[1], A[2], …, A[N]이 주어져 있을 때, 이 안에 X라는 정수가 존재하는지 알아내는 프로그램을 작성하시오.

 

입력

첫째 줄에 자연수 N(1≤N≤50)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤10^8)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안에 존재하는지 알아내면 된다. 모든 정수들의 범위는 int 로 한다.

 

출력

M개의 줄에 답을 출력한다. 존재하면 1을, 존재하지 않으면 0을 출력한다.

 

제한

시간제한 2초, 메모리제한 128MB

 

 

코드 1.1

수 찾기

#include <stdio.h>
 
const int MAX_M = 50;
 
int main() {
    int n, m, k[MAX_M], l[MAX_M], f[MAX_M] = { 0 };
 
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &k[i]);
    }
 
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        scanf("%d", &l[i]);
    }
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (k[i] == l[j]) f[j] = 1;
        }
    }
    
    for (int i = 0; i < m; i++) {
        printf("%d\n", f[i]);
    }
 
    return 0;
}

 

 이 문제에서는 N(1≤N≤50) 제한이 있어서 실행에 몇 초 걸리지 않지만 원래 문제대로 N(1≤N≤100,000)라면 주어진 시간인 2초를 초과해서 오답이 되어버린다. 이럴 때는 조건 N(1≤N≤100,000)라도 시간제한 안에 풀 수 있는 알고리즘을 사용해야 한다. 바로 이진 탐색(Binary Search)이다. 이진 탐색은 주로 제한 시간 내에 범위가 매우 넓은 데이터를 탐색하며 특정한 값을 찾거나 그 값의 개수를 세는 것부터 최소값, 최고값을 구하는 것까지 다양하게 사용할 수 있다.

 

 

 

02.본문 

 알고리즘의 수행 시간을 좌지우지 하는 것은 대게 반복문이다. 아까 수 찾기 문제 변형과 같이 입력의 크기가 작다면 반복문을 사용하는 것이 빠르고 편리하겠지만 입력의 크기가 커지면 커질수록 반복문 한 개당 수행 시간이 어마어마하게 증가하게 된다. 따라서 알고리즘의 수행 시간은 보통 반복문이 수행되는 횟수로 측정한다. 여기서는 2중 루프가 n번 돌기 때문에 실행시간은 n의 4승에 비례하고, 이것을 O( n4 )라고 쓴다. 이진 탐색은 먼저 탐색할 배열 k를 오름차순으로 정렬하는 것으로 시작된다. 그리고나서 k의 정중앙 값을 보면 두 가지의 상황이 등장한다.

-정중앙 값 x가 탐색하고 싶은 값보다 크다면 x는 절반보다 작다

-정중앙 값 x가 탐색하고 싶은 값보다 크다면 x는 절반보다 크다

 

 탐색하고 싶은 값이 속하지 않은 반대편은 버리고 남은 절반에서 다시 반으로 쪼개는 행동을 반복하면 된다. 단순히 쪼개기만 했는데 계산해야할 값은 1/2, 1/4, 1/8..로 줄어드는 것을 볼 수 있다. 마치 벌칙게임에서 자주 등장하던 배스킨라빈스 31 게임이 떠오르는 알고리즘이다.

 

이제 원래 수 찾기 문제를 풀어보자. 제한은 N(1≤N≤100,000)이다.

코드 1.2

수 찾기

#include <stdio.h>
#include <algorithm>
using namespace std;
 
const int max_m = 100000;
int n, m, k[max_m];
 
int bin_search(int x) {
    int l = 0, r = n-1, p;
 
    //범위가 사라질 때까지 반복
    while (l <= r) {
        p = (l + r) / 2;
        if (k[p] == x) return 1; //발견
        else if (k[p] < x) l = p + 1;
        else r = p - 1;
    }
    return 0; //발견하지 못함
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &k[i]);
    }
    sort(k, k + n);
 
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        int a;
        scanf("%d", &a);
        printf("%d\n", bin_search(a));
    }
    return 0;
}

 

코드는 늘어났지만 제한 시간 내에 풀 수 있게 되었다. 이진 탐색의 원리를 그림으로 나타내자면 이렇다.

 

 101까지 있는 배열에서 40을 찾는다고 가정했을 때, 우선 1부터 101까지의 수에서 중앙값을 찾아 탐색한다. 40<51 이므로 51보다 클 수는 없기 때문에 51부터 101까지의 수중에서는 찾고자하는 값이 없음을 확신할 수 있다.

 

 확실히 없는 부분을 버리고 남은 범위인 1부터 50까지의 수중에서 다시 중앙값을 찾는다. 최대 수가 짝수인 경우 중앙값이 두 개가 나오는데 어느 쪽을 선택해도 상관없다. 여기서는 26을 중앙값이라고 치고 탐색한다. 이 때 26<40 이므로 1부터 26까지의 부분을 버린다.

 

이런 식으로 찾아나가다 보면 언젠가는 범위가 없어지고 값 하나가 남는다. 그 값이 바로 정답인 것이다. 이 그림을 코드로 구현하는 건 간단하다.

코드 1.3

 

int bin_search(int x) {
    int l = 0, r = n-1, p;
 
    //범위가 사라질 때까지 반복
    while (l <= r) {
        p = (l + r) / 2;
        if (k[p] == x) return 1; //발견
        else if (k[p] < x) l = p + 1;
        else r = p - 1;
    }
    return 0; //발견하지 못함
}

 

이진탐색에서는 탐색할 후보가 반씩 줄어들기 때문에 처음의 탐색 범위가 n이라고 하면 약 log2n번 반복하면 된다.

 

이번에는 비슷한 문제로 응용을 해보겠다.

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

 

 

숫자 카드

 

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 숫자 M개가 주어졌을 때, 이 숫자가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N (1 ≤ N ≤ 500,000)이가 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 숫자가 주어진다. 숫자 카드에 적혀있는 숫자는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 숫자가 적혀있는 경우는 없다.

 

출력

넷째 줄에 입력으로 주어진 M개의 숫자에 대해서, 각 숫자가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

 

제한

시간제한 2초, 메모리제한 256MB

 

수 찾기와 같은 유형의 문제이다. 입력받은 값을 함수로 보내서 이진탐색으로 숫자가 있는지 찾고 결과 값을 출력한다.

 

코드 1.5

숫자 카드

 

 

#include <stdio.h>
#include <algorithm>
using namespace std;
 
const int max_m = 500001;
 
int n, m, k[max_m];
 
int bin_search(int x) {
    int l = 0, r = n - 1, p;
 
    //범위가 사라질 때까지 반복
    while (l <= r) {
        p = (l + r) / 2;
        if (k[p] == x) return 1; //발견
        else if (k[p] < x) l = p + 1;
        else r = p - 1;
    }
    return 0; //발견하지 못함
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &k[i]);
    }
    sort(k, k + n);
 
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        int a;
        scanf("%d", &a);
        printf("%d ", bin_search(a));
    }
 
    return 0;
}

 

이번엔 좀 더 발전된 숫자 카드 문제다.

 

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

숫자 카드2

 

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 숫자 M개가 주어졌을 때, 이 숫자가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N (1 ≤ N ≤ 500,000)이가 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 숫자가 주어진다. 숫자 카드에 적혀있는 숫자는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

 

셋째 줄에는 M (1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 숫자가 주어지며, 이 숫자는 공백으로 구분되어져 있다. 이숫자도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

 

출력

첫째 줄에 입력으로 주어진 M개의 숫자에 대해서, 각 숫자가 적현 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

 

제한

시간제한 1초, 메모리제한 256MB

 

 

 숫자 카드에서는 첫 번째 배열에서 두 번째 배열의 원소가 몇 개 있든지 상관없이 한 개라도 찾으면 1을 리턴하면 되었지만, 이 문제에서는 몇 개 있는지 세어야 하므로 하나를 찾게 되면 그걸로 끝이 아니라 다시 양쪽으로 탐색을 보내서 전체 개수를 출력해야한다. 재귀 함수를 이용해 함수에서 탐색을 마치고 오는 방법과 함수에서 탐색한 값을 가지고 메인 함수 안에서 세는 방법이 떠올랐지만 코드가 복잡해질 것 같아서 재귀 함수를 선택했다.

코드 1.6

숫자 카드2

#include <stdio.h>
#include <algorithm>
using namespace std;
 
const int max_m = 500001;
 
int n, m, k[max_m], kk[max_m];
 
int bin_search(int l, int r, int n) {
    int res, p = (l + r) / 2;
    
    if (l > r) {
        return 0;
    }
    else {
        if (k[p] == n) {
            res = bin_search(l, p - 1, n);
            res += bin_search(p + 1, r, n);
            res += 1;
        }
        else if (k[p] < n) res = bin_search(p + 1, r, n);
        else res = bin_search(l, p - 1, n);
    }
 
    return res;
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &k[i]);
    }
    sort(k, k + n);
 
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        scanf("%d", &kk[i]);
    }
 
    for (int i = 0; i < m; i++) {
        int l = 0, r = n - 1;
        printf("%d ", bin_search(l, r, kk[i]));
    }
 
    return 0;
}

조금 다른 문제를 풀어보겠다.

 

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

 

랜선 자르기

 

문제

집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.

 

이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm 은 버려야 한다.(이미 자른 랜선은 붙일 수 없다.)

 

편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. 이 때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다.

 

셋째 줄에는 M (1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 숫자가 주어지며, 이 숫자는 공백으로 구분되어져 있다. 이숫자도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

 

출력

첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.

 

제한

시간제한 2초, 메모리제한 128MB 

 

 이 문제도 두 개의 해답이 있다. 첫 번째로는 임의의 랜선 길이를 정하고 만들 수 있는 랜선 개수를 구한 다음 이진 탐색으로 원하는 랜선 개수보다 같거나 많을 경우 최댓값을 답으로 구하는 방법이 있고, 두 번째는 처음 최댓값을 아주아주 큰 수로 잡아두고 거기서부터 이진 탐색을 시작하는 방법이 있다. 무엇이 더 빠른 방법인지 알기 위해서 두 개의 방법으로 풀어보도록 하겠다.

 

코드 1.7

랜선 자르기 첫 번째

 

 

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int len[10000], k, n;
 
long long bin_search(int a, int k) {
    long long res = 0;
    for (int i = 0; i < k; i++) {
        res += len[i] / a;
    }
    return res;
}
 
int main() {
    scanf("%d %d", &k, &n);
    
    int rmax = 0;
    for (int i = 0; i < k; i++) {
        scanf("%d", &len[i]);
        if (rmax < len[i]) {
            rmax = len[i];
        }
    }
 
    int l = 0, r = rmax, res = 0;
 
    while (l <= r) {
        int p = (l + r) / 2;
        long long a = bin_search(p, k);
 
        if (a < n) {
            r = p - 1;
        }
        else {
            if (res < p) {
                res = p;
            }
            l = p + 1;
        }
    }
    printf("%d\n", res);
 
    return 0;
}

코드 1.8

랜선 자르기 두 번째

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int k, n, len[100000];
 
int main() {
    scanf("%d %d", &k, &n);
 
    for (int i = 0; i < k; i++) {
        scanf("%d", &len[i]);
    }
 
    long long l = 0, r = 0x7fffffff, p;
    int num = 0;
 
    while (l <= r) {
        p = (l + r) / 2;
        long long res = 0;
 
        for (int i = 0; i<k; i++) {
            res += len[i] / p;
        }
        if (res >= n) {
            num = p;
            l = p + 1;
        }
        else r = p - 1;
    }
    printf("%d\n", num);
    return 0;
}
 

03. 느낀점

 학교 정올반 방학 숙제를 고민하다가 그마나 조금 알거같았던 이진 탐색을 배우는 겸 문제 푸는 형태로 하기로 했다. 처음엔 너무 부담이 돼서 어떻게 쓸까 고민만 하다가 그냥 어렵게 생각하지 않고 편하게 문제를 풀어간다 생각하며 알고리즘 책 두 권을 펴놓고 풀었다. 그리고 들뜬 마음으로 이걸 프린트해서 가져가려고 했는데 선배들 하신걸 보니 이런게 아니라 이런 알고리즘을 응용해서 '논문'을 써오는 것이 진짜 숙제였고, 이런걸 가지고 무슨 스터디를 하겠나 싶어서 갈아엎어 버렸다... 막상 코드만 길고 별 것도 없는 보고서..였지만 어쨌거나 첫 시도였기도 하고 쓰고 풀고한게 아까워서 올려본다.