Lesson 3: Searching and Sorting

1. Binary Search의 예를 들어, 알고리즘이 무엇인가에 대해서 설명했다. 알고리즘이란 문제를 풀기 위한 트릭의 높은 수준의 묘사이다. 

 

2. 바이너리 서치의 효율성: 우리가 공부하고 있는 것은 알고리즘의 효율성에 관한 문제다. 어떤 알고리즘이 얼마 효율 적인가에 대해 알기 위해서는, 얼마나 반복되고 있는가에 대해서 알아야 한다.

 

2-1. Binary Search의 효율성은 O(logN)이라고 외우고 있는 방법이 가장 똑똑한 방법이긴 하지만, 알지 못하는 알고리즘이 나왔다면 증명을 해야 한다. 이 증명을 위해서 표를 그리고, 최악의 경우를 생각해보자. 반을 가르고, 왼쪽을 본다고 가정할 때, 현재 비교해야 하는 어레이의 값보다 큰 하나를 정하고 반복을 진행해본다. 

 

 

 

2-2. 예를 들어 어레이 사이즈가 1일때, 2일떄, 3일떄,....를 반복하여 규칙성을 찾는 것이다.

 

 

2-3. 어레이 사이즈가 2의 제곱승으로 증가할 때마다, 반복은 1씩 증가하고 있다.

 

2-4. 그것을 수학 기호로 표현하면 로그2의 n +1이 된다.

 

2-5. 하지만 효율성 측면에서 상수는 무시되기 떄문에  O(log(n))이 효율성이 된다.

 

3.  바이너리 서치의 코드를 짜는 것이 퀴즈다. 항상 검색은 위치를 기반으로 하는 것을 잊지 말아야 한다.

"""You're going to write a binary search function.
You should use an iterative approach - meaning
using loops.
Your function should take two inputs:
a Python list to search through, and the value
you're searching for.
Assume the list only has distinct elements,
meaning there are no repeated values, and 
elements are in a strictly increasing order.
Return the index of value, or -1 if the value
doesn't exist in the list."""

def binary_search(input_array, value):
    low = 1
    high = len(input_array)
   

    while low <= high:
        mid = (low + high)/2
        if input_array[mid] == value:
            return mid
            break
        elif input_array[mid] > value:
            low = mid +1
        else :
            high = mid -1
    
    return -1

test_list = [1,3,9,11,15,19,29]
test_val1 = 25
test_val2 = 15
print binary_search(test_list, test_val1)
print binary_search(test_list, test_val2)

4. Recursion 

 

4-1.일종의 while문인 리컬스비 알고리즘은, 자기 자신을 복제하여 반복문을 수행한다. 일정 조건이 만족하면 반복이 끝이 나는데, 잘못하면, 무한 반복이 될 수 있음으로 주의해야 한다.

 

 

 

5. 피보나치 수열의 위치가 주어졌을 때, 그 값을 구하는 코드이다. 난 아주 지랄 쌩쑈를 한 시간 동안 해도 풀지 못했는데, 정말 네 줄만에 풀어버릴 줄은 상상도 못했다. 보고도 믿기지 않아서 5까지 손으로 풀어보았다.  피보나 치 수열도 결국은 더하기... 쪼개고 쪼개놓고 보면 0+1에서 시작한 것이었다. 그것을 코드로 표현하면 요렇게 된다. recusion(반복)이 계속되는 구조다. 

 

내가 풀다가 망친 것.... ㅋㅋㅋㅋㅋ

global first 
global second 
global next 
global t 


first = 0
second = 1
next = 0
t =0

def get_fib(position):

    if t == position :
        return next
    else :
        next = first + second
        first =second
        second =next
        t += 1
        output =get_fib(position)
        
        return output
        

정답

def get_fib(position):
    if position == 0 or position == 1:
        return position
    return get_fib(position - 1) + get_fib(position - 2)

6. intro Sorting Algoritm

 

6-1. 순서를 만들 때, 모든 것들을 모든 것들과 비교하는 것이 가장 순진한 방법이다. 순진한 방법에는 트릭이 없다.

6-2. 트릭이 알고리즘이다. 똑똑한 방법을 찾아야한다. 솔팅은 약간 이상한 주제이긴 하지만, 분명히 중요하다. 솔팅 알고르즘이 어떻게 작용하는지 이해하고, 런타임이 얼마인지 알아야 한다. 또 이 솔팅이 새로운 데이터가 만들어지면서 작동하는 것인지, 아니면 기존의 데이터 내에서 작동하는지도 중요하다. 솔팅 방법에서 시간을 희생해서 공간을 줄이거나, 공간을 희생해서 시간을 줄일 수 있는데, 어떤 것이든 이유만 있으면 괜찮다.

 

