Hello Coding 그림으로 개념을 이해하는 알고리즘 - 1장 요약

알고리즘이란?

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

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

• 병렬 정렬 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))