c언어 탐색 알고리즘에 대하여 알아보기

c언어 탐색 알고리즘에 대하여 알아보기

네 안녕하세요, 이번 포스팅에서는 탐색 알고리즘에 대하여 알아보도록 하겠습니다.

우리가 무언가를 알고 싶을 때 구글링을 하는 것처럼, 컴퓨터가 하는 작업에도 탐색이 포함이 되어있고,

가장 많이 쓰이는 작업 중 하나입니다.

그리고 이 작업 역시 시간을 많이 잡아먹기 때문에 효율적으로 쓰는 것이 중요합니다.

이제 이렇게 많이 쓰이는 알고리즘인 탐색에 대하여 같이 알아보도록 합시다.

그리고 이를 설명하기 위해서 가장 많이 쓰이는 탐색 방법인 순차 탐색과 이진 탐색을 이용하여 설명을 드리도록 하겠습니다.

 

1. 순차 탐색(선형 탐색)

순차 탐색은 현존하는 탐색 방법 중에서 가장 간단하고 직접적인 방법입니다.

그냥 배열에 있는 원소들을 순서대로 하나씩 꺼내서 탐색기와 비교해 원하는 값을 찾아내는 방법입니다.

그래서 일치하는 항목을 찾을 때 까지 반복을 계속하고, 상황에 따라서 아예 첫 시도에서 끝이 날 수도 있고,

마지막 배열 원소까지 가서 끝이 나는 경우도 있습니다.

그리고 평균적으로는 해당 배열들의 절반 내외로 찾고 종료가 되는 경우가 대다수입니다.

그럼 이에 대한 알고리즘을 코드로 한 번 나타내보도록 하겠습니다.

#include <stdio.h>

#define SIZE 10

int main()
{
    int key, i, A[SIZE] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    printf("찾을 값을 입력하세요 : ");
    scanf("%d", &key);

    for(i = 0; i < SIZE; i++)
    {
        if(A[i] == key)
        {
            printf("탐색 성공 인덱스 넘버: %d\n", i);
        }
    }

    printf("탐색을 종료합니다.\n");

    return 0;
}

이렇게 작성을 할 수 있습니다.

그리고 여기서 주의를 해야 할 점은, 늘 말씀드리다시피 컴퓨터는 항상 번호를 0부터 세기 때문에 배열 원소의 인덱스 번호도 0부터 시작을 합니다.

그래서 그 부분을 잘 보셔야 합니다.

그럼 결과를 보도록 하겠습니다.

찾을 값을 입력하세요 : 8
탐색 성공 인덱스 넘버: 7
탐색을 종료합니다.

찾고자 하는 숫자의 인덱스 번호를 잘 출력해주는 것을 보실 수가 있습니다.

반응형

 

2. 이진 탐색

앞서 보여드린 순차 탐색은 '선형 탐색'의 일종입니다.

선형 탐색은 왼쪽에서 오른쪽으로 가면서 순차적으로 탐색을 하는 방법인데, 그래서 그냥 무작위로 배열이 되어있어도 늘 첫 번째는 왼쪽부터라는 것입니다.

이는 데이터의 크기가 방대해지면 시간이 너무 오래 걸려서 효율이 떨어진다는 단점이 있습니다.

그럴 때 쓰는 탐색 방법 중 하나가 이진 탐색인데, 이를 쓰게 되면 탐색의 속도가 매우 빨라집니다.

이 방법은 탐색기가 배열 중앙에 있는 원소의 값과 비교를 하여 찾는 방법입니다.

이 말은 다시 말하면 배열이 일단 정렬이 되어있어야 한다는 뜻입니다.

그래서 일단 일차적으로 정렬을 해주고, 탐색을 합니다.

즉, 정렬이 되어있는 배열의 중앙 값을 비교를 한다는 것은, 보통 배열은 오름차순으로 정렬을 해서 가독성을 높인 형태를 취하고 있기 때문에 찾고자 하는 값이 중앙 원소 값 보다 크다면 오른쪽으로 이동을 하고,

반대로 값이 작다면 왼쪽으로 이동을 하여 값을 찾게 됩니다.

그래서 그 과정에서 무조건적으로 왼쪽에서 오른쪽으로 이동을 하는 것이 아니라,

대소 관계 비교를 통하여 키 값을 찾아내기 때문에 찾고자 하는 값의 크기에 따라서 배열의 일부분을 배제시키고 봅니다.

그래서 탐색의 범위가 매우 큰 폭으로 줄어들어서 탐색 시간이 빨라지는 것입니다.

그러면 이에 대한 알고리즘을 코드로 한 번 작성을 해보도록 하겠습니다.

#include <stdio.h>

#define SIZE 10

int binary_search(int A[], int n, int key);

int main()
{
    int key, A[SIZE] = {2, 4, 5, 7, 9, 11, 14, 16, 45, 55};

    printf("찾고자 하는 값을 입력하세요 : ");
    scanf("%d", &key);

    printf("탐색 결과(인덱스) : %d\n", binary_search(A, SIZE, key));

    return 0;
}

int binary_search(int A[], int n, int key)
{
    int l, m, h; // l = low, m = middle, h = high

    l = 0;
    h = n - 1;

    while(l <= h)
    {
        printf("[%d %d]\n", l, h);

        m = (l + h) / 2;

        if(key == A[m])
        {
            return m;
        }

        else if(key > A[m])
        {
            l = m + 1;
        }

        else
        {
            h = m - 1;
        }
    }

    return -1;
}

이렇게 작성을 했습니다.

이 방법은 숫자들이 남아있을 때 하한값과 상한 값을 계속 반환을 시켜 중앙 위치를 계산하여 찾고자 하는 값이 중앙에 있다면 탐색을 성공을 한 것이고, 그게 아니라면 두 가지 경우가 생기죠?

키 값이 더 클 경우에는 중앙 값을 맞춰줘야 하기 때문에 중앙값에 1을 더해서 중앙값을 더 키워주고,

반대로 키 값이 더 작을 경우에는 중앙 값을 맞춰주기 위해서 중앙값에 1을 빼줍니다.

그러면 결과를 보도록 하겠습니다.

찾고자 하는 값을 입력하세요 : 16
[0 9]
[5 9]
탐색 결과(인덱스) : 7

해당 숫자가 들어있는 인덱스 번호를 잘 찾아낸 것을 볼 수가 있습니다.

그리고 여기에서 주의 사항은 데이터가 정렬이 되어있어야 하므로,

데이터를 한 번 정렬을 해주고 사용을 하시거나,

애초에 정리가 되어있는 데이터에 이용하시기를 권장합니다.

 

여기까지 탐색에 대하여 알아보았는데오,

다음 포스팅에서는 2차원 배열에 대하여 알아보도록 하겠습니다.

긴 글 읽어주신 독자분들께 진심으로 감사드립니다 ~