CS 부수기 - 알고리즘 (탐색) 편
0. 알고리즘이란
드디어, 코딩의 꽃 알고리즘으로 오게 되었다.
알고리즘(Algorithm)의 정의는 위키피디아에 따르면 다음과 같다.
Algorithm : 국어로는 셈법이라고도 하며 수학, 컴퓨터 과학, 전산 언어학 등에서 문제 해결 방법을 정의한 단계적 절차이자 문제 해결을 위한 동작들의 모임
이렇게 정의된다.
우리가 전공하는 컴퓨터에서의 알고리즘은, 크게 탐색과 정렬이 있다.
조금 더 세부적으로 뻗어나가면 완전 탐색, 그리디(Greedy, 탐욕법) 알고리즘, 최단 경로(Dijkstra) 등이 있다.
그 중 오늘은 탐색 알고리즘부터 알아보자.
1. 탐색 알고리즘
탐색 알고리즘은 영어로는 Searching Algorithm이라고 하며 정의는 다음과 같다.
많은 자료들 중 원하는 자료를 찾아내는 방법
이러한 탐색 알고리즘은 크게 2가지의 형태로 나누어진다.
- 정렬되지 않은 리스트에서의 탐색 :
순차 탐색 - 정렬된 리스트에서의 탐색 :
이진 탐색,색인 순차 탐색
탐색 알고리즘의 대표적인 알고리즘은 순차 탐색, 이진 탐색, 색인 순차 탐색이 있는데, 각각의 알고리즘들은 위의 경우로 해당된다.
그렇다면 먼저 순차 탐색 알고리즘부터 코드와 같이 리뷰하겠다.
2. Sequential Search Algorithm
순참 탐색, Sequential Search는 말 그대로 처음부터 끝까지 다 보는 것 을 의미한다.
때문에 선형 탐색이라고 부르기도 한다.
예를 들어 아래 그림과 같이 어느 한 리스트에 원소가 쭉 나열되어 있다고 가정하자.
만약에 필자가 (4)번 속성을 찾고 싶다면, 순차 탐색의 경우 (1)번부터 (2)번, (3)번을 거쳐 도달하는 형태이다.
이러한 특성 때문에 순차 탐색의 경우 리스트가 정렬되어 있지 않아도 탐색이 가능하다.
코드를 통해 알아보자.
// 순차 탐색
#include <stdio.h>
#define MAX_SIZE 100
// List 선언
int list[MAX_SIZE];
// 처음과 끝 숫자를 받아 리스트로 만들어줌
int make_list(int first, int last) {
int index = 0;
// loop 돌며 리스트 속성 추가
for (int i = first; i <= last; i++) {
list[index] = i;
index++;
}
return 0;
}
// 순차 탐색 알고리즘
int linear_search(int key) {
int index;
// index 0부터 각 index의 속성이 찾고자 하는 값(key)과 같은지 확인
for (index = 0; index <= MAX_SIZE; index++) {
// 같을 경우 break로 loop 정지
if (list[index] == key) {
printf("Index of %d : No.%d\n", key, index);
break;
}
}
// 값이 존재하지 않을 경우 -1 반환
return -1;
}
int main() {
make_list(1, 10);
linear_search(4);
make_list(50, 128);
linear_search(88);
}
복잡한 코드는 아니다.
리스트를 생성하고, 0번 인덱스부터 값을 비교하며 찾고자 하는 값이 나왔을 때 그 인덱스를 반환해주는 형태이다.
파이썬으로 작성하면 다음과 같다.
# 순차 탐색
# 리스트와 찾고자 하는 값을 parameter로 받음
def linear_search(num_list, key):
# loop를 돌며 원하는 값(key)을 가르키는 index를 반환
for i in range(len(num_list)):
if num_list[i] == key:
return i + 1
# 원하는 값이 없을 경우 False 반환
return False
numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(linear_search(numbers, 6))
print(linear_search(numbers, 20))
순차 탐색의 시간 복잡도는 다음과 같다.
\[(1 + 2 + 3 + 4 + ... + n) / n = (n + 1) / 2\]즉, 탐색에 실패한다는 가정 하에 n번반복하기 때문에 평균 O(n)의 시간 복잡도를 가지게 된다.
3. Binary Search Algorithm
이진 탐색, Binary Search은 찾는 값이 있는 리스트를 반으로 쪼개 찾는 값이 왼쪽 리스트에 속하는지 오른쪽 리스트에 속하는지 비교하며 탐색하는 방법이다.
이러한 이진 탐색의 특성으로 이진 탐색은 정렬되어 있는 리스트에서 사용하는 특성을 가지게 된다.
그림으로 나타내면 다음과 같다.
(1)번부터 (7)번까지 리스트가 있다고 가정하자.
필자가 찾고자 하는 값은 (1)번이다.
그렇다면, (1)번 ~ (7)번의 속성에서 가장 가운데에 있는 속성은 (4)번이 된다.
(1)번은 (4)번보다 작으므로 (1)번 ~ (3)번까지의 리스트에서 다시 비교한다.
마찬가지로 속성들 중 가장 가운데는 (2)번이고, (1)번은 (2)번에 비해 작으므로 다시 (1)번으로 리스트를 쪼갠다.
이렇게 최종적으로 (1)번 속성을 찾을 수 있다.
코드를 통해 알아보자.
// 이진 탐색
#include <stdio.h>
#include <time.h>
#define MAX_ELEMENTS 10000000L
// 리스트와 몇 번 쪼갰는지 확인을 위한 count 변수 생성
int list[MAX_ELEMENTS];
int count = 0;
// 처음과 끝 숫자를 받아 리스트 만들어줌
int make_list(int first, int last) {
int index = 0;
// loop 돌며 속성 추가
for (int i = first; i <= last; i++) {
list[index] = i;
index++;
}
return 0;
}
// 이진 탐색 알고리즘
int search_binary(int key, int low, int high) {
// 리스트의 가운데를 가르킬 값
int middle;
if (low <= high) {
// 처음과 끝을 2로 나누어 가운데 값 만들어냄
middle = (low + high) / 2;
// 찾는 값(key)가 가운데 값과 같을 경우 count 세고 반환
if (key == list[middle]) {
count++;
printf("Search Count = %d", count);
return middle;
// 찾는 값이 가운데 값보다 작을 경우
} else if (key < list[middle]) {
count++;
return search_binary(key, low, middle - 1);
// 찾는 값이 가운데 값보다 클 경우
} else {
count++;
return search_binary(key, middle + 1, high);
}
}
// 값이 없을 경우 -1로 반환
return -1;
}
int main() {
make_list(0, 10);
search_binary(4, 0, 10);
}
코드에 관해 간단한 설명을 덧붙이자면, 찾고자 하는 값이 전체 리스트의 가운데 값보다 작다면 왼쪽을 탐색하고, 크다면 오른쪽을 탐색하며 최종적으로 그 위치를 알아낸다.
각 과정을 거칠 때 마다 한번씩 count해주어 최종적으로 몇 번에 탐색을 거쳤는지 반환해주며 코드는 종료된다.
파이썬으로 나타내면 다음과 같다.
# 이진 탐색
def binary_search(num_list, key):
# 리스트 정렬
num_list.sort()
# 리스트의 시작 index, 마지막 index와 count값 생성
start = 0
last = len(num_list) - 1
count = 0
# 시작 index와 마지만 index가 같아질 때 까지 반복
while start <= last:
middle = (start + last) // 2
# key값(탐색값) == 가운데 값
if num_list[middle] == key:
count += 1
print("Search Count =", count)
return middle
# key값이 더 클 경우
elif num_list[middle] < key:
start = middle + 1
count += 1
# key 값이 더 작을 경우
else:
last = middle - 1
count += 1
# 탐색에 실패할 경우
return -1
num_list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
binary_search(num_list, 4)
이진 탐색의 시간 복잡도는 다음과 같다.
n개의 원소 중 하나의 원소를 특정하고자 할 때, 모두 반으로 나누면서 탐색을 이어 나가기에, 최종 탐색의 범위가 1이 되기 위해서의 탐색 횟수를 k로 정의하면,
로 정리되며 즉, 시간 복잡도는 $ O(log_2n) $이 된다.
4. Index Sequential Search Algorithm
인덱스 순차 탐색, Index Sequential Search는 인덱스 테이블을 이용하여 탐색의 효율을 높이는 방법이다.
일반적으로는 인덱스 테이블과 전체 주 리스트 두 개의 테이블을 이용하여 서로 비교하며 탐색하는 방법으로 이진 탐색과 마찬가지로 인덱스를 가지고 있기에 정렬된 형태에서만 사용이 가능하다.
그림으로 나타내면 다음과 같다.
10이라는 속성에 대한 인덱스가 1번, 40이라는 속성에 대한 인덱스가 4번, 60이라는 속성에 대한 인덱스가 6번이라고 가정하자.
내가 찾고자 하는 값을 20이라고 할 때, 인덱스 테이블에서 해당하는 인덱스는 10과 40의 사이 이므로, 1번과 4번인덱스 사이에 있다는 것을 확인했다.
이를 바탕으로 우리는 20을 찾을 때 1번인덱스 부터 4번인덱스 사이에서만 탐색을 진행하면 되므로, 최종적으로 10 ~ 40속성 안에서 20을 탐색하면 되는 것이다.
코드를 통해 더 자세히 알아보자.
// 색인 순차 탐색
#include <stdio.h>
#define MAX_SIZE 1000
#define INDEX_SIZE 10
// 전체 list 정의
int n = 9;
int list[MAX_SIZE] = {3, 9, 15, 22, 31, 55, 67, 88, 91};
// index table 구조 생성
typedef struct {
int key;
int index;
} indexTable;
// index table
indexTable index_list[INDEX_SIZE] = { {3, 0}, {15, 2}, {67, 6} };
// index table에서 받아온 low와 high 값으로 주 list에서 검색
// 31을 검색할 경우, low = 2, high = 6
int sequential_search(int key, int low, int high) {
int i;
// index 2번 부터 index 6번까지 속성 비교, 최종 key값에 대한 index 반환
for (i = low; i <= high; i++) {
if (list[i] == key) {
printf("Key is in index No.%d.\n", i);
return i;
}
}
// 없을 경우 -1 반환
return -1;
}
// index table에서 index 찾기
int index_search(int key) {
// i = index 번호, low = index 전 값, high = index 다음 값
int i, low, high;
// 찾고자 하는 key 값이 index table의 0번 속성보다 작거나,
// 마지막 index의 속성보다 클 경우 -1 반환
if (key < list[0] || key > list[n - 1]) {
return -1;
}
// key의 범위를 찾기 위해 index table애서 각 속성들 겁색
for (i = 0; i < INDEX_SIZE; i++) {
if (index_list[i].key <= key && index_list[i + 1].key > key) {
break;
}
}
// i가 속하는 범위를 low 와 high로 만들어줌
// i의 번호가 index table의 마지막 번호일 때
if (i == INDEX_SIZE) {
low = index_list[i - 1].index;
high = n;
printf("Key is located in between of No.%d INDEX and No.%d INDEX.\n", low, high);
// i의 번호가 index table의 마지막 번호가 아닌 곳에 있을 때
} else {
low = index_list[i].index;
high = index_list[i + 1].index;
printf("Key is located in between of No.%d INDEX and No.%d INDEX.\n", low, high);
}
// sequential_search로 key값과 범위 반환
return sequential_search(key, low, high);
}
int main() {
index_search(31);
}
내가 찾고자 하는 값을 index table에서 검색한다.
index table의 범위 내에 내가 찾고자 하는 값이 범위 내에 있을 경우, 그 범위를 주 리스트로 보내주어 최종적으로 주 리스트에서는 모든 값을 탐색하는 것이 아니라, 내가 필요한 범위 내에서만 탐색하도록 만들어준다.
만약 내가 찾고자 하는 값이 index table에 없을 경우는 -1을 반환하게 되며, 주 리스트에서도 탐색할 때 탐색 값이 없다면 -1을 반환하게 한다.
다음은 파이썬으로 설계한 알고리즘이다.
# 색인 순차 탐색
# main list, index table 선언
num_list = [3, 9, 15, 22, 31, 55, 67, 88, 91]
index_table = [[0, 3], [2, 15], [6, 67]]
index_size = len(index_table)
# main list에서의 겁색
def sequential_search(key, low, high):
for i in range(low, high, 1):
if num_list[i] == key:
print("Index number :", i, "Key :", key)
return i
return -1
# index table에서 index 범위 반환
def index_search(key):
i, low, high = 0, 0, 0
if key < num_list[0] or key > num_list[len(num_list) - 1]:
return -1
for i in range(0, index_size, 1):
if i < index_size - 1:
if index_table[i][1] <= key and index_table[i + 1][1] > key:
break
elif i == index_size - 1:
if index_table[i][1] >= key:
break
if i == index_size - 1:
low = index_table[i - 1][0]
high = len(num_list)
else:
low = index_table[i][0]
high = index_table[i + 1][0]
return sequential_search(key, low, high)
index_search(31)
색인 순차 탐색의 시간 복잡도는 다음과 같다.
index table의 크기가 커지면 index table에서 탐색 시간이 늘어나는 대신, 주 리스트에서는 탐색 범위가 줄어들기에 시간이 줄어든다.
반면, index table의 크기가 작아지면 탐색 시간이 줄어드는 대신, 주 리스트에서는 탐색 범위가 늘어나기에 탐색 시간이 늘어난다.
즉, index table의 크기에 의해 그 성능이 좌우되기 때문에 다음과 같은 공식이 생긴다.
index table의 크기 m, 주 리스트의 크기 n으로 가정할 경우,
이 된다.
5. 마치며
이로써 탐색 알고리즘은 마무리가 된다.