이해하기 쉽고, 장황하지 않은 자료를 기반으로 강의를 진행합니다.

잔재미코딩 소식 공유

좀더 제약없이, IT 컨텐츠를 공유하고자, 자체 온라인 강의 사이트와 유투브 채널을 오픈하였습니다
응원해주시면, 곧 좋은 컨텐츠를 만들어서 공유하겠습니다

● 직운영 온라인 강의 서비스 오픈

● 잔재미코딩 유투브 오픈 [구독해보기]

11. 이진 탐색 (Binary Search)¶

탐색할 자료를 둘로 나누어 해당 데이터가 있을만한 곳을 탐색하는 방법

다음 문제를 먼저 생각해보자¶

No description has been provided for this image

이분 탐색의 이해 (순차 탐색과 비교하며 이해하기)¶

* [저작자] by penjee.com * [이미지출처] https://blog.penjee.com/binary-vs-linear-search-animated-gifs/

프로그래밍 연습
임의 리스트가 있을 때,

1. 리스트 중간에 있는 값 출력하기
2. 리스트 중간을 찾고, 리스트 처음부터 중간까지의 중간값을 출력해보기
import random 
data_size = random.randint(1, 100)
data_list = random.sample(range(100), data_size)

In [ ]:

import random 
data_size = random.randint(1, 100)
data_list = random.sample(range(100), data_size)

In [ ]:

len(data_list)

In [ ]:

len(data_list) / 2

In [ ]:

len(data_list) // 2

어떻게 코드로 만들까?¶

이진 탐색은 데이터가 정렬되있는 상태에서 진행
데이터가 [2, 3, 8, 12, 20] 일 때,
- binary_search(data_list, find_data) 함수를 만들고
  - find_data는 찾는 숫자
  - data_list는 데이터 리스트
  - data_list의 중간값을 find_data와 비교해서
    - find_data < data_list의 중간값 이라면
      - 맨 앞부터 data_list의 중간까지 에서 다시 find_data 찾기
    - data_list의 중간값 < find_data 이라면
      - data_list의 중간부터 맨 끝까지에서 다시 find_data 찾기
    - 그렇지 않다면, data_list의 중간값은 find_data 인 경우로, return data_list 중간위치

코드를 뜯어보며 이해하기¶

In [ ]:

import random 
data_list = random.sample(range(1000), 100)

In [ ]:

quick_sort(data_list)

In [ ]:

def binary_search(data_list, data):
    if len(data_list) == 1 and data_list[0] != data:
        return False
    elif len(data_list) == 1 and data_list[0] == data:
        return True
    
    medium = len(data_list) // 2
    
    if data > data_list[medium]:
        return binary_search(data_list[:medium], data)
    else:
        return binary_search(data_list[medium:], data)

In [ ]:

binary_search(data_list, 10)

알고리즘 분석¶

n개의 리스트를 매번 2로 나누어 1이 될 때까지 비교연산을 k회 진행
- n X $\frac { 1 }{ 2 }$ X $\frac { 1 }{ 2 }$ X $\frac { 1 }{ 2 }$ ... = 1
- n X $\frac { 1 }{ 2 }^k$ = 1
- n = $2^k$ = $log_2 n$ = $log_2 2^k$
- $log_2 n$ = k
- 빅 오 표기법으로는 k + 1 이 결국 최종 시간 복잡도임 (1이 되었을 때도, 비교연산을 한번 수행)
  - 결국 O($log_2 n$ + 1) 이고, 2와 1, 상수는 삭제 되므로, O($log n$)

프로그래밍 연습
임의 리스트가 다음과 같이 rand_data_list로 있을 때,
- 입력: k 숫자가 주어지면, rand_data_list에 해당 데이터가 있는지를 알려주는 함수 작성하기 (퀵 정렬과 이분 탐색 각각 위의 자료를 참고해서 함수로 각각 작성해서 구현하기)
- 출력: k 가 있으면 True, 없으면 False 를 리턴

import random 
data_size = random.randint(1, 100)
data_list = random.sample(range(100), data_size)

협업 과제
다음 10000개의 데이터를 삽입 정렬, 병합 정렬, 퀵 정렬로 정렬해보고 각각 정렬 시간을 구하세요

# 데이터 셋
import random 
data_list = random.sample(range(100000), 10000)
현재 시간 구하기¶
import datetime
print (datetime.datetime.now())

합리적인 분들과 확연히 다른 좋은 IT 강의를 만들 수 있는 선순환 시스템을 지향합니다