자료의 정렬과 탐색 - 3. 자료의 탐색(1)

탐색이란?

탐색(Search)는 주어진 원소들 중에서 특정 조건을 만족하는 원소를 찾는 것을 의미합니다. (탐색과 검색은 같은 의미로 사용되곤 합니다.) 원소가 가진 속성중 탐색 대상이 되는 속성(properties)를 키(key)값이라고 합니다.

탐색과 정렬은 자료의 처리 및 분석에 관련된 대부분의 문제 해결에 이용되는 기본 연산이며, 실제로 데이터를 처리하는 데 걸리는 시간보다 데이터를 검색하는데 걸리는 시간이 길어진다면 전체적인 작업 속도가 늦어지므로 효율적인 탐색에 대한 필요성이 강화되었습니다. 

탐색은 대부분의 데이터 처리 작업에서 임계 경로에 포함되는 핵심적인 작업인데, 임계 경로란 작업을 해결하는데 있어 가장 긴 경로(처리 시간이 가장 오래 걸리는 경로) 를 말합니다. 따라서 임계 경로의 길이(수행 시간)을 줄이게 된다면 작업의 전체 시간이 짧아지게 됩니다. 이 임계 경로는 추후에 알고리즘의 효율성을 평가하는데에도 이용하게 됩니다.

비록 탐색이 컴퓨터의 빠르고 정확한 계산 능력을 기반으로 한다고 하더라도, 자료의 양이 매우 많거나 크기가 클경우 컴퓨터를 사용해도 오랜 시간이 걸릴 수 있습니다. 따라서 이러한 자료의 양과 종류에 따라 적합한 탐색 전략이 존재합니다.

이 글에서는 다양한 탐색 알고리즘(탐색 전략) 중 몇가지를 알아보도록 하겠습니다.

순차 탐색(Sequential Search)

순차탐색이란 주어진 원소의 첫번째부터 끝까지 차례대로 모든 요소를 비교해 자료를 찾는 탐색 알고리즘 입니다. 탐색의 수행 방향이 한쪽 방향으로만 흘러 탐색을 수행하기 때문에 선형 탐색(Linear Search)라고도 합니다.

탐색 알고리즘중 가장 단순한 형태를 가진 알고리즘이라고 할 수 있습니다. 순서대로 하나씩 찾다보면 언젠가는 찾고자 하는 Key값을 찾을 수 있을것이고, 주어진 원소를 모두 탐색했는데도 해당하는 값이 없다면 단순히 찾고자 하는 원소가 목록에 없었던 것이라고 판단하면 됩니다. 

순차 탐색 알고리즘으로 탐색을 수행하게 된다면, 운이 좋다면 한번에도 원하는 값을 찾을 수 있을지도 모르지만, 최악의 상황(맨 마지막에 찾고자 하는 원소가 있거나 혹은 목록에 원소가 없는 경우) 목록을 모두 한번씩 탐색해야 하기 때문에 목록의 크기만큼 탐색을 수행해야 할 수도 있습니다. 따라서 효율성이 좋은 알고리즘이라고 보기는 어렵습니다.

#include <stdio.h>

int main()
{
    int d[5], key;
    
    for(int i=0; i<5; i++){  //배열에 5개의 정수를 입력받습니다
        scanf("%d", &d[i]);
    }
        
    printf("Key = ");       //탐색할 키 값을 입력받습니다
    scanf("%d", &key);
    
    int loc=0;
    while(loc<=5 && d[loc] != key) 
        loc++; //첫번째 자리부터 비교를 시작해, 탐색할 값과 불일치할 경우 loc변수에 1씩 더합니다
    
    if(loc > 5)
        loc = -1;  //변수의 크기를 초과할경우 -1을 loc에 저장합니다.
    
    if(loc == -1){
        printf("목록에 없음!");  //loc가 -1인 경우 목록에 없는 것으로 판단합니다.
    }
    else
    {
        printf("%d번째에 %d존재", loc+1, key); //찾은 원소의 위치와 값을 출력합니다.
    }			//이때 loc에는 배열의 인덱스가 저장되어 있으므로 +1하여 출력합니다.
    return 0;
}

효율성이 좋은 알고리즘은 아니지만 설계 및 구현이 용이하고 리스트 내부의 자료를 구조화할 필요가 없기에 자료수가 적을때 편리하게 이용할 수 있는 알고리즘입니다. (하지만 자료의 양이 많은 인터넷 검색등의 작업에는 탐색 속도때문에 한계가 명확하게 드러납니다.)

단계	d[1]	d[2]	d[3]	d[4]	d[5]
초기	3	7	10	22	44
key 값	22
1 단계	3 != 22
2단계		7 != 22
3단계			10 != 22
4단계				22 == 22
완료	22는 d[4]에 존재

2진 탐색(Binary Serach)

2진 탐색이란 주어진 원소들을 탐색이 필요한 영역과 불필요한 영역으로 나누어 가며 수행하는 알고리즘입니다. 한번 탐색을 수행할때 마다 리스트의 원소들이 둘로 분할되기 때문에 2진 탐색(또는 2분 탐색)이라는 이름이 붙게 되었습니다.

2진 탐색은 목록을 둘로 나누며 탐색을 진행합니다. 이는 업 앤 다운 게임(*임의의 숫자를 정해놓고, 어떤 수보다 큰지 작은지를 말해주며 임의의 수가 무엇인지 맞추는 게임)과 비슷하게 진행되게 되는데,  해봤다면 알겠지만 범위를 크게 정해두어도 대게 10번의 질문 안에 숫자를 맞출 수 있습니다. 이처럼 2진 탐색은 자료의 수가 많아질수록 순차 탐색에 비해 매우 높은 효율을 보이게 되는데, 리스트의 원소들이 미리 정렬되어 있어야 적용할 수 있는 방법입니다.

단계	d[1]	d[2]	d[3]	d[4]	d[5]	d[6]	d[7]	d[8]	d[9]
초기	1	3	4	10	20	22	33	68	76
key 값	68
1단계	탐색이 필요 없음				20 < 68	22	33	68	76
2단계	탐색이 필요 없음						33 < 68	68	76
3단계	탐색이 필요 없음							68 = 68	탐색X
완료	68은 d[8]에 존재

*c언어 코드는 작성 예정