탐색(Search)
탐색이란 리스트 내에서 원하는 데이터를 탐색하는 방법을 말한다.
데이터를 정렬하는 것 말고도 원하는 데이터를 탐색할 때에도 여러가지 알고리즘을 적용할 수 있다.
탐색법 중에 잘 알려진 것으로는 가장 기본적인 탐색법인 순차 탐색(또는 선형 탐색으로도 알려져 있다), 이번에 알아볼 이진 탐색, 그리고 해시 탐색 등등이 있다.
순차 탐색(Sequential Search)
이진 탐색에 대해 알아보기 전에, 가장 기본이 되는 탐색법인 순차 탐색(Sequential Search), 또는 선형 탐색(Linear Search)에 대해서 알아보자. 쉽게 말해서 순차 탐색법은 리스트의 처음부터 시작해 찾는 데이터가 나올 때까지 다음 데이터로 넘어가며 무식하게 전부 탐색하는 방법이다.
위 그림은 순차 탐색의 작동 원리를 간략하게 설명한다.
최선의 경우(원하는 데이터가 첫 번째 인덱스에 위치한 경우)에는 비교 연산 한 번에 종료되지만, 최악의 경우(원하는 데이터가 마지막 인덱스에 위치한 경우)에는 리스트의 길이만큼 정직하게 전부 비교해야 한다는 단점이 있다. 따라서 순차 탐색의 시간복잡도는 O(N)으로 표기할 수 있다.
다음 코드는 순차 탐색을 파이썬으로 구현한 것이다.
fruits = ["Banana", "Grape", "Apple", "Lemon", "Orange", "Pineapple"]
def sequential_search(data, target):
for index in range(len(data)):
#리스트 안의 원소를 하나씩 비교해서
if data[index] == target: return index
#원하는 데이터를 찾았다면 현재의 인덱스를 반환한다.
index = sequential_search(fruits, "Apple")
print(index)
2
이진 탐색(Binary Search)
이진 탐색은 리스트 내부의 데이터가 정렬되어 있어야만 사용할 수 있다는 점에서 순차 탐색과 대조된다. 따라서 데이터는 어떠한 방법으로든 특정 기준에 따라 정렬될 수 있어야 한다. (일치/불일치 비교가 아닌 값 간의 대소 비교를 해야 하기 때문.)
데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있고, 이 이점은 리스트의 길이가 커질수록 커진다. 따라서, 탐색해야 할 리스트의 범위가 2000만을 넘어간다면 순차 탐색으로는 시간 초과 판정을 받게 될 수 있으니 이런 상황에서 이진 탐색을 떠올릴 수 있는 것이 중요하다.
이진 탐색은 위치를 나타내는 변수 3개를 사용하는데, 탐색하고자 하는 범위의 시작점, 끝점, 중간점이다. 찾으려는 데이터와 중간점에 위치한 데이터를 계속해서 비교함으로써 원하는 데이터를 찾는 것이 이진 탐색법이다.
이진 탐색의 절차를 글으로 나타내면 다음과 같다.
1. 정렬된 리스트의 처음을 시작점, 마지막을 끝점으로 정한다.
2. 시작점과 끝점의 정중앙에 위치한 원소를 중간점으로 정한다. 만약 남은 부분의 길이가 짝수일 경우에는 2개의 중앙 중 앞에 있는 것을 택한다.(앞에 있는 것을 택할지 뒤에 있는 것을 택할지는 구현하는 사람의 자유이다.)
3. 선택된 중간점의 데이터와 얻고자 하는 데이터를 비교한다.
4. 중간점의 데이터가 얻고자 하는 데이터와 같다면, 중간점의 인덱스를 반환하고 탐색을 종료한다.
5-1. 만약 중간점의 데이터가 얻고자 하는 데이터보다 크다면, 현재의 중간점을 새로운 끝점으로 정한 뒤, 2번부터의 과정을 반복한다.
5-2. 만약 중간점의 데이터가 얻고자 하는 데이터보다 작다면, 현재의 중간점을 새로운 시작점으로 정한 뒤, 2번부터의 과정을 반복한다.
위 그림은 이진 탐색의 작동 과정을 간략하게 설명한다.
위 그림에서 볼 수 있듯, 전체 데이터는 16개이지만 3번의 비교를 통해 원하는 결과를 얻을 수 있었다. 이진 탐색은 한 번 비교를 할 때마다 확인하는 원소의 개수가 절반으로 줄어든다는 점에서 굉장히 효율적이다. 리스트의 길이가 두 배가 된다고 하더라도 평균 비교 횟수는 한 번밖에 늘어나지 않기 때문이다.
따라서 이진 탐색법의 비교 횟수는 log₂N에 비례하며, Big-O Notation을 이용해 표기하면 O(logN)으로 나타낼 수 있다.
이진 탐색을 구현하는 방법에는 크게 두 가지가 있는데, 한 가지는 재귀함수를 활용하는 방법(Recursive)이고, 다른 한 가지는 반복문을 이용하는 방법(Iterative)이다.
characters = ["A", "B", "D", "F", "G", "H", "K", "M", "O", "Q", "S", "T", "V", "X", "Z"]
def binary_search_recursive(data, target):
#재귀함수를 통한 구현
mid_index = len(data) // 2
#줃간점 설정.
#시작점과 끝점은 재귀 방식에서는 명시할 필요가 없다. 앞뒤로 필요없는 데이터를 반복해서 잘라냄으로써 시작점과 끝점을 구현할 것이기 때문.
if data[mid_index] == target:
return mid_index
#현재 중간점의 데이터와 탐색 대상이 일치하는 경우: 중간점의 인덱스를 반환
elif data[mid_index] > target:
return binary_search_recursive(data[:mid_index + 1], target)
#중간점의 데이터가 탐색 대상보다 큰 경우: 중간점 이후의 데이터를 모두 잘라내고 재귀함수 실행
elif data[mid_index] < target:
return binary_search_recursive(data[mid_index:], target)
#중간점의 데이터가 탐색 대상보다 작은 경우: 중간점 이전의 데이터를 모두 잘라내고 재귀함수 실행
def binary_search_iterative(data, target):
#반복문을 통한 구현
start_index = 0
end_index = len(data)
mid_index = len(data) // 2
#시작점, 끝점, 중간점의 인덱스 선언
while data[mid_index] != target:
#중간점의 데이터와 탐색 대상이 일치하지 않는 동안 반복
if data[mid_index] > target:
#중간점의 데이터가 탐색 대상보다 큰 경우:
end_index = mid_index
#중간점을 새로운 끝점으로 설정.
else:
#중간점의 데이터가 탐색 대상보다 작은 경우:
start_index = mid_index
#중간점을 새로운 시작점으로 설정.
mid_index = (end_index - start_index) // 2
#시작점과 끝점의 위치가 변했으므로 새로운 중간점을 그 둘 사이에 위치시킨다.
return mid_index
#탐색이 끝나고 while문을 빠져나오면 중간점의 인덱스를 반환.
index_recursive = binary_search_recursive(characters, "H")
print(index_recursive)
index_iterative = binary_search_iterative(characters, "H")
print(index_iterative)
5
5
트리 자료구조와 이진 탐색
새로운 자료구조인 트리(Tree)에 대해서 간단하게 알아보자.
트리 자료구조는 노드와 노드의 연결로 표현하며, 여기에서 노드는 정보를 포함하고 있는 개체이다. 트리는 부모 노드와 자식 노드의 위계로 표현되는데, 최상단 노드인 루트 노드를 제외한 모든 노드들은 유일한 부모 노드를 가진다. 최하단 노드는 단말 노드라고 한다.
주로 거대한 데이터베이스의 데이터들이 트리 자료구조의 형태로 저장된다.
트리 자료구조에서는 이진 탐색과 유사하게 데이터의 탐색을 할 수 있는데, 부모 노드보다 왼쪽에 있는 자식 노드는 부모 노드보다 값이 작고 오른쪽에 있는 자식 노드는 부모 노드보다 값이 크다는 것이 보장되기 때문에 이진 탐색법과 유사하게 대소 비교를 하는 것으로 원하는 값을 찾아갈 수 있다.