완전 탐색(Brute-Force Search) / 이진 탐색(Binary Search)

귀여운 짹짹이 사진으로 시작합시다

 

 오늘은 완전 탐색과 이진 탐색에 대해 다뤄볼까 합니다.

 

[완전 탐색(Brute-Force Search)]

 

 사탕 바구니에 10개의 사탕이 들어있다고 합시다. 그중에 포도 사탕을 찾아서 먹고 싶은데, 포도 사탕을 어떻게 찾아야 할까요? 답은 어렵지 않습니다. 하나씩 꺼내서 포도 사탕인지 확인해보면 되겠죠.

 

 이러한 탐색 방법이 완전 탐색입니다. 모든 요소에 대해 자기가 찾고자 하는 대상인지 확인해보는 방법이죠.

그럼 이 방법이 어떻게 프로그래밍에서 쓰일까요?

 

 [0,3,2,5,6]의 배열이 주어집니다. 여기서 5가 몇번째 수인지 알고 싶은데, 어떻게 해야할까요?

 

 답은 간단하죠. 4번째 수입니다. 처음의 수부터 비교하여 언제 5가 나오는지 찾아내면 쉽게 알 수 있겠죠. 이것을 프로그램으로 만든다면 다음과 같습니다.

 

#include <iostream>

using namespace std;

int main()
{
    int arr[5]={0,3,2,5,6};
    int i=0;
    int target=5;

    for(i=0;i<5;i++)
    {
        if(arr[i]==target)
        {
           cout << i+1 << endl;
            break;
        }
    }

    return 0;
}

 

 이렇게 모든 요소들을 하나하나 비교해가면서 답을 찾는 방법을 완전 탐색이라고 합니다.

간단한 예제를 풀어보면서 정리해보죠.

 

[예제]

첫 줄에 자연수 a,b,n이 주어진다.

그리고, 그 다음줄에 크기가 a인 배열 A[a]의 요소 A[1],A[2]...A[a]가 공백을 두고 주어진다.

그 다음줄에는 크기가 b인 배열 B[b]의 요소 B[1],B[2]...B[b]가 공백을 두고 주어진다.

(배열의 인덱스는 1부터 시작한다.)

 

(A[i]×B[j])≡0(mod n)인 순서쌍 (i,j)의 개수를 출력하시오.

(a≤100, b≤100, 1<n≤10)

 

 

 

 일단 문제를 해석해봅시다. (A[i]×B[j])≡0(mod n)는 (A[i]×B[j])가 n으로 나누어떨어지냐를 묻는 식임을 알 수 있습니다.

그러니까, 배열 A의 요소와 배열 B의 요소를 곱했을 때 그 값이 n으로 나누어떨어지는 경우의 개수를 찾는 것이네요.

 

 a≤100, b≤100이기 때문에 완전 탐색을 해도 괜찮을 것 같습니다. 어떻게 완전 탐색을 해야 할까요?

 

 답은 가능한 모든 순서쌍에 대해 조건을 만족하는지 탐색해보면 됩니다. 이중 반복문을 사용하면 쉽게 해결할 수 있습니다.

 

[답]

#include <iostream>

using namespace std;

int main()
{
    int a,b,n;
    int A[100];
    int B[100];
    int i,j;
    int cnt=0;

    cin >> a >> b >> n;

    for(i=0;i<a;i++)
    {
        cin >> A[i];
    }

    for(i=0;i<a;i++)
    {
        cin >> B[i];
    }

    for(i=0;i<a;i++)
    {
        for(j=0;j<b;j++)
        {
            if((A[i]*B[j])%n==0)
                cnt++;
        }
    }

    cout << cnt << endl;

    return 0;
}

[이진 탐색(Binary Search)]

 

 업다운 게임을 해보신 적 있으신가요? 사회자가 1~100까지의 수를 하나 정하면, 참가자들이 그 수가 무엇인지를 맞추면 되는 게임입니다. 이때, 사회자가 정한 수가 참가자들이 추측한 수보다 크다면 UP을, 작다면 DOWN을 말해줍니다. 이를 토대로 정해진 횟수 내에 사회자가 어떤 수를 정했는지 맞추면 됩니다.

 

 업다운 게임을 잘할 수 있는 전략이 있을까요? 우선 앞서 다룬 완전 탐색을 적용해보도록 합시다.

 

완전 탐색은 다음과 같이 적용할 수 있습니다. 1부터 시작하여 100까지 전부 도전해보는 것입니다. 최악의 경우 100번째에 맞출 수 도 있겠죠. 기댓값은 50.5번째가 되겠네요.

 

 하지만 업다운 게임은 그리 호락호락하지 않습니다. 보통 7~8번 내로 정답을 맞추어야 합니다. 그렇다면 어떤 방법을 사용해야 할까요?

 

 앞서 완전 탐색에서는 사용하지 않은 성질이 하나 있습니다. 바로 제시한 수가 더 큰지, 작은지를 알 수 있다는 것이죠. 이 사실을 어떻게 이용해야 할까요?

 

 수의 범위가 작은 경우부터 봅시다. 1부터 3까지의 수를 맞추어야 한다고 하죠. 어떤 수를 고르는 것이 좋을까요?

답은 간단합니다. 처음에는 2를 고르면 됩니다. 만약 2가 아니라고 해도, 그 수가 2보다 큰지, 작은지 알 수 있기 때문에 그 다음번에 바로 답을 맞출 수 있게 됩니다.

 

 방금 어떤 전략을 사용한 걸까요? 바로 중간 값을 선택했습니다. 이 방법은 1부터 100까지의 수를 맞출때도 효율적입니다. 한번의 선택만으로 후보군을 절반으로 줄일 수 있기 때문이죠.

 

 예를 들어봅시다. 사회자가 선택한 값이 72라고 합시다. 앞서 말한 전략을 사용해보죠.

 

먼저, 50을 선택합니다. 그럼, UP이라는 답변을 얻을 겁니다.

다음, 75를 선택합니다. 그럼, DOWN이라는 답변을 얻을 겁니다.

다음, 62를 선택합니다. 그럼, UP이라는 답변을 얻을 겁니다.

다음, 68을 선택합니다. 그럼, UP이라는 답변을 얻을 겁니다.

다음, 71을 선택합니다. 그럼, UP이라는 답변을 얻을 겁니다.

다음, 73를 선택합니다. 그럼, DOWN이라는 답변을 얻을 겁니다.

마지막으로, 72를 선택합니다.

 

이 방법을 코드로 구현한다면 다음과 같습니다.

 

#include <iostream>

using namespace std;

int main()
{
    int s=1,e=100;
    int n;
    int cnt=0;

    cin >> n;

    while((s+e)/2!=n)
    {
        cout << (s+e)/2 << " ";
        
        if((s+e)/2>n)
            e=(s+e)/2-1;
            
        else if((s+e)/2<n)
            s=(s+e)/2+1;

        cnt++;
    }

    cout << endl;

    cout << n << endl; // 답
    cout << cnt << endl; // 탐색한 횟수

    return 0;
}

 

이 방법이 바로 이진 탐색입니다. 정렬된 값들에 한정해서 원하는 값을 빠르게 찾을 수 있는 방법입니다.

n개의 수를 찾을 때, 최악의 실행 횟수가 log_2 n이 됩니다. n이 약 21억일때도 약 31회 정도에 찾을 수 있습니다.

 

 

 

 

 다음 게시물은 파라메트릭 서치가 될 예정입니다.

사실 한 게시물에 이어서 쓸 수 있지만.. 너무 길어질 것 같아 여기서 끊으려고 합니다

다음에 봐요