[Python] 탐색(Search)

탐색(Search)

탐색의 기본

개념

• 탐색(Search) : 어떤 집합에서 원하는 것을 찾는 것으로 검색이라고 한다.
• 탐색의 종류
  • 순차 탐색(Sequential Search)
  • 이진 탐색(Binary Search)
  • 트리 탐색(Tree Search)
• 검색 결과로 특정 집합의 위치인 인덱스를 알려 준다.
• 검색에 실패하면(찾는 데이터가 집합에 없다면) -1을 반환하는 것이 일반적이다.

 

탐색 알고리즘의 종류

• 탐색은 데이터 상태에 따라 다양한 알고리즘을 사용할 수 있다.
• 탐색할 집합이 정렬되어 있지 않은 상태라면 순차 탐색을 해야 한다.

순차 탐색(Sequential Search) 

• 순차 탐색은 처음부터 끝까지 차례대로 찾아보는 것으로, 쉽지만 비효율적인 탐색 방법이다.
• 하지만, 집합의 데이터가 정렬되어 있지 않다면 순차 탐색 외에 특별한 방법은 없다.
• 데이터가 정렬되어 있다면 순차 탐색과 이진 탐색 모두를 사용할 수 있다.

 

이진 탐색(Binary Search)

• 탐색에서 상당히 효율적인 방법 중 하나가 이진 탐색이다.
• 단, 이진 탐색은 데이터가 정렬되어 이썽야 검색이 가능하다.
• 이진 탐색은 순차 탐색에 비해서 월등히 효울적이라 데이터가 몇 백만 개, 몇 천만 개 이상이어도 빠르게 찾아낼 수 있다.

 

트리 탐색(Tree Search)

• 이진 탐색 트리(Binary Search Tree)를 활용한 트리 탐색도 데이터 검색에는 상당히 효율적이지만, 트리의 삽입, 삭제 등에는 부담이 되는 특성이 있다.

 

순차 탐색과 이진 탐색 알고리즘의 원리와 구현

① 순차 탐색

• 어떤 데이터는 정렬되지 않은 상태로 존재하고, 어떤 데이터는 정렬된 상태로 존재한다.
• 이 두 경우에 데이터를 찾는 방법은 조금 다르다.

 

정렬되지 않은 집합의 순차 탐색 원리와 구현

• 순차 탐색은 찾을 데이터의 집합의 맨 앞부터 찾아가야 한다.

 

검색 성공

• 첫 번째 데이터부터 차례로 비교해서 찾은 데이터의 위치를 반환한다.

 

검색 실패

• 첫 번째 데이터부터 차례로 비교해서 찾지 못할 경우, -1 위치를 찾았다고 반환해서 검색에 실패한 것으로 처리한다.

 

구현

def seqSearch(ary, fData) :
    pos = -1
    size = len(ary)
    print('## 비교한 데이터 ==> ', end = '')
    for i in range(size) :
        print(ary[i], end = ' ')
        if ary[i] == fData :
            pos = i
            break
    print()
    return pos

dataAry = [188, 150, 168, 162, 105, 120, 177, 50]
findData = 0

findData = int(input('* 찾을 값을 입력하세요. --> '))
print('배열 -->', dataAry)
position = seqSearch(dataAry, findData)
if position == -1 :
    print(findData, '(이)가 없네요.')
else :
    print(findData,'(은)는 ', position, '위치에 있음')

* 찾을 값을 입력하세요. --> 105
배열 --> [188, 150, 168, 162, 105, 120, 177, 50]
## 비교한 데이터 ==> 188 150 168 162 105 
105 (은)는  4 위치에 있음

* 찾을 값을 입력하세요. --> 100
배열 --> [188, 150, 168, 162, 105, 120, 177, 50]
## 비교한 데이터 ==> 188 150 168 162 105 120 177 50
100 (이)가 없네요.

 

정렬된 집합의 순차 검색 원리와 구현

검색 성공

• 첫 번째 데이터부터 차례로 비교해서 찾은 데이터의 위치를 반환한다.

 

검색 실패

• 첫 번째 데이터부터 차례로 비교해서 찾을 데이터보다 큰 데이터를 만나도 못 찾으면 이후는 검색할 필요 없이 검색에 실패한 것이다. 이때는  -1 위치를 찾았다고 반환해서 검색에 실패한 것으로 처리한다.

 

구현

def seqSearch(ary, fData) :
    pos = -1
    size = len(ary)
    print('## 비교한 데이터 ==> ', end = '')
    for i in range(size) :
        print(ary[i], end = ' ')
        if ary[i] == fData :
            pos = i
            break
        elif ary[i] > fData :
            break
    print()
    return pos

