알고리즘 2-1강. 탐색 알고리즘 - 순차 탐색(Sequential Search)

[탐색 알고리즘 강좌]

데이터를 찾아보자!

순차 탐색(Sequential Search)

---

이 강좌에서 알게될 '순차 탐색(Sequential Search)'는 바로 데이터가 모인 데이터 배열이 있으면 이 데이터 배열의 처음부터 끝까지 차례대로 비교하여 원하는 데이터를 찾아내는 알고리즘입니다. 이 순차 탐색은 데이터를 따로 조작할 필요가 없어 단순하지만 비효율적이라는 단점을 지니고 있습니다. 추가로 순차 탐색은 단방향으로 탐색을 수행하기 때문에 선형 탐색(Linear Search)라고 부르기도 합니다.

위에서 말했듯이, 순차 탐색 알고리즘은 단순하여 구현이 정말 간단합니다. 순차 탐색은 정렬되어 있지 않은 데이터 배열에서 평균적으로 (n+1)/2번의 비교를 거치며, 최악의 경우 n번의 비교를 거칩니다. 시간 복잡도는 O(n)입니다. 우선 배열에서의 순차 탐색을 한번 보도록 할까요? seqeuntialSearch 함수를 정의하고, 매개변수로는 데이터 배열과 그 데이터 배열의 길이와 찾고자 하는 데이터를 입력받도록 하겠습니다. 그리고 데이터를 찾으면 0 이상의 숫자를 반환하고, 데이터를 찾지 못하면 -1를 반환하게 하도록 해봅시다.

#include <stdio.h>

int sequentialSearch(int dataArr[], int length, int findData)
{
	for(int i = 0; i < length; i++)
		if (dataArr[i] == findData) return i;
	return -1;
}

int main()
{
	int arr[] = {23, 25, 14, 5, 66, 72, 13, 224, 51};
	int length = sizeof arr / sizeof arr[0];
	int findData = 0;
	int findIndex = 0;

	while (true)
	{
		printf("찾으시는 데이터를 입력해주세요: ");
		scanf("%d", &findData);

		findIndex = sequentialSearch(arr, length, findData);
		if(findIndex == -1) printf("데이터를 찾지 못했습니다.\n");
		else printf("데이터는 %d번째에 있습니다.\n", findIndex);
	}

	return 0;
}

결과:

찾으시는 데이터를 입력해주세요: 22
데이터를 찾지 못했습니다.
찾으시는 데이터를 입력해주세요: 23
데이터는 0번째에 있습니다.
찾으시는 데이터를 입력해주세요: 66
데이터는 4번째에 있습니다.
찾으시는 데이터를 입력해주세요: 442
데이터를 찾지 못했습니다.
찾으시는 데이터를 입력해주세요: 224
데이터는 7번째에 있습니다.
..

알고리즘의 구현이 매우 간단하여 따로 주석같은건 달지 않도록 하겠습니다. 이러한 순차 탐색 알고리즘은 데이터 배열의 크기가 작다면 용이하게 사용되며, 배열뿐만 아니라 리스트같은 자료구조에도 쉽게 적용이 가능합니다. 자료구조 강좌에서 설명드렸던 링크드 리스트(Linked List)를 기억하시나요? 한번 링크드 리스트에 순차 탐색 알고리즘을 적용해보도록 합시다.

#include <stdio.h>
#include <stdlib.h>

typedef struct Node
{
	int data;
	Node* link;
} Node;

void appendNode(Node** Head, int data)
{
	Node* newNode = (Node*)malloc(sizeof(Node));
	newNode->data = data;
	newNode->link = NULL;

	Node* tempPoint = (*Head);
	if (tempPoint != NULL) {
		while (tempPoint->link != NULL) tempPoint = tempPoint->link;
		tempPoint->link = newNode;
	} else *Head = newNode;
}

void printNode(Node** Head)
{
	Node* tempPoint = (*Head);

	if (tempPoint == NULL) printf("리스트가 비어 있습니다.\n");
	else if (tempPoint->link == NULL) printf("%d->NULL", tempPoint->data);
	else {
		while (tempPoint != NULL)
		{
			printf("%d->", tempPoint->data);
			tempPoint = tempPoint->link;
		}
		printf("NULL\n");
	}
}

Node* sequentialSearch(Node** Head, int findData)
{
	Node* tempPoint = (*Head);

	while(tempPoint != NULL) {
		if (findData == tempPoint->data) return tempPoint;
		tempPoint = tempPoint->link;
	}
	return NULL;
}

int main()
{
	Node* Head = NULL;
	Node* findNode = NULL;
	int findData = 0;

	appendNode(&Head, 33);
	appendNode(&Head, 128);
	appendNode(&Head, 64);
	appendNode(&Head, 72);
	appendNode(&Head, 53);
	
	while (true)
	{
		printf("찾으려고 하는 데이터를 입력해주세요: ");
		scanf("%d", &findData);

		findNode = sequentialSearch(&Head, findData);
		if (findNode != NULL) printf("찾은 노드의 위치: %#x\n", findNode);
		else printf("노드를 찾지 못했습니다.\n");
	}

	return 0;
}

결과:

찾으려고 하는 데이터를 입력해주세요: 54
노드를 찾지 못했습니다.
찾으려고 하는 데이터를 입력해주세요: 33
찾은 노드의 위치: 0x568ca8
찾으려고 하는 데이터를 입력해주세요: 72
찾은 노드의 위치: 0x568d50
찾으려고 하는 데이터를 입력해주세요: 53
찾은 노드의 위치: 0x568d88
..

위의 예제는 링크드 리스트에서 선형 탐색 알고리즘을 적용한 것입니다. 제일 앞의 노드인 헤드(Head) 노드부터 시작해서 다음 가리키는 노드(link)가 NULL일때까지, 즉 처음부터 끝까지 노드가 담고있는 데이터를 찾고자 하는 데이터와 서로 비교하여 일치하면 그 노드의 주소를, 일치하는 데이터가 없으면 NULL을 반환합니다. 간단하죠? 오늘은 간단히 탐색 알고리즘 중에서 가장 단순한 순차 탐색 알고리즘에 대해 알아보았습니다.

다음 강좌에서는 이진 탐색(Binary Search)에 대해 알아보도록 하겠습니다. 모두 수고하셨습니다.