탐색

1. 순차탐색

- 리스트 내 특정 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 확인하는 방법

- O(N)

 

2. 이진탐색

- 찾으려는 데이터와 중간 위치 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 방법

- 배열 내 데이터들이 정렬되어있어야 한다.

- 확인하는 데이터의 개수가 절반씩 줄어든다는 점에서 O(logN)

- 입력 데이터가 2000만을 넘어가면 이진 탐색으로 접근해보기

def binary_search (array,target,start,end):
	if start > end:
    	return None
    mid = int((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)

def binary_search(array,target,start,end):
	while start<=end:
    	mid = int((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개의 부품이 있고 각 부품은 고유 번호가 있다.부품 M개를 입력받았을 때, 해당 M개의 부품이 모두 있는지 확인하는 프로그램을 작성하라.( 있으면 yes,없으면 no)

 

#풀이1 : 이진탐색
def binary_search( array,target,start,end):
	while start<=end:
    	mid = int( (start+end) // 2)
        if array[mid] == target:
        	return mid
        elif array[mid] > target:
        	end = mid -1
        else:
        	start = mid + 1
    return None

N = int(input())
array = list(map(int,input().split()))
array.sort()

m = int(input())
search_target = list(map(int,input().split()))

for i in search_target:
	result = binary_search(array,i,0,n-1)
    if result != None:
    	print('yes', end = ' ')
    else:
    	print('no', end = ' ' )

 

#방법2 : 계수 정렬
n = int(input())
array = [0] * 10000001

for i in input().split():
	array[int(i)] = 1

m = int(input())
target_list = list(map(int,input().split()))

for i in target_list:
	if array[i] == 1:
    	print('yes',end = ' ')
    else:
    	print('no',end = ' ')

#방법 3 : set()
n = int(input())
array = set(map(int,input().split())

m = int(input())
target_list = list(map(int,input().split()))

for i in target_list:
	if i in array:
    	print('yes',end = ' ')
    else:
    	print('no', end = ' ')

 

 * 예제2)

  길이가 각기 다른 떡 M개가 주어지고, 절단기에 높이 H를 지정하면 해당 떡들을 한번에 절단한다. 높이가 H보다 긴 떡들은 H위의 부분이 잘리고 낮은 떡은 잘리지 않을 때, 손님은 높이가 H위의 부분을 가져갈 수 있다. 손님이 요청한 총 길이가 M일 때, 적어도 M 만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 H의 최댓값은?

 

 

 

2-2. 트리 자료구조

- 트리 : 노드와 노드의 연결인 link로 표현된 자료구조. 대용량 데이터 처리에 적합하며, 탐색 속도가 빠르다.

- 트리 속성:

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

  2) 트리의 최상단 노드를 루트 노드라고 한다.

  3) 트리의 최하단 노드를 단말 노드라고 한다.

  4) 트리에서 일부를 떼어내도 트리 구조이며, 이를 서브 트리라 한다.

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