본문 바로가기

알고리즘49

알고리즘 - 병합 정렬 병합 정렬은 배열을 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘입니다. 먼저, 정렬된 배열 a, b를 반복문을 이용한 단순 병합을 해보겠습니다. 이럴 경우 병합하는데 필요한 시간 복잡도는 O(n)입니다. def merge_sorted_list(a, b, c) -> None: pa, pb, pc = 0, 0, 0 # 각 배열의 커서 na, nb, nc = len(a), len(b), len(c) # 각 배열의 크기 print(f'배열 a: {a}') print(f'배열 b: {b}') while pa None: if left < right: center =.. 2020. 12. 8.
알고리즘 - 퀵 정렬(2) 퀵 정렬을 비재귀적으로도 만들 수 있습니다. 스택을 사용해 만들어보겠습니다. 먼저 사용할 스택 코드입니다. from typing import Any class FixedStack: #고정 길이 스택 클래스 class Empty(Exception): #비어 있는 FixedStack에 팝 또는 피크할 때 내보내는 예외 처리 pass class Full(Exception): # 가득 찬 FixedStack에 푸시할 때 내보내는 예외 처리 pass def __init__(self, capacity: int = 256) -> None: # 스택 초기화 self.stk = [None] * capacity # 스택 배열 self.capacity = capacity # 스택의 크기 self.ptr = 0 # 스택 포인.. 2020. 12. 4.
알고리즘 - 퀵 정렬(1) 퀵 정렬은 가장 빠른 정렬 알고리즘으로 알려져 있으며 널리 사용됩니다. 퀵 정렬은 배열 어느 한 기준(피벗)으로 나누어 두 배열로 만들고 나누어진 배열에서도 기준(피벗)을 잡고 계속해서 두 배열로 나누어 모든 그룹에 원소 하나가 남으면 정렬이 완료됩니다. PC가 기준이고 PL, PR은 각각 왼쪽, 오른쪽 커서입니다. 기준이 6이므로 왼쪽에는 6보다 작은 수, 오른쪽에는 6보다 큰 수를 이동시키면 됩니다. 먼저 5와 8은 정렬 시킬 필요가 없습니다. 다음으로 7과 9인데 둘 다 6보다 커서 정렬을 할 수 없습니다. 이럴 때는 PR이 정렬 가능한 수를 찾을 때까지 왼쪽으로 이동시켜 줍니다. 7과 3은 정렬 가능하므로 3과 7의 차리를 바꿔줍니다. 이번에는 1, 2 두 수 모두 기준인 6보다 큽니다. 6보다 .. 2020. 12. 1.
알고리즘 - 셸 정렬 단순 삽입 정렬의 장점은 살리고 단점을 보완해, 더 빠르게 정렬하는 알고리즘을 셸 정렬이라고 합니다. 셸 정렬은 먼저 정렬할 배열의 원소를 그룹으로 나누어, 각 그룹별로 정렬을 수행합니다. 그리고 정렬된 그룹을 합치는 작업을 반복하여 원소의 이동 횟수를 줄이는 방법입니다. 위와 같이 8개의 원소를 갖는 배열이 있을 때, 단순 삽입 정렬은 1을 맨 앞으로 이동시킬 때 총 7번 이동시켜야 합니다. 셸 정렬을 하면 먼저 서로 4칸씩 떨어진 원소를 꺼내어 4개의 그룹으로 나누고 그룹별로 각각 정렬합니다. (8, 5), (4, 2), (9, 7), (6, 1) --> (5, 8), (2, 4), (7,9), (1, 6) 이렇게 4칸 떨어진 원소를 정렬하는 방법을 4-정렬이라고 합니다. 이어서 2칸 떨어진 원소를 .. 2020. 11. 24.

티스토리툴바