[2장] 알고리즘이 중요한 까닭

자료 구조에서 봤듯이 구조 그 자체만으로도 효율성이 드라마틱하게 바뀌게 된다. 이제 자료 구조 결정 후에도 코드 효율성에 영향을 미치는 요인인 알고리즘 선택에 관해 알아볼 것

ㅇ알고리즘이 뭐냐구요?
그냥 어떤 과제를 완수하는 명령어 집합에 불과함 ㅅㄱ

2.1 정렬된 배열(ordered array)
배열은 배열인데 순서대로 값이 정렬된 배열을 말함. 정렬된 배열에서의 연산은 어떻게 될까?

2.1.1 삽입
필요 단계 : N+2 (N : 배열내 원소의 개수) // 맨 뒤에 삽입될 경우 N+1
과정을 설명하기에 앞서 그냥 배열보다 삽입연산이 비효율적인데도 쓰는 이유는 검색 연산이 매우 효율적이기 때문임. 특히, 이진 검색(binary search)가 가능한데 바로 뒤에서 살펴보겠음

배열 = [ 3, 10, 20, 200 ]
'나' : 70을 배열에 넣어라 노예야
'컴퓨터' : 순서대로 넣어야하니 70이 들어갈 자리를 찾고, 그 뒤쪽을 하나씩 밀어서 자리를 하나 마련해야겠군

[ 3(확인), 10, 20, 200 ] 어 70이 3보단 크네
[ 3, 10(확인), 20, 200 ] 어 70이 10보단 크네
[ 3, 10, 20(확인), 200 ] 어 70이 20보단 크네
[ 3, 10, 20, 200(확인) ] 오 70이 200보단 작네 여기 왼쪽에 자리하나 마련해야겠네
[ 3, 10, 20, 빈칸, 200 ]
[ 3, 10, 20, 70, 200 ]

a번째 자리에 들어가게될 값이라면 (단, a != N ... 끝 자리에 들어가는 경우가 아님을 뜻함)
[1] a+1번 비교하고 (a자리의 좌우값을 다 비교해봐야하므로)
[2] (N-a)개를 오른쪽으로 밀고
[3] 값을 삽입함 (+1)

2.2 정렬된 배열의 검색
선형 검색의 경우 일반 배열과 정렬된 배열의 검색을 비교해보자

ㅇ배열내 검색 값이 존재하는 경우 (20을 찾아보자)

ㅇ배열내 검색 값이 없는 경우 (30을 찾아보자)

2.3 이진 검색(binary search)
대학교가서 술게임으로 업앤다운 한번쯤은 다 해봤을텐데 그거 생각하면 쉬울듯요. 제가 맘속으로 1~100 사이 숫자중 하나 정했는데 맞춰보쉴? true/false로만 답해드림

Q. 50보다 큼? true
Q. 75보다 큼? false
Q. 63보다 큼? yes
Q. 69보다 큼? 헉;;

ㅇ컴퓨터에서의 이진검색
'나' : 4를 찾아와라 노예야
'컴퓨터'

ㅇ코드구현

def binary_search(array, search_value):
    step = 1
    lower_bound = 0
    upper_bound = len(array) - 1

    while (lower_bound <= upper_bound):
        midpoint = int((upper_bound + lower_bound) / 2)
        value_at_midpoint = array[midpoint]
        
        print(step)

        if search_value == value_at_midpoint:        
            return midpoint
        elif search_value < value_at_midpoint:
            upper_bound = midpoint - 1
        elif search_value > value_at_midpoint:
            lower_bound = midpoint + 1
        
        step += 1

    return "no value"

정렬된배열 = [1, 20, 30, 40, 50, 60, 70, 80, 120, 140, 200]
찾는값 = 130

a = binary_search(정렬된배열, 찾는값)
print(a)

2.4 선형 검색 vs 이진 검색
원소가 100만개쯤 되는 배열이 있다고 하자. 각각 최악의 시나리오를 구할 수 있겠는가?
  - 선형검색 : 100만 단계
  - 이진검색 : 20단계

어떻게 나왔냐구요?
선형검색은 순서대로 하나씩 뒤져보는거니까 N개만큼 다 뒤질테고
이진검색은 한번 검색마다 검색해야할 대상이 1/2 씩 줄어드니까
N/2 → N/4 → N/8  → N/16  → N/32 ... 
즉, N ≤ 2^x 가 되는 x를 찾으면 그게 곧 최악의 시나리오임

물론 원소 수가 적고 삽입도 병행해야하는 경우라면 (혹은 삽입만 하는 경우라면)
정렬된 배열과 이진검색을 쓰는게 오히려 나쁠 수도 있으니
때에 맞게 잘 사용합시다