Hello Coding 그림으로 개념을 이해하는 알고리즘 Study Note 01

Chapter 1 알고리즘의 소개

이진 탐색

- 정렬이 되어있는 원소 리스트가 필요

- 원소리스트의 중간 값으로 원소리스트의 절반씩 탐색 범위를 좁혀 가는 방법

- 이진 탐색은 크기가 n 인 리스트를 확인하기 위해 log n 번의 연산이 필요

- 빅오 표기법 O(log n)

코드 실행을 위해 Visual Studio Code + Anaconda 설치

01_binary_search.py 작성 테스트

def binary_search(list, item):

    low = 0

    high = len(list) - 1

    loopCnt = 0

    while low <= high:

        loopCnt = loopCnt + 1

        mid = (low + high) // 2

        guess = list[mid]

        if guess == item:

            print(f"LoopCnt : {loopCnt}")

            return mid

        if guess > item:

            high = mid - 1

        else:

            low = mid + 1

    print(f"LoopCnt : {loopCnt}")

    return None

   

my_list = [1,3,5,7,9]

print(binary_search(my_list, 3)) # => 1

print(binary_search(my_list, -1)) # => None

빅오 표기법

주요 5개 속도 순서 (빠름 -> 느림)

- O(log n) => 로그시간, 이진 탐색

- O(n) => 선형시간, 단순 탐색

- O(n * log n) => 퀵정렬 같은 정말 빠른 알고리즘

- O(n^2) => 선택정렬 같은 느린 정렬 알고리즘

- O(n!) => 외판원 문제 같은 정말 느린 알고리즘

원소하나 확인하는데 1밀리초가 걸린다고 가정하고

10억개의 원소가 있는 리스트라고 가정하면

- 선행시간 = 약 11.57 일

- 로그시간 = 30ms

Chapter 1 정리

이진 탐색은 단순 탐색 보다 아주 빠르다

알고리즘의 속도는 시간이 아니라 연산 횟수가 어떻게 증가하는지 빅오 표기법으로 표기한다

=> 입력 데이터 크기가 늘어날 때 알고리즘 실행 속도가 얼마나 증가하는지 알 수 있다