Python 79 - 이진탐색 (2)

이진 탐색 트리

트리 자료구조 중에서 가장 간단한 형태가 이진 탐색 트리이다. 이진 탐색 트리란 이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조이다. 이진 탐색 트리를 설명하는 동안 코드를 배제할 테니 편하게 다음그림을 보자.

보통 이진 탐색 트리는 이 그림과 같은데 모든 트리가 다 이진 탐색 트리는 아니며, 이진 탐색 트리는 다음과 같은 특징을 가진다.

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

그림에서 루트를 포함한 일부만 다시 살펴보자.

좀 더 간단하게 표현하면 왼쪽 자식 노드 < 부모노드 < 오른쪽 자식 노드가 성립해야지 이진 탐색 트리라 할 수 있다. 그림에도 17 < 30 < 48 로 성립한다는 걸 알 수 있다.

이진 탐색 트리에 데이터를 넣고 빼는 방법은 알고리즘보다는 자료구조에 가까우며, 이진 탐색 트리 자료구조를 구현하도록 요구하는 문제는 출제 빈도가 낮으므로, 이 책에서는 이진 탐색 트리를 구현하는 방법은 소개하지는 않는다.

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

이진 탐색 트리에서 데이터 조회는 동작 원리만 살펴보면 간단하게 느껴진다. 공식에 따라 루트 노드부터 왼쪽 자식 노드 혹은 오른쪽 자식 노드로 이동하며 반복적으로 방문한다. 자식 노드가 없을 때까지 원소를 찾지 못했다면, 이진 탐색 트리에 원소가 없는 것이다. 짧게 3단계로 살펴봤지만 아무리 노드가 많아도 이진 탐색 트리는 이 과정을 반복하는 것에 불과하니 위의 과정 그림을 이해하면 충분하다.

빠르게 입력받기

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

때로는 코딩 테스트 출제자가 아예 sys 라이브러리를 사용하기를 권고하는 문장을 문제에 적어 놓기도 한다. sys 라이브러리는 다음과 같은 방식으로 사용하며 한 줄씩 입력받는다.

한 줄 입력받아 출력하는 소스코드

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

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

입력값 : Hello, Coding Test!
출력값 : Hello, Coding Test!

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

코드가 짧으니, 관향적으로 외워서 사용하자. 

 

---

본 포스팅은 ‘이것이 코딩 테스트다 with 파이썬’을 읽고 공부한 내용을 바탕으로 작성하였습니다.

 

 

 

작성자 : 엄코딩 eomcoding