[파이썬 알고리즘] 독학 중 나의 정리 노트 - 완전탐색 과 이진탐색

완전 탐색 : 가능한 모든 경우의 수에 대해 시도하며 결과를 찾는 알고리즘

ex) 자물쇠 비밀번호 3자리를 찾을때 000 ~ 999까지 코드를 사용하여 하나씩 탐색

password = 845

for look_for_password in range(1000) :
    if look_for_password == password :
        print(f"자물쇠가 열렸습니다. \n자물쇠의 비밀번호는 {look_for_password}입니다.") 

출력 :
자물쇠가 열렸습니다.
자물쇠의 비밀번호는 845입니다.

이 코드에서 나타내는 시간복잡도 : O(n)
비밀번호 자릿수가 틀려지면 코드도 틀려지기 때문에 시간 복잡도 표기 방식도 틀려진다. 

---

백트래킹(backtracking) : 왔던 길을 되짚어 간다라는 뜻으로 탐색 과정에서 잘못된 경로로 판단되면 이전으로 돌아가 다른 경로를 탐색하는것으로 완전 탐색을 최적화 하는 기법 중 하나.

그림처럼 "강아지"라는 단어를 찾기위해
"강수량","강수확" 전체를 찾지 않고 첫글자와 두번째를 순서대로 확인 후 글자가 일치하지 않을때
다시 돌아와 더 빠르게 찾을 수 있다.

---

이진탐색 : 정렬된 데이터에서 찾는 데이터를 크기를 비교하며 좁혀나가 탐색하는 방법

    최악의 상황에도 시간복잡도 O(log n)임으로 선형 탐색O(n)보다 빠르며 정답을 찾는 즉시 탐색 종료로 최선의 경우 O(1)의 시간복잡도를 가진다.

※ 정렬되지 않은 리스트에서는 사용할 수 없다.

Up! Down! 게임으로 예시


target_number = 68
print(f"탐색 숫자 : {target_number}")

tries = 0
low = 1
high = 100

while True:
    mid = (low + high) // 2
    print(f"현재 숫자 : {mid}", end = "")

    tries += 1

    if mid == target_number :
        print(f"{tries}번 시도로 찾았습니다.")
        break
    elif mid < target_number:
        print("업!")
        low = mid + 1
    else :
        print("다운!")
        high = mid - 1



출력 :
탐색 숫자 : 68
현재 숫자 : 50. 업!
현재 숫자 : 75. 다운!
현재 숫자 : 62. 업!
현재 숫자 : 68. 4번 시도로 찾았습니다.