알고리즘이란?

  • 어떤 일을 하기 위한 명령의 집합

알고리즘 학습 시 중요한 것은 각 알고리즘들의 차이점을 이해하는 것.

  • 병렬 정렬 vs 퀵 정렬
  • 배열 vs 리스트

이진탐색

  • 입력: 정렬된 리스트
  • 출력: 리스트에 원하는 원소가 있으면 원소의 위치 반환 or null 반환

이진 탐색의 쉬운 예제

  • 1 ~ 100 중 원하는 숫자를 찾을 때 1, 2, 3, ..., 100 처럼 1씩 증가하면서 찾는 알고리즘은 Simple Search(단순 탐색)라고 한다.
  • 이진 탐색은 100의 중간 값인 50부터 검색을 시작한다.
  • 값 82를 찾는다고 하면 50 -> 75 -> 82 순으로 3번에 값을 찾는다.
  • 이진 탐색은 결과를 최대 log N 번만에 찾을 수 있다.
  # 입력 값: 정렬된 list, 찾을 item 원소
  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    # 찾으면 item의 위치 반환

          if guess > item:
              high = mid - 1 

          else:
              low = mid + 1
      return None             # 없으면 None 반환

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

  print(binary_search(my_list, 3))
  print(binary_search(my_list, -1))

빅오 표기법

  • 알고리즘이 얼마나 빠른지 표시하는 특별한 방법
  • 속도를 시간 단위로 세지 않고, 연산 횟수를 비교하기 위한 것
  • 수행해야 할 일이 많아질 때, 알고리즘에 걸리는 시간이 어떤식으로 증가하는지 알수있다.(최악의 실행시간을 나타낸다.)
  • 이진탐색은 크기가 n인 리스트를 확인하기 위해 logN의 연산이 필요 (O(logN))