Passwd

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..