탐색 (순차, 이진)

이진 탐색을 이해하기 위해서는 순차 탐색을 먼저 살펴볼 필요가 있다. 

N 개의 데이터가 있을 때 데이터를 차례대로 하나씩 확인하는 그 자체가 바로 순차 탐색이다. 

 

순차탐색 

리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드를 이용할 때도 내부에서는 순차 탐색이 수행된다. 

 

import sys 
input = sys.stdin.readline

array = [1,2,3,4,5,1,2,3,1,2,1,2,3,45,56,1,32,4,14,21,41,5,14,124,12341,1,1,213,1,2,3,4,1,2,3,1,1,1,2,3,1,2,3]

N = int(input())

cnt = 0

for i in array:
    if i == N:
        cnt += 1 

print(cnt)

 

주어진 array 에서 특정 원소를 찾는 방법이다. 

 

이진 탐색 

이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다. 

탐색 범위를 절반 씩 좁혀가며 데이터를 탐색하는 특징이 있다. 

 

이진 탐색은 변수 3개를 사용한다. 

1) 시작점 

2) 끝점 

3) 중간점 이다. 

 

찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 것이 이진 탐색 과정이다. 

 

import sys 
input = sys.stdin.readline

array = [0,2,4,6,8,10,12,14,16,18]

#내가 햇갈리는 부분 그냥 index 를 넘기면 array에 접근이 어렵지 않다. 
#array를 짤라야한다는 고정관념을 버리자. 

target = int(input())


def binary_search(start, end, array, target):
    ############ 못찾는 경우 
    if start > end: 
        return None
    #####################
    mid = (start+end)//2
    if target == array[mid]:
        return mid 
    if target < array[mid]: 
        end = mid-1
        binary_search(start,end,array,target) 
    else: 
        start = mid+1 
        binary_search(start,end,array,target)


print(binary_search(0, len(array)-1, array, target))

while 문으로도 구할 수 있다. 

while(start <= end):

즉 , 못찾거나 찾을 때까지 돌아라. 

 

※ 비슷한 유형 매번 실수하는 부분 

array 를 반 쪼개서 넘겨줄 생각을 하다보니 그때 index 를 초기화하려고한다. 

array를 그대로 넘겨주면 index 를 초기화할 염려가 없다. 

global 변수인 array를 그냥 넘겨준다는 것이 어색해서 자꾸 다른 처리를 하려고 하는데, 사실 상관 없다. 

 

존 벤틀리에 따르면 이진 탐색 코드를 작성할 수 있는 프로그래머가 10% 내외라고 했다. 

약 5년전 처음 이진 탐색을 배울때만 해도 지식의 공유가 지금처럼 되지 않아 납득이 잘 갔는데, 지금 한국 코더들에게 이진탐색을 구현하라고 하면 약 95%는 구현이 가능할 것 같다. 

그럼에도 처음 배울 때랑 변화가 있다면 지식을 받아들일 때 세부 디테일이 머리속에 들어오느냐 안들어오느냐 차이가 있는 것 같다. 

 

트리 자료구조

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

동작하는 프로그램에서 데이터를 정렬해두는 경우가 많으므로 이진 탐색을 효과적으로 사용할 수 있다. 

 

데이터베이스는 내부적으로 대용량 데이터 처리에 적합한 트리 자료구조를 항상 이용하여 데이터를 정렬한다. 

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

 

트리 자료 구조는 몇가지 주요한 특징이 있다. 

사진 출처: https://blog.geusan.com/32

 

트리의 특징 

• 트리는 부모 노드와 자식 노드의 관계로 표현된다. 
• 트리의 최상단 노드를 루트 노드라 한다. 
• 트리의 최하단 노드를 단말 노드라 한다. 
• 트리에서 일부를 떼어내도 트리 구조이며 이를 서브 트리라 한다. 
• 트리는 파일 시스템과 같이 계층적이고 정렬된 데이터를 다루기에 적합하다. 

이진 탐색 트리 

트리 자료구조 중에서 가장 간단한 형태가 이진 탐색 트리 

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

모든 트리가 다 이진 탐색 트리는 아니다. 

 

이진 탐색 트리 특징 

• 부모 노드보다 왼쪽 노드가 작다.
• 부모 노드보다 오른쪽 자식 노드가 크다. 

즉, 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드 

 

이진 탐색 트리에 데이터를 넣고 빼는 방법은 알고리즘보다는 자료구조에 가깝고 자료구조를 구현하도록 요구하는 문제는 출제 빈도가 낮다. 

※ 처음 이진 탐색 트리를 배울 때는 왜 왼쪽 자식 노드가 더 낮은 수를 갖고 오른쪽 자식 노드가 더 높은 수를 갖는지 전체적인 구조로 이해를 하지는 못했다. 당시는 트리 구조의 필요성에 대해 공감하지 못하고 학문적으로 접근하다보니 이해를 깊게 하지 못한 것 같다. 

 

