알고리즘을 파이썬으로 이해하기_1

알고리즘은 일반적으로 어렵다고 알려져 있습니다.

2017년 4월에 출판된 서적에서 많은 도움을 받고 있습니다. (Hello Coding 알고리즘)

앞으로 9개의 소스로 알고리즘을 해석하려고 합니다.

오늘은 1차 [이진탐색] 에 대해서 파이썬으로 내용을 연습해 보았습니다.

확인 URL:

http://www.pythontutor.com/visualize.html

위 입력창에 아래 소스를 붙여넣고 [Visualize Execution] 버튼을 클릭합니다.

# ========= 소스 시작 ==========

# 시간복잡도(연산횟수)에 사용되는 로그함수 제작
import math
def logB(x, base): # 2를 base밑으로하는 로그 함수
 return math.log(x)/math.log(base)
print "log2(5) = ", math.ceil(logB(5.0,2.0)) # 소수점 이하는 무조건 올림 예 2.3번 = 3번

# 이진탐색 구하기
def binary_search(list, item):
  # 검색할 목록(배열)의  영역의 시작위치와 끝위치를 지정 한다.
  low = 0
  high = len(list) - 1

  # 목록(배열)의 수 만큼 반복한다.
  while low <= high:
    # 목록(배열)의 중간위치를 추출한다
    mid = (low + high) // 2
    print "mid =  ",mid # 몇번 반복된는지 확인용
    guess = list[mid]
    # 중간위치 항목값과 item 파라미터값을 비교한다.
    if guess == item:
      return mid # 3번째 while 반복에서 배열의 list[1] 에서 1을 리턴하면 반복문 종료 즉 2진탐색은 검색횟수가 밑이2인 log 5 = 2.3  = 3번
    # 중간위치값이 item 파라미터값 보다 크다면.
    if guess > item:
      high = mid - 1 # 검색할 목록(배열)의 끝을 중간값-1로 변경
    # 중간위치값이 item 파라미터값 보다 작다면
    else:
      low = mid + 1 # 검색할 목록(배열)의 시작을 중간값+1로 변경

  # 위 while문이 조건에 맞지 않아서 실행을 건너띄고 즉, 검색할 item이 없다면 None 리턴
  return None

my_list = [1, 3, 5, 7, 9]
print binary_search(my_list, 3),"(result1)" # => 1

# 위 while문 2번 반복하고, 건너띄고 None 출력
print binary_search(my_list, -1),"(result2)" # => None

# ========= 소스 끝 ==========

다음은 2차 [선택탐색] 에 대해서 파이썬으로 내용을 연습해 보겠습니다.