이진탐색 .in Python [백준 5639]

---

이진 탐색

• 순차 탐색 : 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서 부터 데이터를 하나씩 확인 하는 방법
• 이진 탐색 : 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법 (이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정한다.)

---

1. 이진 탐색 알고리즘

이미 정렬된 10개의 데이터 중에서 값이 4인 원소를 찾는 예시

 

1. 시작점: 0, 끝점: 9 , 중간점: 4 (소수점 이하 제거)
2. 중간점인덱스와 타겟 인덱스를 비교 (중간점:4, 타겟:2)
3.  중간점 > 타겟이므로 끝점 = 중간점 - 1
4. 시작점: 0, 끝점: 3, 중간점: 1
5. 중간점인덱스와 타겟인덱스를 비교 (중간점:1, 타겟:2)
6. 중간점 < 타겟이므로 시작점 = 중간점 + 1
7. 시작점:2, 끝점:3, 중간점: 2
8. 중간점인덱스와 타겟인덱스를 비교 (중간점:1, 타겟:2)
9. 중간점인덱스랑 타겟인덱스가 같으므로  Index 2 = 4

---

• 단계마다 탐색 범위를 2로 나누는 것과 동일하므로 연산횟수는 log_2N에 비례한다.
• 예를 들어 초기 데이터 개수가 32개일때, 이상적으로 1단계를 거치면 16개가량의 데이터만 남는다.
• 시간복잡도는 O(logN)을 보장한다.

---

2. 이진 탐색 코드 (재귀 함수)

def binary_search(array, target, start, end):
    if end < start:
        return None
    mid = start + end // 2

    if array[mid] == target:
        return mid
    
    elif array[mid] > target:
        return binary_search(array, target, start, mid-1)
    elif array[mid] < target:
        return binary_search(array, target, mid+1, end)
    
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)

 

---

3. 이진 탐색 코드 (반복문)

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 = 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)

 

---

[백준] 5639번 이진 검색 트리

    문제

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.
노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.
이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

 

    입력

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 10^6 보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.

 

    출력

입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

 

---

문제 풀이

 

1. 이 문제의 조건이 왼쪽 서브트리보다 오른쪽 서브트리 값이 무조건 크다는 조건을 이용하여 이진 탐색을 실시한다.
2. 전위 순회에서의 맨 앞쪽 값을 mid로 잡고 mid보다 작은값까지, 그 이외의 값으로 나눈다.
3. 후위순회가 (왼쪽-오른쪽-루트) 이기때문에 왼쪽 부터 탐색한다.
4. 재귀 함수를 이용하여 넘겨주는 array가 0일때 return 하여 출력한다. 

---

전체 코드

nodes = []
while True:
    try:
        nodes.append(int(input()))
    except:
        break

def binary_tree(arr):

    if len(arr) == 0:
        return
    
    left, right = [], []
    mid = arr[0]

    for i in range(len(arr)):
        if arr[i] > mid:
            left = arr[1:i]
            right = arr[i:]
            break
        else:
            left = arr[1:]

    binary_tree(left)
    binary_tree(right)
    print(mid)
    
binary_tree(nodes)