알고리즘 - 이진탐색 코드를 짜보자(1)

오늘도 등장한 아메바쨩

 

오늘은 저번 이진탐색 개념정리에 이어서 직접 코드를 구현하는 시간을 가져보려고 한다.

 

 

https://shineild-security.tistory.com/22

알고리즘 - 이진탐색 알고리즘 개념

이진탐색을 진행함에 앞서서 필요한 전제조건이 뭔지 생각해보자.

우선은 데이터 정렬이 진행되어야 할 것이다.

여러 정렬들이 있지만 나는 하나밖에 정렬코드를 안만들어 놨음으로 버블소트 정렬을 사용할 것이다.

 

기존 버블소트 코드를 일단 가져왔다.

 

#include <stdio.h>

int main(int argc, const char * argv[]) {
    int num;
    printf("데이터 개수 입력 : ");
    scanf("%d", &num);
    int data[num];
    for (int i = 0; i < num; i++){
        printf("데이터 입력: ");
        scanf("%d", (data + i));
    }
    int tmp;
    for (int n = 0; n < num; n++){
        for (int i = n+1; i < num; i++){
            if (data[n] > data[i]){
                tmp = data[n];
                data[n] = data[i];
                data[i] = tmp;
            }
        }
    }

    return 0;
}

데이터 출력만 제거한체 그대로 인용하면 될 것같다.

 

 

음 이진탐색을 코딩하려면 일단 수학적으로 접근해서 분석해야 할 것 같아서 생각을 좀해보았다.

계속해서 반을 나누어 가기 때문에 기준점이 되는 숫자가 있을테고 그 숫자에 들어가 있는 값이 작을때와 클때로 경우를 나눌수가 있다.

만약 가운데 있는 숫자가 찾고자하는 숫자보다 크다면 우리는 어떻게 해야할까?

 

100개의 데이터(1부터 100까지 1씩 증가하는 데이터가 있다고 가정)가 있다고 가정하고 47이란 데이터를 찾기 원한다고 생각했을 때 100개의 가운데는 50일것이다.

그리고 50과  47을 비교해보았을 때 50이 더 크다.

이럴때는 우리는 다시 50을 반으로 나누어 25로 비교해 볼 것이다.

자 이제 이걸 숫자만 때서 생각해보자.

100 -> 50 -> 25

공식이 한눈에 보일것이다.

n(비교 대상 값)과 data(실제 알고자 하는 값)를 비교했을 때 n > data 일시에는 우리는 n/2를 해주면 된다.

 

그렇다면 반대로 n < data의 경우는 어떠할까?

찾고자하는 숫자가 69라고 했을때 50과 비교했을때 50이 더 작다.

그러면 우리는 다시한번 75와 비교해볼 것이다.

 

100 -> 50 -> 75

느낌은 대충 오지만 식으로 어떻게 구현해야 하나 잠시 고민할 수 있을법한 생각을 좀 해야하는 부분이다.

이 패턴을 공식화 하면 n = n/2(50/2) + n(50)이된다.

 

이제 공식은 대충 짜여졌으니 생각했던걸 코드로 구현하는 일만 남았다.

 

int n = num/2;
    int find;
    printf("찾고자 하는 숫자 : ");
    scanf("%d", &find);
    while(1){
    
        if (data[n] == find){
            printf("%d번째에 %d가 들어있습니다.\n", n+1, find);
            break;
        }
        else if (data[n] > find){
            n = n/2;
        }
        else if (data[n] < find){
            n = (n/2) + n;
        }
    }

 

앞에 말한 공식을 코드로 구현하면 대충 이렇게 될 것이다.

 

이제 두개를 함께 맞춰주기만 하면 된다.

 

#include <stdio.h>

int main(int argc, const char * argv[]) {
    int num;
    printf("데이터 개수 입력 : ");
    scanf("%d", &num);
    int data[num];
    for (int i = 0; i < num; i++){
        printf("데이터 입력: ");
        scanf("%d", (data + i));
    }
    int tmp;
    for (int n = 0; n < num; n++){
        for (int i = n+1; i < num; i++){
            if (data[n] > data[i]){
                tmp = data[n];
                data[n] = data[i];
                data[i] = tmp;
            }
        }
    }
    int n = num/2;
    int find;
    printf("찾고자 하는 숫자 : ");
    scanf("%d", &find);
    while(1){
    
        if (data[n] == find){
            printf("%d번째에 %d가 들어있습니다.\n", n+1, find);
            break;
        }
        else if (data[n] > find){
            n = n/2;
        }
        else if (data[n] < find){
            n = (n/2) + n;
        }
    }
    return 0;
}

 

 

이렇게해서 이진탐색 알고리즘 코딩이 완성되었다.

이제 다음 포스팅때는 다른 사람들의 코드를 참고해서 더 보안해보도록 하려한다.