📖 순차 탐색(Sequential Search)
- 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법
- 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용
- 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소(데이터)를 찾을 수 있다는 장점이 있음
- 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로 최악의 경우 순차 탐색의 시간 복잡도는 O(N)임
✏️ 7-1.py 순차 탐색 소스코드
# 순차 탐색 소스코드 구현
def sequential_search(n, target, array):
# 각 원소를 하나씩 확인하며
for i in range(n):
# 현재 원소가 찾고자 하는 원소와 동일한 경우
if array[i] == target :
# 현재의 위치 반환(인덱스는 0부터 시작하므로 1 더하기)
return i + 1
print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.")
input_data = input().split()
# 원소의 개수
n = int(input_data[0])
# 찾고자 하는 문자열
target = input_data[1]
print("앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.")
array = input().split()
# 순차 탐색 수행 결과 출력
print(sequential_search(n, target, array))생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요. 5 Dongbin↵ 앞서 적은 원소 개수만큼 문자열을 입력하세요, 구분은 띄어쓰기 한 칸으로 합니다. Hanul Jonggu Dongbin Taeil Sangwook↵ 3
📖 이진 탐색(Binary Search)
- 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘
- 데이터가 무작위일 때는 사용할 수 없음
- 그러나 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다는 특징이 있음
- 탐색 범위를 절반씩 좁혀가며 데이터를 탐색한다는 특징이 있음
- 이진 탐색은 위치를 나타내는 변수 3개를 사용 : 탐색하고자 하는 범위의 시작점, 끝점, 그리고 중간점
- 찾으려는 데이터와 중간점(Middle) 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 게 이진 탐색 과정
- 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다는 점에서 시간 복잡도가 O(logN)임
✏️ 7-2.py 재귀 함수로 구현한 이진 탐색 소스코드
# 이진 탐색 소스코드 구현(재귀 함수)
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(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)10 7↵ 1 3 5 7 9 11 13 15 17 19↵ 4 10 7↵ 1 3 5 6 9 11 13 15 17 19↵ 원소가 존재하지 않습니다.
✏️ 7-3.py 반복문으로 구현한 이진 탐색 소스코드
# 이진 탐색 소스코드 구현(반복문)
def binary_search(arrat, 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만을 넘어가면 이진 탐색으로 문제에 접근해보길 권함
- 처리해야 할 데이터의 개수나 값이 1,000만 단위 이상으로 넘어가면 이진 탐색과 같이 O(logN)의 속도를 내야 하는 알고리즘을 떠올려야 문제를 풀 수 있는 경우가 많다는 점을 기억해야함
📖 트리 자료구조
- 트리 자료구조는 노드와 노드의 연결로 표현하며 여기에서 노드는 정보의 단위로서 어떠한 정보를 가지고 있는 개체로 이해할 수 있음
- 트리 자료 구조는 그래프 자료구조의 일종으로 데이터베이스 시스템이나 파일 시스템과 같은 곳에서 많은 양의 데이터를 관리하기 위한 목적으로 사용
- 트리 자료구조는 몇 가지 주요한 특징이 있음
- 트리는 부모 노드와 자식 노드의 관계로 표현됨
- 트리의 최상단 노드를 루트 노드라고 함
- 트리의 최하단 노드를 단말 노드라고 함
- 트리에서 일부를 떼어내도 트리 구조이며 이를 서브 트리라 함
- 트리는 파일 시스템과 같이 계층적이고 정렬된 데이터를 다루기에 적합
- 큰 데이터를 처리하는 소프트 웨어는 대부분 데이터를 트리 자료구조로 저장해서 이진 탐색과 같은 탐색 기법을 이용해 빠르게 탐색이 가능함
📖 이진 탐색 트리
- 트리 자료구조 중에서 가장 간단한 형태가 이진 탐색 트리
- 이진 탐색 트리란 이진 탐색이 동작할 수 있도록 고안된, 효율적이 탐색이 가능한 자료구조임
- 이진 탐색 트리는 다음과 같은 특징을 가짐
- 부모 노드보다 왼쪽 자식 노드가 작음
- 부모 노드보다 오른쪽 자식 노드가 큼
- 간단하게 표현하면 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드가 성립해야 이진 탐색 트리라 할 수 있음
- 이진 탐색 트리에서의 데이터 조회 방법은 공식에 따라 루트 노드부터 왼쪽 자식 노드 혹은 오른쪽 자식 노드로 이동하며 반복적으로 방문하는 것임
- 자식 노드가 없을 때까지 원소를 찾지 못했다면, 이진 탐색 트리에 원소가 없는 것임
📖 빠르게 입력 받기
- 이진 탐색 문제는 입력 데이터가 많거나, 탐색 범위가 매우 넓은 편임
- 그런데 이렇게 입력 데이터의 개수가 많은 문제에서
input()함수를 사용하면 동작 속도가 느려서 시간 초과로 오답 판정을 받을 수 있음 - 이처럼 입력 데이터가 많은 문제는
sys라이브러리의readline()함수를 이용하면 시간 초과를 피할 수 있음 sys라이브러리를 사용할 때는 한 줄 입력받고 나서rstrip()함수를 꼭 호출해야 함- 소스코드에
readline()으로 입력하면 입력 후 엔터가 줄 바꿈 기호로 입력되는데, 이 공백 문자를 제거하려면rstrip()함수를 사용해야 함
- 소스코드에
✏️ 7-4.py 한 줄 입력받아 출력하는 소스코드
import sys
# 하나의 문자열 데이터 입력받기
input_data = sys.stdin.readline().rstrip()
# 입력받은 문자열 그대로 출력
print(input_data)Hello, Coding Test!↵ Hello, Coding Test!
📖 bisect
- 파이썬에서는 이진 탐색을 쉽게 구현할 수 있도록
bisect라이브러리를 제공함 bisect라이브러리는 '정렬된 배열'에서 특정한 원소를 찾아야 할 때 매우 효과적으로 사용됨bisect라이브러리에서는bisect_left()함수와bisect_right()함수가 가장 중요하게 사용되며, 이 두 함수는 시간 복잡도 O(logN)에 동작함bisect_left(): 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 왼쪽 인덱스를 찾는 메서드bisect_right(): 정렬된 순서를 유지하도록 리스트a에 데이터x를 삽입할 가장 오른쪽 인덱스를 찾는 메서드
✏️ bisect_example-1.py
from bisect import bisect_left, bisect_right
a = [1, 2, 4, 4, 8]
x = 4
print(bisect_left(a,x))
print(bisect_right(a,x))2 4
- 아래의
count_by_range(a, left_value, right_value)함수는 정렬된 리스트에서 [left_value,right_value]에 속하는 데이터의 개수를 반환하는 함수임 - 원소의 값을
x라고 할 때,left_value<=x<=right_value인 원소의 개수를 O(logN)으로 빠르게 계산할 수 있음
✏️ bisect_example-2.py
from bisect import bisect_left, bisect_right
# 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
def count_by_range(a, left_value, right_value):
right_index = bisect_right(a, right_value)
left_index = bisect_left(a, left_value)
return right_index - left_index
# 리스트 선언
a = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9]
# 값이 4인 데이터 개수 출력
print(count_by_range(a, 4, 4))
# 값이 [-1, 3] 범위에 있는 데이터 개수 출력
print(count_by_range(a, -1, 3))2 6
AI를 공부하고 있는 학생입니다:)