그림으로 개념을 이해하는 알고리즘

Chapter 2. 이진탐색

  • 예를 들어 전화번호부를 찾는다고 치자 이 씨를 찾기위해서는 맨앞에서 시작하는 방법과 중간부터 시작하는 방법 등 다양한 방법이 있을 것이다.
  • 처음에서 시작하는 것보다 중간에서 시작하는 것이 더 빨리 탐색
  • 1~100 까지 숫자 있을 때 1부터 순서대로 찾게 된다면 100이 찾는 수라면 100번을 수행해야 찾게 된다. (Simple Search)

더 좋은 탐색 방법

100의 중간 50부터 시작하는 것. 해당 부분보다 적거나 많다면 다시 절반 이러한 방식으로 찾게 된다면 더 빨리 찾게 될 것이다.

  • 예) 100 -> 50 -> 25 -> 13 -> 7 -> 4-> 2 -> 1과 같은 순서대로 진행 될 것이다.

  • 240,000개의 단어가 있다면 최대 몇 번만에 정답을 찾을까?

    • 단순 : 만약 최악의 수로 가장 마지막에 있다면 240,000번

    • 이진 : 총 18번 (240k -> 120k -> 60k -> 30k -> 15k -> 7.5k -> 3750 -> 1875 -> 938 -> 469 -> 235 -> … -> 1)

      • n개의 원소를 가진 리스트에서 이진 탐색 : \(최대 \ Log_2n\)

      • 빅오표기법에서 사용하는 Log는 아래가 2인 로그이다

PYTHON 코드

# python 3.5 
def binary_search(list, item):
	low = 0
  	high = len(list) - 1

 	while low <= high:
      	mid = (low + high) // 2
  		guess = list[mid]
  		if guess == item:
    		return mid
        if guess > item:
    		high = mid - 1
  		else:
    		low = mid + 1
    return None
  
my_list = [1,3,5,7,9]
print(binear_search(my_list,3)) # => 1
print(binear_search(my_list,-1)) # => None

실행시간

  • 단순 탐색과 같이 100개의 리스트 100번의 탐색과 같이 추측해야할 최대 횟수와 같은 것을 선형시간이라고 한다.
    • 단순탐색 : O(n)
  • 이진 탐색과 같이 100개의 리스트 7번, 40억개 32번만 추측. 이러한 것을 로그 시간이라고 한다.
    • 이진탐색 : O(logN)

빅오 표기법

  • 알고리즘이 얼마나 빠른지 표시하는 특별한 방법

예 : 밥이라는 NASA의 프로그래머가 있다고 하자.

우주선이 달에 착륙해야하는데 10초의 시간이 주어졌고, 해당 코드는 정확하고 빠르게 작동해야 한다.

  • 시간 : 이진탐색, 안전성 : 단순탐색
  • 조건 : 원소 하나 확인하는데 1밀리 초가 걸린다고 가정.
  • 중간 계산
    • 단순 : 100개 -> 100밀리초
    • 이진 : 100개 -> 7밀리초
      • 15배 정도 차이가 난다.
    • 이진 : 10억개 -> 30밀리초
      • 단순 : 30 x 15 = 450 밀리초 -> 틀렸다.
      • 단순 : 10억개 -> 10억밀리초 -> 11일
    • 즉, 증가되는 속도가 다르다.
  • 원소의 수가 커지면 커질수록 이진 탐색이 더 빠르게 검색한다.
  • 알고리즘의 실행 시간이 얼마가 걸리는지만 고려할 것이 아니라, 리스트의 크기가 증가할 때 어떻게 증가하는지를 파악할 필요가 있는데 빅오 표기법을 사용하는 이유가 그 이유다.

여러가지 빅오 실행 시간 살펴보기

종이 하나를 가지고 네모 16개를 만드는 알고리즘.

알고리즘 1
  • 조그만한 네모를 종이에 16개를 나눠서 그리게 되는 경우
  • 16번의 줄긋기를 해야 함.
  • 실행시간 : O(n)
알고리즘 2
  • 반으로 접고 반으로 또 접고 하는 방식으로 수행
  • 2 -> 4 -> 8 -> 16
  • 실행시간 : O(LogN)
알고리즘 실행 시간 순서
  • O(NlogN) > O(LogN) > O(N) > O(N^2) > O(N!)