[Algorithm]이진 탐색

이진 탐색(Binary Search)은 리스트 내에서 데이터를 매우 빠르게 탐색하는 알고리즘이다. 이진 탐색을 공부하기 전에 선형 탐색(Linear Search)에 대해 먼저 알아야 한다. 

 

선형 탐색은 리스트 내의 특정 요소를 찾기 위해 리스트의 처음부터 요소를 찾을때까지 순서대로 리스트를 탐색 하는것이다. 보통 정렬되지 않은 리스트에서 요소를 찾을때 사용된다. 선형 탐색은 정말 자주 사용되는데, 리스트에 특정 값이 있는지 체크할 때도 순차 탐색으로 원소를 확인하고, 리스트 자료형에서 특정한 값을 가지는 원소의 갯수를 셀 수 있는 count() 메서드를 이용할 때도 내부에서는 순차 탐색이 수행된다.

 

다음은 선형 탐색을 소스 코드로 구현한 것이다. 입력값 s는 문자열들을 담은 리스트라고 가정하자.

for i in s:
	if i == '구름'
    	return i

 

이 코드는 여러개의 문자열이 담긴 리스트 s를 for문을 통해 순회하며, 만약 현재 검사중인 리스트의 요소가 '구름'이라면, 그 문자열을 리턴하는 코드이다. 

 

따라서 데이터의 갯수가 N개일때 N번의 검색을 하므로 순차 탐색의 최악의 경우 시간 복잡도는 O(N)이다.

 

📎 이진 탐색 : 반으로 쪼개면서 탐색하기

이진 탐색은 배열의 내부가 정렬이 되어 있어야만 수행 할 수 있는 알고리즘이다. 데이터가 무작위 상태일땐 사용 할 수 없지만, 정렬이 되어있다면 이진 탐색을 수행 할 수 있다. 이진 탐색은 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 특징이 있다.

 

이진 탐색은 위치를 나타내는 변수 3개를 사용하는데, 탐색하고자 하는 범위의 시작점, 끝점, 중간점이다. 

 

아래 이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾는 예시를 보자.

 

전체 데이터의 갯수는 10개이지만, 이진 탐색을 이용해 총 3번의 탐색으로 원소를 찾을 수 있었다. 이진 탐색은 한번 확인 할때마다 확인하는 원소의 갯수가 반으로 줄어든다는 점에서 시간 복잡도가 O(logN)이다.

 

다음은 반복문으로 쓰여진 재귀함수 코드이다.

 

def bSearch(arr, target, start, end):
	while start <= end:
    	mid = (start + end) // 2
        # 찾은 경우 중간 인덱스 반환
        if arr[mid] == target
        	return mid
        # 중간값이 target보다 큰 경우 왼쪽 부분 탐색
        elif arr[mid] > target:
        	end = mid - 1
        #중간값이 target보다 작은 경우 오른쪽 부분 탐색
		else:
        	start = mid + 1
        return None

 

📌 트리 자료구조

트리 자료구조를 간단히 알아보자. 트리는 노드와 간선의 연결로 표현되며, 여기에서 노드는 어떤 정보를 담고 있는 객체 정도로 이해 할 수 있다. 트리 자료구조는 그래프 자료구조의 일종으로 데이터베이스 시스템이나 파일 시스템과 같은 곳에서 많은 양의 데이터를 관리하기 위해 사용된다. 트리 자료구조는 몇가지 중요한 특징이 있다.

 

• 트리는 부모-자식 노드간의 관계로 표현된다.
• 트리의 최상단 노드를 루트 노드라고 한다.
• 트리의 최하단 노드를 단말 노드(leaf node)라고 한다.
• 트리에서 일부를 떼어내도 트리 구조이며 이를 서브트리 라고 한다.
• 트리는 파일 시스템과 같이 계층적이고 정렬된 데이터를 다루기에 적합하다.

정리하면 큰 데이터베이스를 다루는 소프트웨어는 데이터를 트리 자료구조로 저장해서 이진 탐색과 같은 탐색 기법을 이용해 빠르게 탐색이 가능하다. 그렇다면 이런 트리 구조를 이용하면 어떤 방식으로 이진 탐색이 가능할까?

 

📌이진 탐색 트리(Binary Search Tree)

트리 자료구조 중에서 가장 간단한 형태가 이진 탐색 트리이다. 이진 탐색 트리란 이진 탐색이 동작 할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조이다. 

이진 탐색 트리는 다음과 같은 특징을 가진다.

 

• 부모 노드보다 왼쪽 자식노드가 작다.
• 부모 노드보다 오른쪽 자식 노드가 더 크다.

좀 더 간단하게 표현하면 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 

 

 

이처럼 이진 탐색 트리가 이미 구현되어 있다고 가정하고 다음 그림과 같은 이진 탐색 트리에서 데이터를 조회하는 과정만 살펴 보겠다. 다음은 찾는 원소가 37일때 동작하는 과정이다. 

 

이진 탐색 문제는 입력 데이터가 많거나, 탐색 범위가 매우 넓은 편이다. 예를들어 데이터의 갯수가 1,000개를 넘어 가거나 탐색 범위의 크기가 1,000억 이상이라면 이진 탐색 알고리즘을 의심 해보자. 하지만 이렇게 입력 데이터의 갯수가 많은 문제에 input()함수를 사용하면 동작 속도가 느려 시간 초과로 오답 판정을 받을 수 있다. 이처럼 입력 데이터가 많은 문제는 sys 라이브러리의 readline()함수를 이용하면 시간 초과를 피할 수 있다.

 

import sys
# 하나의 문자열 데이터를 입력받기
input_data = sys.stdin.readline().rstrip()

# 입력받은 문자열 그대로 출력
print(input_data)

 

sys 라이브러리를 사용할 때는 한 줄 입력받고 나서 rstrip() 함수를 꼭 호출해야 한다. 소스코드에 readline()으로 입력하면 입력 후 엔터Enter가 줄 바꿈 기호로 입력되는데, 이 공백 문자를 제거하려면 rstrip() 함수를 사용해야 한다. 코드가 짧으니, 관행적으로 외워서 사용하자.