🌱 그리디 알고리즘
합리적인 시간 내에 최적에 가까운 답을 찾는 매우 실용적인 알고리즘입니다. 최적해를 찾기도 하고 대부분은 정답을 근사하게 찾는 용도로 활용되고 속도가 매우 빠릅니다. 활용 가능한 문제로는 최적 부분 구조와 탐욕 선택 속성이 있습니다. 최적 부분 구조는 문제의 최적 해결 방법이 부분 문제의 최적 해결 방법으로 구성되는 경우이고, 탐욕 선택 속성은 앞의 선택이 이후 선택에 영향을 주지 않는 것을 말합니다. 따라서, 그리디 알고리즘은 선택을 다시 고려하지 않는 특징이 있습니다.
Ex) 다익스트라 알고리즘, 허프만 코딩 알고리즘에서 허프만 트리를 빌드할 때, 분할 가능 배낭 문제(짐을 쪼갤 수 있는 경우),
머신러닝 분야에서 의사결정 트리 알고리즘으로 유명한 ID3 알고리즘
🌱 다익스트라 알고리즘
그래프에서 한 정점에서 다른 정점까지의 최단 경로를 구하는 알고리즘입니다. 특징으로 음수 경로에는 사용할 수 없습니다. 최단 경로 테이블을 두고 방문 여부 boolean 값과 연결된 노드 중 최솟값을 찾는 식으로 최단 경로 테이블을 채워나갑니다. 이 과정을 반복하면 최종적으로 테이블에 각 노드까지 최단 경로 값이 들어가게 됩니다. 또한, 이것은 그리디 알고리즘이나 다이나믹 프로그래밍으로 풀이가 가능합니다.
🌱 정렬
🌿 버블 정렬
인접한 2개의 값을 비교하여 오름차순 혹은 내림차순으로 스왑하는 식으로 1회전하는 정렬 방식입니다. N번의 라운드를 거치고 N번 비교하기 때문에 시간 복잡도는 항상 O(n2)입니다. 스왑 여부를 확인하는 식으로 구현하면 n2보다 좀 더 최적화할 수 있지만 그럼에도 다른 알고리즘보다 느립니다.
def bubblesort(A):
for i in range(1, len(A)):
for j in range(0, len(A) - 1):
if A[j] > A[j + 1]:
A[j], A[j + 1] = A[j + 1], A[j]🌿 병합 정렬
배열을 쪼갤 수 없을 때까지 분할한 후, 다시 조합하는 과정에서 순서를 맞추어 최종 결과를 만들어내는 정렬로 분할 정복 방식입니다. 최선과 최악 모두 O(nlogn)인 사실상 완전한 θ(nlogn) 으로 일정한 알고리즘입니다.
대부분의 경우 퀵 정렬보다는 느리지만 일정한 실행 속도뿐만 아니라 중복된 값을 입력 순서와 동일하게 정렬하는 안정 정렬이라는 점에서 여전히 상용 라이브러리에서 많이 쓰이고 있습니다.
def mergesort(A):
if len(A) < 2:
return A
mid = len(A) // 2
low = mergesort(A[:mid])
high = mergesort(A[mid:])
merged_A = []
l, h = 0, 0
while l < len(low) and h < len(high):
if low[l] < high[h]:
merged_A.append(low[l])
l += 1
else:
merged_A.append(high[h])
h += 1
merged_A += low[l:]
merged_A += high[h:]
return merged_A🌿 퀵 정렬
피벗을 기준으로 좌우를 나누는 파티션 교환 정렬으로 병합 정렬과 같은 분할 정복 알고리즘입니다. 피벗이라는 개념을 통해 피벗보다 작으면 왼쪽, 크면 오른쪽으로 파티셔닝하면서 쪼개 나갑니다. 이렇게 피벗을 통해 쪼개진 아이템들을 각각 재귀를 돌려 퀵 정렬을 반복하여 최초 입력된 좌우 위치가 역전되지 않을 때까지 반복하는 정렬 방법입니다. 평균 시간 복잡도는 O(nlogn)입니다.
기대 결과와 반대로 정렬된 배열이 들어오거나 중복 값이 많은 최악의 경우 O(n2)이 됩니다. 항상 일정한 성능을 보이는 병합 정렬과 달리, 퀵 정렬은 이처럼 입력값에 따라 성능 편차가 심한 편(불안정 정렬)입니다. 하지만 피벗을 선택하는 알고리즘을 개선해 좀 더 최적화하는 방법으로 개선할 수 있습니다.
def quicksort(A, l, h):
def partition(l, h):
pivot = A[h]
left = l
for right in range(l, h):
if A[right] < pivot:
A[left], A[right] = A[right], A[left]
left += 1
A[left], A[h] = A[h], A[left]
return left
if l < h:
pivot = partition(l, h)
quicksort(A, l, pivot - 1)
quicksort(A, pivot + 1, h)📌 퀵 정렬의 최적화 방법
중복 값의 경우 피벗보다 작은 값, 같은 값, 큰 값 3개의 블럭으로 파티셔닝하는 방법이 있고, Hoare 분할 방식이 있습니다. 이것은 반전을 감지할 때까지 서로를 향해 달려가는 2개의 인덱스를 사용하여 두 인덱스가 서로 만나면 알고리즘이 중단되고 최종 인덱스를 반환하는 방식입니다. 이 방식은 평균적으로 3배 더 적은 스왑을 수행하기 때문에 로무토의 방식보다 평균적으로 좋은 성능을 보입니다.
🌿 삽입 정렬
2번째 값부터 시작하여 해당 값을 1번째 값부터 비교하여 들어갈 위치를 찾으면 해당 위치에 값을 넣고 나머지 원소는 밀어내는 정렬 방식입니다. 시간 복잡도는 최고 O(n)이고 평균과 최악의 경우는 O(n2)으로 같습니다.
# ListNode
def insertionSortList(head):
cur = parent = ListNode(0)
while head:
# 탐색
while cur.next and cur.next.val < head.val:
cur = cur.next
# swap + head -> head.next
cur.next, head.next, head = head, cur.next, head.next
# head.val가 자신보다 클 경우 cur을 옮길 필요가 없음
if head and cur.val > head.val:
cur = parent
return cur.next🌿 선택 정렬
오름차순의 경우 최솟값을 리스트에서 찾아 가장 앞에 넣고 그 값을 제외한 나머지 값 중 다시 최솟값을 찾아 2번째 위치에 넣는 식으로 정렬하는 알고리즘입니다. 해당 정렬은 n라운드 수행하고 반복문이 2개 들어가므로 시간 복잡도가 항상 O(n2)이 됩니다.
def selectionsort(list):
for i in range(len(list)):
min = list[i]
for j in range(i + 1, len(list)):
if min > list[j]:
min = list[j]
idx = list.index(min)
list[i], list[idx] = list[idx], list[i]
return list