TIL-231007(자료구조 & 알고리즘 4주차)

📝오늘 공부한 것

• 프로그래머스 문제풀기
• 스파르타코딩클럽 자료구조 & 알고리즘 4주차 강의 듣기

 

알게 된 점❗

[ 퀵소트 ]

퀵소트(Quicksort)

분할 정복(Divide and Conquer)을 통해 주어진 배열을 정렬하는 알고리즘이다.

배열에서 기준(pivot)을 잡고, 기준보다 값이 작은 집합과 큰 집합으로 나눈다.

그리고 그 사이에 기준을 위치시킨다.

작은 집합과 큰 집합을 대상으로 재귀호출하여 정렬한 뒤 결과를 합치면 정렬된 배열을 얻을 수 있다.

 

def quicksort(lst, start, end):
    def partition(part, ps, pe):
        pivot = part[pe]
        i = ps - 1
        for j in range(ps, pe):
            if part[j] <= pivot:
                i += 1
                part[i], part[j] = part[j], part[i]

        part[i + 1], part[pe] = part[pe], part[i + 1]
        return i + 1

    if start >= end:
        return None

    p = partition(lst, start, end)
    quicksort(lst, start, p - 1)
    quicksort(lst, p + 1, end)
    return lst

 

[ Mergesort ]

def merge(arr1, arr2):
    result = []
    i = j = 0
    while i < len(arr1) and j < len(arr2):
        if arr1[i] < arr2[j]:
            result.append(arr1[i])
            i += 1
        else:
            result.append(arr2[j])
            j += 1

    while i < len(arr1):
        result.append(arr1[i])
        i += 1

    while j < len(arr2):
        result.append(arr2[j])
        j += 1

    return result

시간 복잡도는 총 O(Nlog_2N) = O(NlogN) 이 된다.

 

[ Heapsort ]

힙

• 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리
• 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조
• 부모 노드의 값이 자식 노드의 값보다 항상 커야한다. 그러면 가장 큰 값은 모든 자식보다 커야하기 때문에 가장 위로 간다. 따라서 최대의 값들을 빠르게 구할 수 있게 된다.

 

항상 최대의 값들이 필요한 연산이 있다면 힙을 사용!

 

최소 힙 - 삽입 시간복잡도

완전 이진트리의 최대 높이는 O(log(N))

반복하는 최대 횟수도 O(log(N))

즉! 최소 힙의 원소 추가는 O(log(N)) 만큼의 시간 복잡도를 가진다.

 

최소 힙 - 추출 시간복잡도

완전 이진트리의 최대 높이는 O(log(N))

반복하는 최대 횟수도 O(log(N))

즉! 최소 힙의 원소 삭제는 O(log(N)) 만큼의 시간 복잡도를 가진다.