[크래프톤 정글] WEEK02 회고

To do list : 해시 (+테이블 생성과 메모리 관련 trade-off 상충관계, isinstance)

선형탐색 (linear search)

from typing import Sequence

def seq_search(a: Sequence, key: Any) -> int:

    n = len(a)
    for i in range(n):
        if key == a[i]:
            return i
    return -1
#  보초법 적용한 seq_search

def seq_search_sentinel(a, key):
    sentinel = a.deepcopy(a)
    sentinel.append(key)
    i = 0
    while True:
        if sentinel[i] == key:
            break
        i +=1
    return -1 if i == len(sentinel) else i # 리턴 되는 값이 원래 배열의 값인지 보초 배열에 있는 값인지 판단하기 위해 만약 i 가 보초값에 있던 것이라면 -1 아닐 경우 i 반환
if __name__ == '__main__':
    n = int(input)
    x = [None] * n
    for i in range(n):
        x[i] = int(input(f'x{[i]} : '))
    key = int(input('찾을 키 값은? : '))
    
    if seq_search(x, key) != -1:
        print(f'{key} 값은 {seq_search(x, key)} 인덱스에 존재한다.')
    else:
        print('찾는 {key}값은 존재하지 않습니다.')

특징

• 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘
• 정렬되지 않은 배열을 검색할 때 사용하는 유일한 방법
• 보초법을 사용하여 탐색을 조기 종료할 수 있다.
• 시간복잡도 = O(N)

수행방법

기본

1. key (찾는 값)을 가지고 배열에 접근하여 인덱스에 하나씩 맞는지 검사하여 배열 끝까지 도달한다.

보초법 사용

1. 탐색하려는 배열(a)의 길이 + 1 만큼 새로운 배열(b)을 만들고 b에 a를 복사한 후 마지막 인덱스에 key값을 넣는다.
2. key값으로 b에서 탐색하고 key값을 찾았을 경우 보초값인지, a에 있던 원소인지 인덱스 값으로 확인 후 반환한다.

- 종료 조건
	- 검색할 값을 찾지 못하고 배열 끝에 도달할 경우 (return -1)
	- 검색할 값과 같은 원소를 찾은 경우 (return i)

이진탐색 (binary search)

from typing import Any, Sequence
import random
"""
이미 오름차순으로 정렬된 리스트에 사용 가능
정렬되지 않은 리스트일 경우 선형탐색 (linear_search) 사용
"""
def binary_search(a, key):
    left = 0
    right = len(a) - 1
    center = (left + right) // 2
    while True:
        if a[center] == key:
            return center
        elif a[center] > key:
            right = center - 1
            center = (left + right) // 2
        else:
            left = center +1
            center = (left + right) // 2
        if left > right:
            break
    return -1

def binary_search_recur(a, key, left, right):
    center = (left + right) // 2
    if a[center] == key:
        return center
    elif a[center] > key:
        binary_search_recur(a, key, left, center - 1)
    else:
        binary_search_recur(a, key, center + 1, right)

if __name__ == '__main__':
    n = int(input())
    x = [None] * n
    for i in range(n):
        x[i] = random.randint(1, 100)
    key = random.choice(x) 
	x.sort()
    print(f'키 값 {key}은 인덱스 {binary_search(x, key)}에 있습니다.')
            

특징

• 정렬된 배열에만 사용이 가능하다.

• 종료 조건
  • a[center]와 key값이 일치하는 경우 (return center)
  • 검색 범위가 더 이상 없는 경우 (return -1)
• 시간복잡도 = O(logN)

수행방법

1. 먼저 배열의 중앙 a[center]에 주목한다.
2. a[center]가 key값과 같다면 (return center)
3. key값이 a[center]보다 큰지 작은지 비교한다.
4. 크다면 left = center + 1, 작다면 right = center - 1로 범위를 1/2 시켜준다.
5. 반복한다.