Passwd

우선순위 큐 (Priority Queue) 큐나 스택과 같은 자료 구조 중 하나로, 각 원소가 우선순위를 가지고 있는 것이 특징이다. 우선순위 큐에서 높은 우선순위를 가진 원소가 낮은 우선순위를 가진 원소보다 먼저 처리된다. 우선순위가 같은 원소는 우선순위 큐 내 순서를 기준으로 처리된다. 우선순위 큐 == 힙 (?) 인터넷에 우선순위 큐에 대해 찾다 보면 힙과 함께 정리한 글이 많이 보이는데, 우선순위 큐가 힙이라고 할 수는 없다. 우선순위 큐는 리스트나 맵과 같은 추상적인 개념으로 힙, 배열, 연결 리스트 또는 다른 방식으로 구현할 수 있다. 다만 시간복잡도 등의 이유로 일반적으로 힙으로 많이 구현하는 것 같다. 아래는 우선순위 큐의 구현 방식에 따른 enqueue / dequeue 연산의 시간복잡도..

개요 예전에 Python에서 큐를 다루는 방법을 소개하고자 2021.10.07 - [자료 구조] 회문 찾기 / 큐 & 스택을 작성했었는데, 찾아보니 deque라는 자료구조가 따로 존재해 내용을 적어둔다. 양방향 큐 (deque) Queue는 먼저 저장한 자료를 먼저 빼내는 선입선출(First In First Out; FIFO) 방식의 자료구조다. REAR에서민 자료를 추가하고 FRONT에서만 자료를 삭제하기 때문에 방향을 구분하지 않는다. 반면 양방향 큐(Double-Ended Queue; deque)는 그 이름대로 데이터의 추가와 삭제가 FRONT, REAR 모두에서 이뤄진다. 즉, FIFO나 후입선출(Last In First Out; LIFO)를 따르지 않는다. Deque는 기본적으로 동적 배열을 사..

DAG 비순환 방향 그래프; Directed Acyclic Graph 순환을 포함하지 않은 방향 그래프 \( e = (u, v) \)라면, \( e \)를 \( u \)에서 \( v \)로 가는 변이라고 한다. 꼭짓점 \( v \)는 변 \( e \)의 머리라고 하며, 꼭지점 \( u \)는 변 \( e \)의 꼬리라고 한다. 위상 정렬 Topological Sorting 변 (u, v)들에 대해 u가 v 전에 선행하도록 나열한 꼭짓점의 선행 정렬 즉, 그래프의 방향성을 거스르지 않고 꼭짓점을 나열한 것이다. 아래 그림과 같이 나열한 것은 위상 정렬에 해당하지 않다. 하나의 방향 그래프는 여러 개의 위상 정렬을 가질 수 있다. 꼭짓점의 순서는 왼쪽에서 오른쪽 방향으로 진행한다. 정렬 과정은 아래 그림과 ..

2022.03.18 - 힙 트리 (Heap tree) 글에 이어서, 힙 트리에는 두 가지 종류가 존재한다. 최소 힙 (Min heap) : 부모 노드가 자식 노드보다 작거나 같다. 최대 힙 (Max heap) : 부모 노드가 자식 노드보다 크거나 같다. 형제간에는 대소 관계가 없다. 최소 힙에서는 루트 노드가 최솟값이 되고 최대 힙에서는 루트 노드가 최댓값이 된다. 삽입 연산 트리 끝에 노드를 추가한다. 부모 노드와 대소를 비교한다. 최대 힙인 경우, 추가한 값이 부모 노드보다 크면 자리를 바꾼다. 최소 힙인 경우, 추가한 값이 부모 노드보다 작으면 자리를 바꾼다. 2번을 반복한다. 코드 삽입 연산을 python 코드로 나타내면 아래와 같다. def insert_h(heap, val): heap.appe..

힙 트리 최댓값 또는 최솟값을 빠르게 찾기 위해 고안된 완전 이진트리의 일종 우선순위 큐를 위해 만들어진 자료구조이다. 부모-자식 노드 간의 대소관계가 성립한다는 속성을 만족하며, 일종의 반정렬 상태(느슨한 정렬 상태)를 유지한다. 형제 간의 대소 관계는 없다. 값을 중복하여 저장할 수 있으며, 일반적으로 간단히 heap이라고 말한다. 우선순위 큐 데이터가 우선순위를 가지고 있어, 우선순위가 높은 데이터가 먼저 나가는 우선순위의 개념을 큐에 도입한 자료 구조 배열, 연결 리스트 또는 힙으로 구현할 수 있으며 셋 중에서는 힙으로 구현하는 것이 가장 효율적이다. 구현 힙 트리는 1차원 배열로도 충분히 구현할 수 있다. 조건 루트 노드의 인덱스는 1이다. 0으로 설정하면 부모-자식 간의 대소관계를 표현하기 어..

트리 그래프(Graph)의 일종 스택이나 큐와 같은 선형 구조가 아닌 비선형 자료 구조이다. 계층적 관계를 표현한다. cycle이 없고, 서로 다른 두 노드를 잇는 길이 하나인 그래프를 트리라고 한다. 특징 하나의 루트 노드(root node, 최상위 노드)를 갖는다. 노드 a가 노드 b를 가리킬 때, a를 b의 부모 노드(parent node)라고 한다. b는 a의 자식 노드(child node)라고 한다. 루트 노드는 0개 이상의 자식 노드를 갖는다. 자식 노드는 0개 이상의 자식 노드를 갖는다. 자식 노드가 없는 노드는 잎 노드(leaf node)라고 한다. 잎 노드가 아닌 노드는 내부 노드(internal)라고 한다. 자식 노드는 한 개의 부모 노드를 가진다. 노드와 노드를 연결한 길은 간선(ed..