7. 버블 솔트는 나이브한 접근법이다. 버블솔트는 정렬이 될 때까지 반복하여 두 개의 값을 비교한다. 빅오 표기법으로 표시하면 사이즈가 n인 배열에 대하여 n-1 * (n-1)번의 반복을 시행해야한다 즉 O(n^2)

 

 

 

7-2. 최악, 평균의 경우 n^2 이며, 최고의 경우 n이다. 

7-2. 버블 솔트는 새로운 공간이 필요하지 않으므로 인플레이스 알고리즘이며 O(1)의 효율성을 가진다.

 

 

8. 머지 솔트는 다바이드엔 콘쿼라고도 부른다. 일단 대충 나눈 다음에, 순서를 정하고, 나눠진 다른 조각들과 비교하며

순서를 만들어간다.

 

 

 

8-2. 머지소트의 효율성은 다음과 같다. 규칙성을 찾아나가 보면, 어레이의 사이즈가 2의 n승+1일 때마다 반복은 증가한다. 하지만 효율성은 "대략"따지기 때문에 중요하지 않다. 

8-3.  바이너리 서치를 했던 때와 같이 log(n)의 속도로 증가한다. 매 단계에서 비교가 반복되는 횟수도 대략 "n"이기 떄문에 log(n)에 n을 곱한다.

8-4. 측공간이라는 새로운 공간에서 반복이 수행됨으로 O(n)이 된다.

9. 퀵 솔트 : 보통 가장 효율적이다. 퀵솔트는 일단 임의의 수 하나를 선택 한 후, 그것을 기준으로 앞에서 부터 숫자를 비교한다. 그 숫자보다 크면 뒤에다 놓고, 작으면 앞으로 위치 시킨다. 이를 피벗이라고 하며, 이 피벗이 임의의 숫자에 의하여 수행되었을 때, 그 숫자의 위치는 바뀌지 않는다.

 

 

9-2. 그 숫자를 기준으로(여기서는 2)앞 과 뒤의 숫자 그룹에 대해서 다시 피벗 솔팅을 진행한다. 반복되면 모두 정렬된다.

9-3. 최악의 경우는 그 임의의 숫자가 본래 자리에 있는 경우다. 이 경우는 버블솔트와 마찬가지로 모든 숫자에 대하여 비교해야 한다.이때 효율성은 O(n^2)이다

 

 

9-4. 하지만 평균과 최적의 경우는 O(nlog(n))이다. 중간 중간 딱 맞아 떨어진다면 머지 소트와 비슷해진다. 위에서 봤던 것처럼, 이미조금 솔팅이 되어있다면 퀵솔트를 쓰면 효율이 좋지 않아진다.

 

9-5. 효율성 측면에서, 공간도 인플레이스로 진행될 뿐만 아니라 작은 곳과 큰곳에서 동시에 프로세스를 진행하면서 속도를 높일 수 있다.

또한 최악의 경우를 방지하기 위해서, 끝부분에서 중앙값을 택하게 할 수 도 있으니, 많은 사람들이 퀵 솔트를 사용한

 

 

10. 답안지를 보고 풀면서도, 감탄스럽다. 리커선을 이용하여, 더 이상 반복되지 않는 곳을 답으로 만들게 하는 것이 정말 신기하다.

왼쪽/중간/오른쪽으로 공간을 나누는 것을 어레이의 사이즈가 1일 때까지 수행하라!

계속 수행하다 보면 각자의 범위 안에서 재배열 되고, 재배열 되어,  모든 입력 리스트의 사이즈는 1이된다. 이때부터 반복문에서 빠져 나오면서 우리가 원하는 정렬된 리스트를 가지게 된다!

 

 

"""Implement quick sort in Python.
Input a list.
Output a sorted list."""
def quicksort(array):
    
    if len(array) > 1:
        pivot = array[len(array)-1]
        left, mid, right = [], [], []
        for i in range(len(array)-1):
            if array[i] < pivot:
                left.append(array[i])
            elif array[i] > pivot:
                right.append(array[i])
            else:
                mid.append(array[i])
        mid.append(pivot)
        return quicksort(left) + mid + quicksort(right)
        
    else:
        return array
            

test = [21, 4, 1, 3, 9, 20, 25, 6, 21, 14]
print quicksort(test)