Python algorithm 개념 및 실습 - 이진 탐색

알고리즘이란 ?

• 어떤 일을 하기 위한 명령의 집합
• 문제 해결 방법을 추상화하여 각 절차를 논리적으로 기술해 놓은 것
• 어떤 문제를 해결하기 위한 절차나 방법

 

알고리즘 복잡도

• Complexity
  • 어떤 알고리즘이 문제를 풀기 위해 해야하는 계산이 얼마나 복잡한가?
• 알고리즘의 성능을 객관적으로 평가하는 기준
  • 시간복잡도(time complexity) : 실행 횟수로 판단
  • 공간복잡도(space complexity) : 기억공간과 파일 공간의 사용량
• 빅오 표기법 ( Big O Notation)
  • 알고리즘이 얼마나 빠른지 표시하는 방법
  • 입력 데이터 크기 증가할 때 알고리즘 연산 시간(횟수)의 증가 방식
  • 연산의 횟수를 비교함
  • O(n) : 계산 복잡도 
    • O : 빅 O
    • n : 연산 횟수
    • O(1) : 입력 크기 n과 계산 복잡도가 무관 할때 ex) n(n+1)/2
    • O(logn) : 입력 크기 n의 로그 값에 비례하여 증가 ex) 이분탐색
    • O(n) : 입력 크기 n에 비례하여 복잡도 증가 ex) 최댓값, 순차탐색
    • O(nlogn) : 입력 크기 n과 로그 n 값의 곱에 비례하여 복잡도 증가 ex) 병합정렬, 퀵정렬
    • O(n²) : 입력 크기 n의 제곱에 비례하여 복잡도 증가 ex) 선택정렬, 삽입정렬
    • O(n₂) : 입력 크기가 n 일 때, 2의 n 제곱 값에 비례하여 복잡도 증가 ex)하노이의 탑

 

 

이진 탐색 

• 자료가 정렬된 상태여야 함
• 탐색할 자료를 둘로 나누어 찾는 값이 있을 법한 곳만 탐색

def binary_search1(list1, num):

    # 시작위치 지정

    start = 0

   # 종료 위치 지정

    end = len(list1) - 1

    # 반복문 - 시작위치가 종료위치보다 작거나 같을때까지

    while start <= end:

         # 중간 위치 지정

        mid = (start + end) // 2  # 4호출 ==> 25

        # 찾고자 하는 숫자가 중간위치의 숫자보다 작으면 end = 중간위치 -1

        if num < list1[mid]:

            end = mid - 1

        # 찾고자 하는 숫자가 중간위치의 숫자보다 크면 start = 중간위치 + 1

        elif num > list1[mid]:

            start = mid + 1

        # 둘 다 아닌 경우 중간위치 리턴

        else:

            return mid

 

재귀호출

• 종료 조건 : 리스트가 빈 상태라면 탐색 종료
• 재귀
  1. 중간 위치 지정
  2. 찾는 값과 중간 위치 값이 같다면 결과값으로 중간 위치 값 돌려주기
  3. 찾는 값이 중간 위치 값보다 크다면 중간 위치의 오른쪽을 대상으로 이진 탐색 함수를 재귀호출
  4. 찾는 값이 중간 위치 값보다 작다면 중간 위치의 왼쪽을 대상으로 이진 탐색 함수를 재귀호출

 

def binary_search2(list1, num, start, end):

# 종료 조건

    if len(list1) <= 0:

        return

    # 중간 위치 지정

    mid = (start + end) // 2

    if num < list1[mid]:

        return binary_search2(list1, num, start, mid - 1)

    elif num > list1[mid]:

        return binary_search2(list1, num, mid + 1, end)

    else:

        return mid

if __name__ == "__main__":

    list1 = [1, 4, 9, 16, 25, 36, 49, 64, 81]

    print("36이 있는 위치", binary_search1(list1, 36))

    print("49가 있는 위치", binary_search2(list1, 49, 0, len(list1) - 1))