📝오늘 공부한 것
- 프로그래머스 문제풀기
- 스파르타코딩클럽 자료구조 & 알고리즘 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)) 만큼의 시간 복잡도를 가진다.
'TIL(Today I Learned)' 카테고리의 다른 글
TIL-231010(자료구조 & 알고리즘 5주차) (0) | 2023.10.10 |
---|---|
TIL-231009(자료구조 & 알고리즘 5주차) (0) | 2023.10.09 |
TIL-231006(자료구조 & 알고리즘 4주차) (0) | 2023.10.06 |
TIL-231005(자료구조 & 알고리즘 3주차) (0) | 2023.10.06 |
TIL-231004(자료구조 & 알고리즘 3주차) (0) | 2023.10.04 |