Algorithms, Data Analytics

재귀용법을 활용한 병합 정렬 알고리즘

 -> 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다

 -> 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.

 -> 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한다.

def split(list):

    if len(list) <= 1:
        return list
    
    left_list = split(list[:int(len(list) / 2)])
    right_list = split(list[int(len(list) / 2):])
    
    return merge(left_list, right_list)


def merge(left_list, right_list):

    arrange_list = []
    lp, rp = 0, 0
    
    while (len(left_list) > lp and len(right_list) > rp):

        if (left_list[lp] > right_list[rp]):
            
            arrange_list.append(right_list[rp])
            rp += 1

        else:
            
            arrange_list.append(left_list[lp])
            lp += 1
            
    while (len(left_list) > lp):
        
        arrange_list.append(left_list[lp])
        lp += 1
        
    while(len(right_list) > rp):
        
        arrange_list.append(right_list[rp])
        rp += 1
        
                 
    return arrange_list

이 부분은 2가지의 함수를 사용하였다.

먼저 리스트를 절반으로 나누어 주는데, 계속 절반으로 나눠줘야하기 때문에 리스트를 나누는 부분에 재귀를 적용하였다.

다음은 나누어진 리스트를 작은 순서대로 arrange_list에 넣어준다. 혹시 한쪽 리스트에 있는 값이 다른쪽 리스트에 있는 값 보다 모두 작아서 한쪽 리스트의 값이 하나도 없을 경우도 고려해준다.

그다음 정렬된 리스트를 반환해준다.

강의를 들을수록 초보자도 쉽게 알 수 있게 강의 순서를 고려해주신 것 같다.

설명도 물론 좋다.

정렬 알고리즘의 꽃이라고 한다.

기준점(pivot)을 정해서 기준점보다 작은 데이터는 왼쪽, 큰데이터는 오른쪽으로 모으는 함수를 작성

각 왼쪽, 오른쪽은 재귀용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복함

함수는 왼쪽 + 기준점 + 오른쪽을 리턴함

def qsort(list):
    
    if (len(list) <= 1):
        return list
    
    left = []
    right = []
    pivot = list[0]
    
    for n in range(1, len(list)):
        
        if pivot > list[n]:
            left.append(list[n])
            
        else:
            right.append(list[n])
        
    return qsort(left) + [pivot] + qsort(right)

전에 C++로 했을 때 보다 이해도 쉽고 코드구현도 쉬웠다.

pivot 값 보다 작은 값을 저장 할 left 리스트와 큰 값을 저장 할 right 리스트 선언하고

pivot 값을 list의 0번째 값으로 지정한다.

for문을 통해 작은 값과 큰 값을 나눠준다.

재귀알고리즘을 사용하여 left 리스트와 right 리스트에서도 위의 과정을 진행해준다.

시간복잡도는 O(n logn)이다.

최악의 경우

 -> 맨 처음 pivot이 가장 크거나 가장 작으면 모든 데이터를 비교하는 상황이 나와서 O(n^2)이 나온다.

 -> 빅O표기법은 최악의 경우를 표기하는 것이 맞으나 최악의 경우가 거의 나오기 힘들기 때문에 평균적인 시간 복잡도로 채택하였다

동적 계획법

 -> 1) 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘

 -> 2) 상향식 접근법으로 가장 최하위 해답을 구한 후, 이를 저장하고 해당 결과값을 이용해서 상위 문제를 풀어가는 방식

 -> 3) Memoization 기법을 사용함

         -> 프로그램 실행 시 이전에 계산한 값을 저장하여 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술

 -> 문제를 잘게 쪼갤 때, 부분 문제는 중복되어 재활용됨( Ex) 피보나치 수열 )

분할 정복

 -> 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘

 -> 하향식 접근법으로 상위의 해답을 구하기 위해 아래로 내려가면서 하위의 해답을 구하는 방식

     -> 일반적으로 재귀함수로 구현

 -> 문제를 잘게 쪼갤 때 부분 문제는 서로 중복되지 않음 ( Ex) 병합 정렬, 퀵 정렬 등 )

공통점과 차이점

 -> 공통점 : 문제를 잘게 쪼개서 가장 작은 단위로 분할

 -> 차이점 : 동적 계획법 ->  -> 부분 문제는 중복되어 상위 문제 해결 시 재활용, Memoization 기법 사용( 부분 문제의 해답을 저장해서 재활용하는 최적화 기법으로 사용)

                 분할 정복 -> 부분 문제는 서로 중복 되지 않음, Memoization 기법 사용 안함

동적 계획법

 -> 1) 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘

 -> 2) 상향식 접근법으로 가장 최하위 해답을 구한 후, 이를 저장하고 해당 결과값을 이용해서 상위 문제를 풀어가는 방식

 -> 3) Memoization 기법을 사용함

         -> 프로그램 실행 시 이전에 계산한 값을 저장하여 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술

 -> 문제를 잘게 쪼갤 때, 부분 문제는 중복되어 재활용됨( Ex) 피보나치 수열 )

분할 정복

 -> 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘

 -> 하향식 접근법으로 상위의 해답을 구하기 위해 아래로 내려가면서 하위의 해답을 구하는 방식

     -> 일반적으로 재귀함수로 구현

 -> 문제를 잘게 쪼갤 때 부분 문제는 서로 중복되지 않음 ( Ex) 병합 정렬, 퀵 정렬 등 )

공통점과 차이점

 -> 공통점 : 문제를 잘게 쪼개서 가장 작은 단위로 분할

 -> 차이점 : 동적 계획법 -> -> 부분 문제는 중복되어 상위 문제 해결 시 재활용, Memoization 기법 사용( 부분 문제의 해답을 저장해서 재활용하는 최적화 기법으로 사용)

                 분할 정복 -> 부분 문제는 서로 중복 되지 않음, Memoization 기법 사용 안함

피보나치 수열을 동적 계획법으로 구현

def fibo(n):
    cache = [0 for i in range(n + 1)]
    cache[0] = 0
    cache[1] = 1
    
    for i in range(2, n + 1):
        cache[i] = cache[i-1] + cache[i-2]
        
    return cache[n]