이번 포스트에서는 알고리즘 중의 AOV/AOE 네트워크에 대해 다루겠다. AOV 네트워크란? : AOV는 Activity On Vertex의 약자이다. 즉, 정점이 Activity, 작업을 나타내고, 간선이 작업간의 우선순위 관계를 나타내는 방향 그래프이다. AOV 동작 과정 스택 [0], 위상 순서 [] 스택 [3, 2, 1], 위상 순서 [0] (1, 2, 3번 노드의 선행 노드 0이 사라졌으므로 스택에 저장) 스택 [2, 1], 위상 순서 [0, 3] 스택 [5, 1], 위상 순서 [0, 3, 2] 스택 [1], 위상 순서 [0, 3, 2, 5] 스택 [4], 위상 순서 [0, 3, 2, 5, 1] 스택 [], 위상 순서 [0, 3, 2, 5, 1, 4] AOE 네트워크란? : AOE는 Activi..

이번 포스트에서는 그래프 중의 최소비용 신장 트리 알고리즘에 대해 다루겠다. 최소비용 신장 트리 알고리즘의 제약 조건 : 그래프 내에 존재하는 edge들만 사용 n - 1개의 edge만 사용 Cycle을 형성할 수 있는 edge는 사용 불가 최소비용 신장 트리 알고리즘 (모두 greedy method 사용) : Kruskal Prim Sollin Kruskal 알고리즘이란? 한 번에 하나의 edge씩 추가하면서 최소비용 트리 T를 생성 Edge들을 비용의 오름차순으로 정렬한 후, 가장 비용이 적은 edge부터 선택(greedy) 선택된 edge는 기존에 선택된 edge들과 사이클을 형성하지 않을 경우에만 T에 포함 그래프 G가 연결되었으며, n > 0개의 vertex가 존재할 경우, 정확히 n - 1개의..

이번 포스트에서는 깊이 우선 탐색(DFS) 알고리즘에 대해 다루도록 하겠습니다. 깊이 우선 탐색(DFS)란? : 루트 노드(혹은 임의의 노드)부터 시작하여 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법입니다. 즉, 넓게 탐색하기 전에 깊게 탐색하는 것입니다. 깊이 우선 탐색의 특징 : 재귀 알고리즘이다. 모든 형태의 트리 순회(traversals)는 깊이 우선 탐색의 종류이다. 어떤 노드를 방문했는지를 반드시 검사한다. 더 이상 방문할 노드가 없으면 이전 노드로 backtracking(다시 돌아가서 탐색하지 않은 정점이 있는지 확인) 깊이 우선 탐색의 동작 과정 : V0부터 시작해서 V0 방문 V0과 인접한 V1 방문 V1과 인접한 V3 방문 V3과 인접한 V7 방문 V7과..

이번 포스트에서는 너비 우선 탐색(BFS) 알고리즘에 대해 다루도록 하겠습니다. 너비 우선 탐색(BFS)이란? : 루트 노드(혹은 임의의 노드)부터 시작해서 인접한 노드를 먼저 탐색하는 방법입니다. 즉, 깊게 탐색하기 전에 넓게 탐색하는 것입니다. 너비 우선 탐색의 특징 : 재귀적으로 동작하지 않는다. 방문한 노드들을 차례대로 저장한 후 꺼낼 수 있는 자료 구조인 큐(Queue)를 사용한다. 어떤 노드를 방문했는지를 반드시 검사한다. 너비 우선 탐색의 동작 과정 : 초기 상태의 큐에는 시작 노드만 저장. (Q = [0]) 큐에서 노드를 꺼내서 방문 및 인접 노드를 큐에 삽입 -> V0 방문 (Q = [1, 2]) 더 이상 삽입할 인접한 노드가 없다면 dequeue 실행 (큐의 맨 앞에서 노드를 꺼낸다) ..