아래는 예제 

1) 부품 찾기 

전자 매장에 부품이 N 개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. M 개 종류의 부품을 대량 구매하려고 한다. 부품 M 개 종류를 모두 가지고 있는지 확인해보자. 

입력: 

N
array of N 
M 
array of M

출력: 

해당 물품이 있으면 yes, 없으면 no 로 출력 

import sys 
input = sys.stdin.readline

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

M = int(input())
arrayM = list(map(int,input().split()))

def binary_search(start,end,array,target):
    mid = (start+end) // 2
    if start > end:
        return False
    if target == array[mid]: 
        return True
    if target < array[mid]:
        end = mid - 1
        return binary_search(start, end, array, target)
    else:
        start = mid + 1
        return binary_search(start, end, array, target)


for i in arrayM:
    if not binary_search(0, len(arrayN)-1, arrayN, i):
        print("no", end = ' ')
    else:
        print("yes", end = ' ')

 

※ 유의점 

return binary_search()

recursive 에서 함수를 return 해주지 않으면 return None 이 되는 경우가 종종 존재 

 

또한 위 문제는 계수 정렬로 풀 수도 있다. 

첫번째 input 으로 array 1 표시, 두번째 input 으로 array 검사 중 1로 표시되어 있나 확인 

 

 

꼭 binary search 여야 할까? 

그냥 element in list 로 풀면 어떨까? 

 

다음의 이슈가 있다. 

 

The binary search is going so fast that when you try to print the time it took, it just prints 0.0. Whereas using in takes long enough that you see the very small fraction of a second it took.

The reason that in does take longer is because this is a list, not a set or similar data structure; whereas with a set, membership testing is somewhere between O(1) and O(logn), in a list, every element has to be checked in order until there's a match, or the list is exhausted.

즉, in 을 할꺼면 list 보다 set 이 빠르다. 

https://stackoverflow.com/questions/7571635/fastest-way-to-check-if-a-value-exists-in-a-list

속도 비교 그래프이다.

 

하지만 이와 같은 글도 있다. 

 

constructing that set from your list may take more time than faster membership testing will save

list 에서 set 을 만드는 과정이 더 시간이 오래걸릴 수도 있다고 한다. 

애초에 데이터를 받아올 때 list 화 하지말고 set 화 해서 받아오는 것이 가장 빠른 방법일 것 같다. 

 

2) 떡볶이 떡 만들기 

떡을 일정하지 않은 길이로 자르려 한다. 다만, 한 봉지 안에 들어가는 떡의 총 길이는 동일하게 맞춘다. 

 

높이 H 를 지정하면 높이가 H 보다 긴 떡은 H 위의 부분이 잘리고, 낮은 떡은 잘리지 않는다. 

 

예를들어 높이가 19, 14, 10, 17 이고 15 높이로 자르면, 15, 14, 10, 15 가 되고 잘린 떡의 길이는 4, 0, 0, 2 이다. 

남은 떡 6 길이의 떡을 가져가고자 한다. 

 

만약 적어도 M 길이의 떡을 가져가고자 하면, 최대로 설정할 수 있는 높이는 몇인가? 

 

입력:

N M (4 6)

array (19 15 10 17)

 

출력:  

최대 길이 (15)

 

import sys 
input = sys.stdin.readline

N, M = map(int, input().split())
array = list(map(int,input().split()))
start = 0 
end = max(array)

target = M

def binary_search(start, end, array, target, result):
    mid = (start+end) // 2

    length = 0 
    if start > end:
        return result
    for i in array:
        if i > mid:
            length += (i - mid)

    if length == target: 
        return mid 
    if length < target:
        end = mid -1 
        return binary_search(start, end, array, target, result)
    else:
        print(mid)
        result = mid 
        start = mid + 1
        return binary_search(start, end, array, target, result)

print(binary_search(0, end, array, target, 0))

몇가지 실수로 오래시간 고민을 했다. 

첫번 째, 문제에서 자르는 길이보다 짧은 떡은 잘리지 않는다고 분명히 나와있는데 구현에서는 해당 부분을 반영하지 않았다. 

두번 째, 종료조건 

start > end: return

 에 대하여 지금과 같이 탐색해서 해당 해를 찾는 것이 아니라 최대한 가까운 값을 구할 때도 사용 가능한 것임이 직관적으로 바로 이해되지 않았다. 

예전에 해당 문제를 학습할 때 자세히 보지 않고 넘어갔기 때문이다. 

정리하자면, 탐색을 반복하며 찾는 값에 해당 하는 값이 없어도 점점 더 최대한 가까운 값에 다가가고, 결국 찾지 못하면 return을 하게 되는데, 이 때 찾는 과정에서 찾는 값에 가장 가까우며 작은 값 과 가장 가까우며 큰 값을 찾는 것이 가능하다.