Directed graph란 유방향 간선으로 이루어진 그래프를 의미합니다. 이에 대치되는 개념은 앞선 시간에서 살펴보았던 undireced graph, 즉 무방향 간선으로 이루어진 그래프입니다. Directed graph에서 간선 정리 Undirected graph에서 그래프 탐색을 할 때는 DFS의 경우 unvisited, discovery, back edge의 3가지 간선 종류가 있었고, BFS의 경우에는 unexplored, discovery, cross edge의 3가지 간선 종류가 있었습니다. Directed graph의 탐색된 간선은 4가지가 있는데, 이를 정리해 보도록 하겠습니다. 정점 v에서 시작하여 DFS와 BFS 등으로 탐색된 경로가 정점 v를 루트로 하는 트리와 같은 형식이라는 것을 ..
Breadth First Search(BFS)는 그래프 탐색 방식중 하나이다. BFS는 시작 정점을 기준으로 가까운 정점부터 차례대로 방문하는 방식이다. 이런 특성을 통하여 가중치가 없는 간선 그래프에서 가장 가까운 경로를 발견할때 사용할 수 있다. 구현 시작 정점 v에서 출발하고, 큐 Q에 시작 정점을 추가하고 VISITED 상태로 만든 후 다음 과정을 반복한다. 1. Q가 비었다면 종료한다. 정점이 있다면 해당 정점 v에 대하여 다음을 실행한다 2. v에 인접한 정점중 UNVISITED인 정점을 큐에 삽입하고, VISITED상태로 변경한다. 용어 unvisited vertex: 아직 방문하지 않은 정점 visited vertex: 방문한 정점 unexlored edge: 아직 방문하지 않은 간선 di..
Depth First Search(DFS)는 그래프 탐색 방식중 하나이다. DFS의 방식은 분기점이 생겼을시, 우선 무시하고 한 방향의 끝에 다다를때 까지 진행한 후, 하나의 경로를 완전히 탐색했으면, 분기점으로 돌아가 분기점을 탐색하는 방식이다. 구현 시작 정점 v에서 출발하여, 다음과 같은 과정을 거친다. 1. 현재 정점이 VISITED라면 재귀를 종료하고 다시 돌아가기 2. 현재 정점을 VISITED로 설정(중복 방문을 막기 위하여) 3. 연결되어 있는 다른 정점 탐색 4. 연결된 모든 다른 정점에 대하여 해당 알고리즘 반복 용어 unvisited vertex: 아직 방문하지 않은 정점 visited vertex: 방문한 정점 unvisited edge: 아직 방문하지 않은 간선 discovery ..
그래프는 정점과 간선의 집합으로 이루어진 자료구조이다. 정점(vertex)는 노드(node)라고도 부른다. 간선(edge)는 정점의 쌍으로 표현되는데, 간선을 통해서 정점 사이를 이동할 수 있다. 이때 간선에 방향이 존재하면 directed edge, 존재하지 않으면 undirected edge라고 하는데, 모든 간선이 directed edge인 그래프를 directed graph, 모든 간선이 undirected edge인 그래프를 undirected graph라고 한다. 용어 directed edge: 방향이 존재하는 간선. undirected edge: 방향이 존재하지 않는 간선. directed graph: 모든 간선이 directed edge인 그래프. undirected graph: 모든 간선..
해시 테이블(Hash table) 해시 테이블은 해시 함수를 이용하는 자료구조로 dictionary의 기능을 한다. 기본적인 원리는 적당한 크기의 공간(배열)을 할당해 두고, 특정 키 x로 접근할 시에 해당 키를 해싱하여 나온 값 h(x)를 배열의 인덱스로 이용하여 배열을 즉시 탐색하는 방식이다. 이진 탐색 트리와의 비교 해시 테이블은 맵 자료구조를 만들 때 유용한데, 이전에 소개한 이진 탐색 트리가 O(h)에 접근이 가능한 것과 달리 O(1)에 접근이 가능하다. 그러나 이진 탐색 트리는 범위를 두고 쿼리가 가능한 반면, 해시 테이블은 정확한 키값을 지정해 줘야 탐색이 가능하다. 공간 면에서도 이진 탐색 트리는 당장 필요한 만큼의 공간을 사용하지만, 해시 테이블은 사용할 공간을 에측해서 미리 할당해 두어..
이전 시간에 살펴보았던 이진탐색트리는 O(h)의 시간 복잡도를 가지기에, 높이의 균형을 유지하여야 O(log n)의 효율을 유지할 수 있었다. 이렇게 밸런스를 유지하는 방법으로는 height-balanced와 weight-balanced의 방식이 있는데 그중 height-balanced 트리는 대표적으로 AVL 트리와 레드-블랙 트리가 존재한다. 이번 글에서는 이 중 AVL 트리에 대해서 다루어 보려 한다. AVL 트리 AVL 트리의 정의는 모든 노드 v에 대하여 v 양옆의 자식들의 높이(height) 차이가 1 이하인 이진탐색트리를 의미한다. AVL트리의 효율 증명 이러한 방식으로 AVL트리를 제작했을 때 이 효율이 O(log n)인 것의 증명을 서술...나중에 한다. ADT search(key) in..
이진 탐색 트리는 이진트리로서, 중위순회(In-order traversal) 시 정렬된 형태라는 특징을 가지고 있다. ADT lookup(key): key값을 가지는 노드를 리턴하고, 없다면(NULL일시) NULL의 부모를 리턴한다 put(key): key값을 가지는 노드에 삽입한다. delete(key): key값을 가지는 노드를 삭제한다. 구현 이진탐색트리 구현의 핵심은 계속 중위순회순으로 정렬된 상태를 유지하는 것이다. 탐색 루트에서 시작해서 노드의 값이 탐색값보다 크면 left child로 탐색, 작으면 right child로 탐색을 반복하면 된다. 삽입 삽입은 탐색을 한 후 값을 변경하거나 추가만 해주니 단순하다. 경우를 나누어 보자면, 탐색하여 노드를 발견했다면 그대로 값을 수정하면 되고, 값..
맵 & 딕셔너리(Map & Dictionary) 맵과 딕셔너리는 매우 유사한 자료구조다. 이에 맵에 대해서 먼저 설명하고, 맵과 딕셔너리의 차이점을 알아보겠다. 우선 맵은 키-값(key-value) 쌍으로 이루어진 집합이다. 키를 통해서 값을 추가, 탐색하고 이를 수정, 삭제할 수 있다. 이때 맵의 특징은 같은 키를 가지는 여러 값이 존재할 수 없다는 것이다. 그렇다면 딕셔너리는 무엇일까? 딕셔너리는 기본적으로 맵과 동일하지만, 중복된 키값이 존재할 수 있다는 특징이 있다. 다만 실제로 맵과 딕셔너리의 차이를 엄밀하게 다들 지키는 것은 아니고, 반대의 의미로 쓰이거나 하여 사실상 같은 의미를 가진다고 볼 수 있다. 예를 들어 파이썬의 딕셔너리는 기본적으로 키 중복을 허용하지 않지만 딕셔너리(dict)라는..
힙(Heap) 힙은 완전 이진 트리(Complete binary tree)의 형태를 가집니다. 즉, 완전 이진 트리의 성질에 따라 트리의 높이 h arr[idx]) { swap(parent, idx); upHeap(parent); } } void downHeap(int idx) { int left = 2 * idx; int right = 2 * idx + 1; int child; if (left > getSize()) return; else if (left == getSize()) child = left; else { if (arr[left]
우선순위 큐에 대해 소개하기 전에 ADT(Abstract Data Type)와 implementation(구현 방법)의 차이에 대해서 잠시 다시 짚어보겠습니다. ADT(자료구조) Implementation(구현 방법) List Array, Linked list Stack Array, Linked list Queue Array, Linked list Tree Linked structure Binary tree Array, Linked structure Priority queue Heap, Binary search tree, List 위와 같이 각 자료구조는 여러가지의 구현 방법이 있을 수 있습니다. 또한 다른 자료구조 자체도 다른 자료구조의 구현 방법이 될 수 있습니다. 이를 여기서 다시 짚어보는 이유는 ..