dataAry = [188, 150, 168, 162, 105, 120, 177, 50]
findData = 0

dataAry.sort()
findData = int(input('* 찾을 값을 입력하세요. --> '))
print('배열 -->', dataAry)
position = seqSearch(dataAry, findData)
if position == -1 :
    print(findData, '(이)가 없네요.')
else :
    print(findData, '(은)는 ', position, '위치에 있음')

* 찾을 값을 입력하세요. --> 150
배열 --> [50, 105, 120, 150, 162, 168, 177, 188]
## 비교한 데이터 ==> 50 105 120 150
150 (은)는  3 위치에 있음

* 찾을 값을 입력하세요. --> 70
배열 --> [50, 105, 120, 150, 162, 168, 177, 188]
## 비교한 데이터 ==> 50 105
70 (이)가 없네요.

 

순차 탐색의 시간 복잡도

정렬되지 않은 집합

• 정렬되지 않은 집합의 순차 탐색은 찾는 데이터가 앞쪽에 배치되어 있는 운이 좋은 경우에는 몇 번의 비교만으로 검색을 완료할 수 있다.
• 하지만, 가장 뒤쪽에 배치되거나 아예 없는 데이터를 모든 데이터와 비교해야 한다.
• 데이터 개수가 `n`개라면 시간 복잡도는 `O(n)`으로 표현된다.

 

정렬된 집합

• 정렬된 집합의 순차 탐색 역시 운이 좋게 찾을 데이터가 앞쪽이라면 몇 번의 비교만으로 완료할 수 있다.
• 검색할 데이터가 없는 경우에도 데이터의 크기가 작다면 앞쪽만 검색한 후 검색 실패를 효율적으로 확인할 수 있다.
• 하지만, 최악의 경우에는 맨 마지막까지 검색할 수 있으므로 시간 복잡도는 `O(n)`으로 표현해야 한다.

 

② 이진 탐색(Binary Search)

이진 탐색의 원리와 시간 복잡도

원리

• 정렬된 데이터 집합을 검색하는 경우에는 이진 탐색(Binary Search)을 주로 사용하는데, 순차 탐색에 비해서 엄청난 성능으로 데이터를 검색할 수 있다.
• 이진 탐색은 전체를 반씩 잘라내서 한쪽을 버리는 방식을 사용한다.
• 데이터 개수가 계속 1/2씩만 남으므로 급격히 비교할 데이터 개수가 줄어든다.
• 찾는 값을 검색하고자 1단계에서 중앙 위치를 기준으로 잡는다.
  • 찾는 값이 왼쪽 구역에 있을 경우, 오른쪽 구역을 버린다.
    • 이 과정을 찾을 값을 찾을 때까지 반복한다.

 

시간 복잡도

• 이진 탐색의 데이터 개수를 1/2로 줄여 가면서 비교한 시간 복잡도는 `O(log_{2}n)`이 된다.
  • `O(n)`에 비해 엄청나게 효과적인 방식이다.

 

이진 탐색 구현

• 이진 탐색 구현은 키를 찾기 위해 계속 시작, 중앙, 끝을 반복적으로 1/2씩 줄여 가면서 계산하는 방식이다.
• 검색할 범위를 1/2씩 반복해서 분할하는 기법을 분할 정복(Divide and Conquer)이라고 한다.

① 전체의 첫 데이터를 '시작'으로 지정하고, 마지막 데이터를 '끝'으로 지정한 후, 시작과 끝의 중앙인 데이터를 찾을 값과 비교한다.
② 끝은 그대로 두고 시작을 중앙의 바로 오른쪽으로 옮긴다.
③ 중앙의 오른쪽 그룹에서 다시 시작과 끝의 1/2 위치인 새 중앙을 찾을 값과 비교한다.
④ 시작은 그대로 두고 끝을 중앙의 바로 왼쪽으로 옮긴다.
⑤ 중앙의 왼쪽 그룹에서 다시 시작과 끝의 1/2 위치인 새 중앙을 찾을 값과 비교한다.
...(②~⑤ 과정 반복)
⑥ 검색 성공/실패

 

시작 = 0
끝 = 배열길이 - 1
while (시작 <= 끝)
    중앙 = (시작+끝) // 2
    if 찾는값 == 중앙 :
        검색 성공. 중앙 위치 반환
    elif 찾는값 > 중앙 :
        시작 = 중앙 + 1
    else :
        끝 = 중앙 - 1
while 문에서 중앙 위치를 반환하지 못하고, 여기까지 오면 검색 실패

 

구현

def binSearch(ary, fData) :
    pos = -1
    start = 0
    end = len(ary) - 1

    while (start <= end) :
        mid = (start + end ) // 2
        if fData == ary[mid] :
            return mid
        elif fData > ary[mid] :
            start = mid + 1
        else :
            end = mid - 1

    return pos