이번 포스트에서는 그래프의 표현법인 인접 행렬과 인접 리스트에 대해 다루도록 하겠습니다. 인접 행렬(Adjacency Matrix)란? : 그래프의 연결 관계를 2차원 배열로 나타내는 방식입니다. A[u][v]라는 인접 행렬이 있다고 가정하면, 노드 u에서 노드 v로 가는 간선이 있다면 1, 없다면 0으로 표현할 수 있습니다. 인접 행렬의 예시 : 무방향성 그래프: A[][]는 대칭 행렬 (이때, A[n(n-1)/2]로 구현 가능) 방향성 그래프 : A[][]는 비대칭 행렬 장점 : 구현이 쉽다 단점: 복잡도 = O(n의 2승) 인접 리스트(Adjacency List)란? : n개의 정점(vertex)을 각각에 대해 인접한 정점들의 리스트로 만드는 것입니다. 즉, 그래프 G의 각 정점에 대해 한 개의 연..

이번 포스트에서는 자료구조 상의 그래프(Graph)에 대해 다루도록 하겠습니다. 그래프란? : 그래프는 2개의 집합 V와 E로 구성됩니다. 이때 V는 공집합이 아닌 정점(vertex)의 유한 집합이고 E는 간선(edge)들의 집합입니다. 그래프의 특징 : 2개이상의 경로가 가능하다. 루트 노드라는 개념이 없다. 부모-자식 관계라는 개념이 없다. 그래프에 사용되는 용어 : 정점(vertex) : 위치라는 개념 간선(edge) : 위치 간의 관계, 즉 노드를 연결하는 선 완전 그래프(Complete graph) : 간선의 수가 최대인 그래프 인접(adjacent) : 간선에 의해 직접 연결된다 부분 그래프(Subgraph) : V(G')⊆V(G)이고 E(G')⊆E(G)일 경우, G'는 G의 부분 그래프 경로..

이번 포스트에서는 자료구조의 힙(Heap)에 대해 다루도록 하겠습니다. 힙이란? : 완전 이진 트리 구조의 일종으로 우선순위 큐를 위해 만들어진 자료구조입니다. 힙의 종류 : 최대 힙 (Max Heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 (부모 key ≥ 자식 key) 최소 힙 (Min Heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 (부모 key ≤ 자식 key) 최대 힙(Max Heap)의 추가 및 삭제 : 최대 힙 추가 소스 코드 : void push_max_heap(element item, int *n) { int i; if (HEAP_FULL(*n)) { fprintf(stderr, "The heap is full..

이번 포스트에서는 이진트리의 순회에 대해 다루도록 하겠습니다. 이진 트리 순회란? : 트리에 있는 모든 노드를 한 번씩만 방문하는 것입니다. 또한 한 노드가 방문될 때 어떤 연산이 그 노드에 대해 수행됩니다. 만일 L, V, R이 한 노드에서 각각 왼쪽으로 이동, 노드 방문, 오른쪽으로 이동하는 것을 나타낸다면 LVR, LRV, VLR, VRL, RVL, RLV 등 6개의 순회 방법이 있을 수가 있습니다. 이진 트리 순회의 종류 : (1) Inorder (중위 순회, LVR) : 더 이상 진행할 수 없을 때까지 왼쪽 방향으로 이동하여 내려간 다음, 그 노드를 방문하고 오른쪽 자식 노드로 이동한 뒤 계속합니다. 이때 오른쪽으로 이동할 수 없을 때에는 한 노드 뒤로 되돌아갑니다. 소스 코드 : void in..

이번 포스트에서는 이진 트리에 대해 다루도록 하겠습니다. 트리란? : 트리는 1개 이상의 노드로 이루어진 유한 집합으로서 큐나 스택과 같은 선형 구조가 아닌 비선현 자료구조입니다. 트리의 특징 : 하나의 루트 노드를 가진다. 모든 노드는 0개 이상의 자식 노드를 가진다. 노드의 서로간을 연결하는 간선(Edge)이 존재한다. 트리에 관한 용어 정리 : 노드의 차수(degree) : 자식 노드의 개수 (A : 3) 트리의 차수(degree of tree) : 트리의 최대 차수, 즉 제일 많은 가짓수 (3) 단말 노드(leaf of terminal node) : 자식이 없는 노드 (K, L, F, G, M, I, J) Parent : 부모 노드 (E : B, B : A) Children : 자식 노드 (B :..