원형 리스트 연결 리스트의 꼬리 노드가 다시 머리 노드를 가리키는 모양입니다. 이중 연결 리스트 연결 리스트는 next 필드를 통해 뒤쪽 노드를 찾기는 쉬운 반면, 앞쪽 노드를 찾기 어렵습니다. 이 단점을 개선한 이중 연결 리스트는 뒤쪽 노드에 대한 포인터 뿐만 아니라 앞쪽 노드에 대한 포인터를 포함합니다. 원형 이중 연결 리스트 위 두 개념을 합친 연결 리스트입니다. 노드는 다음과 같이 앞쪽 포인터와 뒤쪽 포인터를 포함합니다. class Node: """원형 이중 연결 리스트용 노드 클래스""" def __init__(self, data: Any = None, prev: Node = None, next: Node = None) -> None: """초기화""" self.data = data self.p..
자료구조
배열로 구현한 연결 리스트의 한계 [a, b, c, d]의 배열에서 a와 b 사이에 e을 삽입한다면 c, d를 하나씩 뒤로 이동해야합니다. 삭제하는 경우에도 마찬가지로 데이터를 옮겨야 하므로 효율적이지 않습니다. 파이썬의 연결 리스트 연결 리스트는 임의의 위치에 원소를 삽입하거나 삭제할 때 빠르게 수행할 수 있다는 장점이 있지만, 메모리와 속도 면에서는 배열보다 효율이 떨어집니다. 파이썬의 리스트는 이러한 연결 리스트의 자료구조가 아니라 모든 원소를 연속으로 메모리에 배치하는 '배열'로 내부에서 구현하고 있습니다. 그러므로 속도가 급격히 떨어지지는 않습니다. 또 원소를 하나씩 추가/삽입 시 내부에서 메모리를 해제하거나 확보하지 않습니다. 실제 필요한 메모리보다 여유 있게 미리 마련하기 때문입니다. 포인터..
일반적으로 파이썬에서 문자열 검색을 하려면 표준 라이브러리(in, not in)를 사용하는 것을 추천하지만, 사용하지 않는다면 브루트 포스법이나 보이어-무어법을 사용하는 경우가 많습니다. 보이어-무어법 KMP법보다 효율적이어서 실제 문자열 검색에서 널리 사용됩니다. 패턴의 끝 문자에서 시작하여 앞쪽을 향해 검사를 수행합니다. 이 과정에서 일치하지 않는 문자를 발견하면 미리 준비한 표를 바탕으로 패턴이 이동하는 값을 결정합니다. ① ABCXDEZCABACABAC에서 ABAC를 검색하는 과정 ② 텍스트와 패턴의 첫 문자를 위아래로 나란히 놓고 패턴의 마지막 문자 C에 집중합니다. X는 패턴 안에 포함되어 있지 않습니다. 패턴을 오른쪽으로 한칸씩 이동해도 말이죠. ③ 한번에 오른쪽으로 4칸을 밀어서 다음과 같..
브루트 포스법 전수 공격법으로, 문자열에 맞는 모든 경우의 수를 다 체크하는 방식입니다. 전체 문자열과 찾는 대상 문자열, 두 문자열의 검색 위치를 잡아주는 pt, pp 변수를 선언하고 확인해나갑니다. def bf_match(txt: str, pat: str) -> int: pt = 0# txt를 따라가는 커서 pp = 0# pat를 따라가는 커서 while pt != len(txt) and pp != len(pat): if txt[pt] == pat[pp]: pt += 1 pp += 1 else: pt = pt - pp + 1 pp = 0 return pt - pp if pp == len(pat) else -1 ① ABABCDEF 에서 ABC 검색 ② pt = 2, pp = 2 까지 증가 ③ txt[p..
병합 정렬 배열을 앞부분 A 배열과 뒷부분 B 배열의 두 그룹으로 나누어 각각 정렬한 후 병합하는 작업을 반복하는 알고리즘입니다. 각 배열에서 주목하는 원소의 값을 비교하여 작은 쪽의 원소를 꺼내 새로운 배열 C에 저장합니다. 정렬을 마친 두 A, B 배열을 병합하는 코드입니다. def merge_sorted_list(a: Sequence, b: Sequence, c: MutableSequence) -> None: """정렬을 마친 배열 a와 b를 병합하여 c에 저장""" pa, pb, pc = 0, 0, 0 na, nb, nc = len(a), len(b), len(c) while pa < na and pb < nb: if a[pa] < b[pb]: c[pc] = a[pa] pa += 1 else: c..
힙 정렬 힙은 '부모의 값 ≥ 자식의 값'인 관계가 항상 성립하는 완전 이진 트리입니다. 모든 자식의 노드가 2개인 트리 구조라는 것입니다. 이때 부모의 값이 자식의 값보다 항상 작아도 힙입니다. 즉, 이러한 두 값의 대소관계가 일정하면 됩니다. 힙은 부모-자식 관계는 일정하지만, 형제 사이의 관계는 일정하지 않습니다. 아래 그림과 같이 7이 6보다 왼쪽에, 5와 4가 3과 2보다 왼쪽에 있지만, 아래 2와1보다 큰 3이 오른쪽에 있는 것처럼 말입니다. 이러한 이유로 부분 순서 트리라고도 합니다. 힙 정렬에서 배열의 인덱스는 다음과 같습니다. 이러한 순서로 배열을 힙에 저장하면 부모, 오른쪽 자식, 왼쪽 자식과는 다음과 같은 관계가 성립합니다. 원소 a[i] ① 부모: a[(i - 1) // 2] ② 왼..
도수 정렬 원소의 대소 관계를 판단하지 않고 빠르게 정렬하는 알고리즘으로, 다음과 같은 과정을 통해 if 문을 사용하지 않고 for 문만 반복해서 정렬할 수 있습니다. 비교/교환 작업이 필요 없어 매우 빠르지만, 데이터의 최솟값과 최댓값을 미리 알고 있는 경우에만 적용할 수 있습니다. ① 도수 분포표 만들기 ② 누적 도수 분포표 만들기 ③ 작업용 배열 만들기 ④ 배열 복사 도수 분포표 만들기 각 학생의 점수를 나타내는 배열 a가 있습니다. [5, 7, 0, 2, 4, 10, 3, 1, 3] (e.g. a[0]은 5점) 이때 0~10점을 나타내기 위한 원소 수 11개인 배열 f를 만듭니다. 그리고 각각 그 값을 넣어줍니다. for i in range(n): f[a[i]] += 1 도수 분포표 배열 [1, ..
셸 정렬 셸 정렬은 단순 삽입 정렬에서 특정 원소를 삽입할 위치가 멀리 떨어져 있으면 이동 횟수가 많아지는 단점을 보완한 정렬 알고리즘입니다. 비교하는 횟수를 확 줄인 알고리즘이죠. 배열 [8, 1, 4, 2, 7, 6, 3, 5]를 셸 정렬로 정렬하는 예시입니다. 먼저 서로 4칸씩 떨어진 원소를 꺼내어 (8, 7), (1, 6), (4, 3), (2, 5)의 4개의 그룹으로 나눈 후 각자 따로 정렬합니다. 그럼 다음과 같이 [7, 1, 3, 2, 8, 6, 4, 5]가 됩니다.(4-정렬) 다음은 2칸 떨어진 원소를 모두 꺼내 (7, 3, 8, 4), (1, 2, 6, 5) 두 그룹으로 나누고, 각각 정렬을 수행합니다.(2-정렬) 마지막으로 1칸 떨어진 배열, 즉 배열 전체에 단순 삽입 정렬을 적용하면 ..
단순 선택 정렬 단순 선택 정렬이란 가장 작은 원소부터 선택해 알맞은 위치로 옮기는 작업을 반복하며 정렬하는 알고리즘입니다. 아직 정렬하지 않은 부분에서 값이 가장 작은 원소 a[min]을 선택하고, 정렬하지 않은 부분의 맨 앞 원소와 교환합니다. def selection_sort(a: MutableSequence) -> None: n = len(a) for i in range(n - 1): min = i for j in range(i+1, n): if a[j] < a[min]: min = j a[i], a[min] = a[min], a[i] 예시: [6, 4, 1, 7, 3, 9, 8] ① 먼저 배열에서 가장 작은 원소와 아직 정렬하지 않은 부분(배열 전체)의 첫번째 원소와 교환합니다. → [1, 4,..
버블 정렬 이웃한 두 원소의 대소 관계를 비교하여 필요에 따라 교환을 반복하는 알고리즘입니다. 아래 예시처럼 n개 원소의 배열에서 처음 교환 과정(패스)에서는 비교 횟수가 n - 1회, 다음 패스에서는 비교 횟수가 n - 2회로 최종적으로 시간 복잡도는 O(n^2)입니다. from typing import MutableSequence def bubble_sort(a: MutableSequence) -> None: n = len(a) for i in range(n - 1): for j in range(n-1, i, -1): if a[j-1] > a[j]: a[j-1], a[j] = a[j], a[j-1] 처음에는 이 코드가 이해가 되지 않았는데, 우측의 a[j-1], a[j]를 (a[j-1], a[j]) ..
