이진 탐색 Binary Search

" 범위를 반씩 좁혀가는 탐색 "

순차 탐색 Sequential Search

- 리스트 내에서 특정한 데이터를  찾기 위해 앞에서부터 데이터를 하나씩 매우 빠르게 탐색하는 이진 탐색 알고리즘

- 예시) Greedy  '거스름돈' 문제에서 가장 큰 화폐 단위부터 확인(탐색)해서 각 단위에 대하여 처리한 것

- 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소(데이터)를 찾을 수 있다는 장점

<사용 예시>

- 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로 최악의 경우 시간복잡도 O(N)

- 리스트에 특정 값의 원소가 있는지 체크할 때 순차 탐색으로 원소를 확인하고, 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드를 이용할 때에도 내부에서는 순차 탐색이 수행됨

def sequential_search(n, target, array):
    
    for i in range(n):

        if array[i] == target:
            return i + 1

input_data = input().split()
n = int(input_data[0])
target = input_data[1]

array = input().split()
print(array)
print(sequential_search(n, target, array))

# input
# 생성할 원소 개수와 찾고자 하는 문자열
5 apple
banana orange apple melon watermelon 

# output
# 문자열 위치(몇 번째에 있는지)
3

 

이진 탐색 Binary Search

범위 내에서 조건을 만족하는 가장 큰 값을 찾으라는 최적화 문제라면 이진 탐색으로 결정 문제를 해결하면서
범위를 좁혀갈 수 있다.(= 파라메트릭 서치 Parametric Search)

<입력조건> 자세히 보기
- 수 가 굉장히 큰 범위라면 "이진 탐색을 먼저 떠올려야한다.

 

- 반으로 쪼개면서 탐색하기

- 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘

- 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다는 특징이 있다.

- 이진 탐색은 변수를 3개를 사용(= 시작점, 끝점, 중간점)

- 찾으려는 데이터와 중간점 Middle 위치에 데이터를 반복적으로 비교

- 폭넓게 적용되는 원리와 유사하기 때문에 매우 중요하고 단골 문제이니 가급적 외우길

- 시간복잡도 O(logN)

# 재귀함수 활용

def binary_search(array, target, start, end):
    if start > end:
        return None

    mid = (start + end) // 2

    # 중간점이 찾고자 하는 값과 같을 경우 해당 값 출력
    if array[mid] == target:
        return mid
    
    # 중간점의 값보다 찾고자 하는 값이 작은 경우 
    # 끝점을 중간점 - 1 이동
    elif array[mid] > target:
        return binary_search(array, target, start, mid - 1)

    # 중간점의 값보다 찾고자 하는 값이 큰 경우
    # 시작점을 중간점 + 1 이동
    else:
        return binary_search(array, target, mid + 1, end)

num, target = map(int, input().split())  

array1 = list(map(int, input().split()))

res = binary_search(array1, target, 0, n-1)

if res == None:
    print("원소가 존재하지 않습니다")

else:
    print(res+1)

# 단순하게 반복문 사용
def binary_search(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2

        # 중간점이 찾고자 하는 값과 같을 경우 해당 값 출력
        if array[mid] == target:
            return mid
        
        # 중간점의 값보다 찾고자 하는 값이 작은 경우 
        # 끝점을 중간점 - 1 이동
        elif array[mid] > target:
            end = mid - 1

        # 중간점의 값보다 찾고자 하는 값이 큰 경우
        # 시작점을 중간점 + 1 이동
        else:
            start = mid + 1

    return None 

num, target = map(int, input().split())  

array1 = list(map(int, input().split()))

res = binary_search(array1, target, 0, n-1)

if res == None:
    print("원소가 존재하지 않습니다")

else:
    print(res+1)

1. array 정렬
2. 끝점이 시작점보다 크면(=인덱스) None
3. mid 값 설정(= start+end // 2)
4. 조건 부여
    array 중간점(=인덱스) == target, return
    array 중간점 > target, return end = mid - 1 or 재귀함수 인자에 적용
    array 중간점 < target, return start = mid + 1 or 재귀함수 인자에 적용

트리 자료구조

" 노드와 노드의 연결로 표현하며 여기에서 노드는 정보의 단위로서 어떠한 정보를 가지고 있는 개체로 이해할 수 있다 "

- 이진 탐색은 전제 조건이 데이터 정렬

- DB는 내부적으로 대용량 데이터 처리에 적합한 트리 자료구조를 이용하여 항상 데이터가 정렬되어 있다.

- 이진 탐색과 조금 다르지만, 유사한 방법을 이용해 탐색을 항상 빠르게 수행하도록 설계되어 있어서 데이터가 많아도 탐색하는 속도가 빠르다.

- 그래프 자료구조의 일종으로 DB 시스템이나 파일 시스템 같은 곳에서 많은 양의 데이터를 관리하기 위한 목적으로 사용한다.

<특징>

- 트리는 부모 노드와 자식 노드의 관계로 표현된다(노드 = "도시"와 같은 정점의 의미)

- 트리의 최상단 노드를 "루트 노드"

- 트리의 최하단 노드를 "단말 노드"

- 트리에서 일부를 떼어내도 트리 구조이며 이를 "서브 트리"라고 한다.

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

큰 데이터를 처리하는 SW는 대부분 데이터를 트리 자료구조로 저장해서 이진 탐색과 같은 탐색 기법을 이용해 빠르게 탐색한다.

How??? 이런 트리 구조를 이용하면 어떤 방식으로 이진 탐색이 가능한가

이진 탐색 트리

" 이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조 "

- 트리 자료구조 중에서 가장 간단한 형태

- 크기가 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드가 성립해야지 이진 탐색 트리라 할 수 있다.

= 시작점, 중간점, 끝점을 설정하는 것과 비슷함

 

<이미 정렬되어 있을 때>
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

1. 중간값 4
2. 중간값 기준으로 왼쪽은 작은 값, 오른쪽은 큰 값인 두 그룹으로 나눠짐

왼쪽 = [0, 1, 2, 3]
오른쪽 = [5, 6, 7, 8, 9]

3. 왼쪽에서 중간값 출력 1(= 중간값[4]보다 작으니까 트리에서 왼쪽)
	다시 왼쪽에서 중간값인 1을 기준으로 왼쪽[0], 오른쪽[2, 3] 나눔
    	작은쪽은 데이터가 하나이기 때문에 중간값은 0이됨
        	
        	오른쪽 그룹 [2, 3]에서 중간값[2] 기준으로 왼쪽[2], 오른쪽[3] 나눔
            (= 왼쪽[2]는 1의 중간값의 그룹이니까 1에 붙여줌(오른쪽으로)
            	(= 오른쪽[3]의 중간값은 3이니까 2에 붙여줌(오른쪽으로)
        

4. 오른쪽에서 중간값 출력 7(= 중간값[4]보다 크니까 트리에서 오른쪽)
	이하 같음
    
## 이진 트리 구조
		4
            /  	    \
        1		7
      /   \           /   \
    0	   2	   5	    8
    	      \       \       \
                3      6        9

https://www.youtube.com/watch?v=9ZZbA2iPjtM참조