[이것이 코딩테스트다 with 파이썬] 이진탐색

최근 보고 있는 책인  '이것이 코딩테스트다 with 파이썬 편_나동빈_한빛미디어' 책을 읽으면서 정리하고자 한다.

www.hanbit.co.kr/store/books/look.php?p_code=B8945183661

이것이 취업을 위한 코딩 테스트다 with 파이썬

 

이는 글로 간단하게 작성한 것인데, 책에 보면 그림과 함께 매우 상세한 설명이 적혀있다 !!

 

순차탐색

리스트 안에 잇는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다. 

리스트에서 특정 값의 원소가 있는지 확인할 때에도 순차 탐색으로 원소를 확인하고, 리스트에서 특정 값을 가지는 원소의 개수를 세는 count() 메서드를 사용할 때에도 순차탐색이 이용된다.

데이터의 개수가 N개 일때 최대 N개를 뒤져봐야하므로 시간 복잡도는 O(N) 이다.

# 순차 탐색 소스코드 구현
def sequential_search(n, target, array):
	# 각 원소를 하나씩 확인하며
    for i in range(n) :
    	# 현재의 원소가 찾고자 하는 원소와 동일한 경우
        if array[i] == target:
        	return i+1	# 현재의 위치 반환 (인덱스는 0부터 시작하므로 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))

 

이진탐색

정렬된 데이터에서만 사용이 가능하고, 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 찾아내려는 것이다. 

1. 시작접과 끝점을 통해 중간점(소수점 이하 버림)을 찾아낸다.

2. 중간점과 찾으려는 데이터를 비교한다.

3-1. 중간점보다 찾으려는 데이터가 큰 경우 : 시작점을 (중간점+1)로 설정하여 다시 시작점과 끝점과 찾으려는 데이터를 파라미터로 하여 이 함수를 실행한다.

3-2. 중간점보다 찾으려는 데이터가  작은 경우 : 끝점을 (중간점 -1 )로 설정하여 다시 시작점과 끝점과 찾으려는 데이터를 파라미터로 하여 이 함수를 실행한다.

3-3. 중간점과 찾는 데이터가 같은 경우 : 탐색종료

 

찾는 원소의 개수가 절반씩 줄어들기 때문에 시간복잡도가 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)

 

트리 자료구조

데이터베이스 : 내부적으로 대용량 데이터 처리에 적합한 트리 자료구조로 데이터가 정렬되어있다.

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

 

 

 

이진 탐색 트리

이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 구조이다.

(특징)

 1. 부모 노드보다 왼쪽 자식 노드가 작다.

 2. 부모 노드 보다 오른족 자식 노드가 크다.

 

 

 

 

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

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