dataAry = [ 50, 60, 105, 120, 150, 160, 162, 168, 177, 188]
findData = 162  # 할머니키

print('배열 -->', dataAry)
position = binSearch(dataAry, findData)
if position == -1 :
    print(findData,'(이)가 없네요.')
else :
    print(findData,'(은)는 ', position, '위치에 있음')

배열 --> [50, 60, 105, 120, 150, 160, 162, 168, 177, 188]
162 (은)는  6 위치에 있음

 

이진 탐색 알고리즘의 응용

색인으로 도서관 책 찾기

• 색인 또는 인덱스(Index)는 순서가 없는 데이터에서 특정 열(Column)만 추출하여 순서대로 정렬한 것이다.
• 색인은 원래 데이터 위치도 함께 관리해야 한다.
• 색인표를 만든 후 도서명 또는 작가명으로 이진 탐색을 하면 아주 빠른 탐색이 가능하다.

 

책장 배열 정의

bookAry = [['어린왕자', '쌩떽쥐베리'],['이방인', '까뮈'], ['부활', '톨스토이'],
           ['신곡', '단테'], ['돈키호테', '세르반테스'], ['동물농장', '조지오웰'],
           ['데미안','헤르만헤세'], ['파우스트', '괴테'], ['대지', '펄벅']]

 

도서명만 추출하고, 도서명 옆에 책의 순번(책장 위치) 기록

정렬전_색인표 = []
순번 = 0
for 책한권 in 책장배열 :
    정렬전_색인표.append((책한권[도서명], 순번))
    순번 += 1

 

도서명을 기준으로 색인표 배열 정렬

• 파이썬의 sorted() 함수를 사용해서 0번째 열인 도서명 열을 기준으로 정렬

정렬후_색인표 = sorted(정렬전_색인표, key=0번째 열)

 

작가명 색인표 만들기

• 위와 같은 방식으로 [작가명 색인표]를 만든다.

 

구현

from operator import itemgetter

def makeIndex(ary, pos) :
    beforeAry = []
    index = 0
    for data in ary :
        beforeAry.append( (data[pos], index) )
        index += 1

    sortedAry = sorted(beforeAry, key = itemgetter(0))
    return sortedAry

def bookSearch(ary, fData) :
    pos = -1
    start = 0
    end = len(ary) - 1

    while (start <= end) :
        mid = (start + end ) // 2
        if fData == ary[mid][0] :
            return ary[mid][1]
        elif fData > ary[mid][0] :
            start = mid + 1
        else :
            end = mid - 1

    return pos

bookAry = [['어린왕자', '쌩떽쥐베리'],['이방인', '까뮈'], ['부활', '톨스토이'],
           ['신곡', '단테'], ['돈키호테', '세르반테스'], ['동물농장', '조지오웰'],
           ['데미안','헤르만헤세'], ['파우스트', '괴테'], ['대지', '펄벅']]
nameIndex = []
authIndex = []

print('#책장의 도서 ==>', bookAry)
nameIndex = makeIndex(bookAry, 0)
print('#도서명 색인표 ==>', nameIndex)
authIndex = makeIndex(bookAry, 1)
print('#작가명 색인표 ==>', authIndex)

findName = '신곡'
findPos = bookSearch(nameIndex, findName)
if findPos != -1 :
    print(findName, '의 작가는', bookAry[findPos][1], '입니다.')
else :
    print(findName, ' 책은 없습니다.')

findName = '괴테'
findPos = bookSearch(authIndex, findName)
if findPos != -1 :
    print(findName, '의 도서는', bookAry[findPos][0], '입니다.')
else :
    print(findName, ' 작가는 없습니다.')

#책장의 도서 ==> [['어린왕자', '쌩떽쥐베리'], ['이방인', '까뮈'], ['부활', '톨스토이'], ['신곡', '단테'], ['돈키호테', '세르반테스'], ['동물농장', '조지오웰'], ['데미안', '헤르만헤세'], ['파우스트', '괴테'], ['대지', '펄벅']]
#도서명 색인표 ==> [('대지', 8), ('데미안', 6), ('돈키호테', 4), ('동물농장', 5), ('부활', 2), ('신곡', 3), ('어린왕자', 0), ('이방인', 1), ('파우스트', 7)]
#작가명 색인표 ==> [('괴테', 7), ('까뮈', 1), ('단테', 3), ('세르반테스', 4), ('쌩떽쥐베리', 0), ('조지오웰', 5), ('톨스토이', 2), ('펄벅', 8), ('헤르만헤세', 6)]
신곡 의 작가는 단테 입니다.
괴테 의 도서는 파우스트 입니다.