[이것이 코딩테스트다] 15일차 - 순차탐색, 이진탐색, 트리자료구조

[이것이 코딩테스트다] 15일차 - 순차탐색, 이진탐색, 트리자료구조

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다.

Chapter 7 이진탐색

이진탐색을 학습하기 전, 순차탐색을 먼저 알아야한다.

순차탐색

리스트안에 있는 요소들을 하나씩 탐색하여 특정한 데이터를 찾는 탐색 방법

구현이 간단하고 자주 사용되는 탐색법이다. (파이썬 내장함수 count()도 순차탐색 방법 사용)

data = [1,2,3,4,5,6,7,8,9] target = 3 def sequential_search(data, target): for i in range (len(data)): if data[i] == target : return i+1

순차탐색은 정렬과 관계없이 가장 앞의 원소부터 하나씩 확인하는 과정을 거치는 특징이 있다.

순차탐색의 시간 복잡도는 최악의 경우 O(N)이다

이진탐색

배열 내부의 데이터가 래덤하지 않고 정렬되어 있어야만 사용할 수 있는 탐색방법

절반씩 데이터를 나누어 탐색하므로 매우 빠르게 요소를 찾아낼 수 있다는 장점을 가진다

총 3개의 변수를 사용한다

- 시작점

- 끝점

- 중간점

탐색하고자 하는 범위의 시작점과 끝점을 기준으로 중간점을 구하고 중간점과 target을 비교하며 target의 위치를 찾아간다.

target이 중간점보다 작을때 (왼쪽에 위치할때) 끝점의 위치를 중간점-1 으로 옮기고, 중간점 다시 계산

target이 중간점보다 클때 (오른쪽에 위치할때) 시작점의 위치를 중간점+1 으로 옮기고, 중간점 다시 계산

전체 데이터의 개수는 N이지만 한 번 확인할 때마다 확인하는 원소가 절반으로 줄어들기 때문에 시간복잡도는 O(logN)이다.

이진탐색은 재귀함수나 반복문을 이용하여 구현할 수 있다.

# 이진 탐색 소스코드 구현 (재귀 함수) def binary_search(array, target, start, end): if start > end: return None mid = (start + end) // 2 # 찾은 경우 중간점 인덱스 반환 if array[mid] == target: return mid # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인 elif array[mid] > target: return binary_search(array, target, start, mid - 1) # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인 else: return binary_search(array, target, mid + 1, end) # n(원소의 개수)과 target(찾고자 하는 값)을 입력 받기 n, target = list(map(int, input().split())) # 전체 원소 입력 받기 array = list(map(int, input().split())) # 이진 탐색 수행 결과 출력 result = binary_search(array, target, 0, n - 1) if result == None: print("원소가 존재하지 않습니다.") else: print(result + 1)

# 이진 탐색 소스코드 구현 (반복문) def binary_search(array, target, start, end): while start <= end: mid = (start + end) // 2 # 찾은 경우 중간점 인덱스 반환 if array[mid] == target: return mid # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인 elif array[mid] > target: end = mid - 1 # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인 else: start = mid + 1 return None # n(원소의 개수)과 target(찾고자 하는 값)을 입력 받기 n, target = list(map(int, input().split())) # 전체 원소 입력 받기 array = list(map(int, input().split())) # 이진 탐색 수행 결과 출력 result = binary_search(array, target, 0, n - 1) if result == None: print("원소가 존재하지 않습니다.") else: print(result + 1)

이진탐색은 코디테스트에서 단골로 나오는 알고리즘이기 때문에 구현 방법을 외우는것이 좋다

탐색범위가 2,000만을 넘어가면 O(logN)의 속도를 가진 이진탐색을 이용하는것이 좋다

트리자료구조

이진탐색은 데이터 정렬이 전제 조건으로 동작하는 프로그램에서는 데이터가 정렬되어 있는 경우가 많으므로 이진탐색을 효과적으로 사용할 수 있다.

데이터베이스는 내부적으로 대용량 데이터 처리에 적합한 트리(Tree)구조를 이용하여 정렬되어 있다.

데이터베이스의 탐색은 이진탐색과는 조금 다르지만 유사한 방법을 이용해 데이터를 탐색하도록 설계되어 있어 탐색 속도가 빠르다

트리자료구조

트리자료구조는 노드와 노드의 연결로 표현하며 노드는 어떠한 정보를 담고 있는 개체로 이해할 수 있다.

트리는 다음과 같은 특징이 있다

1. 트리는 부모노드와 자식노드의 관계로 표현된다

2. 트리의 최상단 노드 = 투르노드 / 트리의 최하단 노드 = 단말노드

3. 트리의 일부를 떼어내도 트리구조이다 (서브트리)

4. 파일시스템과 같이 계층적이고 정렬된 데이터를 다루는데 적합하다

이진 탐색 트리

이진탐색이 가능하도록 고안된 자료구조

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

1. 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

이진탐색트리 조회 과정

from http://gammistory.tistory.com/28 by ccl(A) rewrite - 2021-12-18 04:01:20