Computer Science/Data Structures11 9. Graph Graph란? 그래프는 정점(vertex)들과 정점들을 잇는 간선(edge)으로 이루어진 자료구조이다. 예를 들어 위와 같은 그래프는 5개의 정점과 6개의 간선으로 이루어진 그래프이다. 그렇다면 이렇게 정점과 간선의 정보를 어떻게 저장해야 할까. 그래프는 크게 인접 리스트(Adjacency List) 형태나 인접 행렬(Adjacency Matrix) 형태로 구현된다. Adjacency List 인접 리스트는 각각의 정점마다 리스트를 할당하고, 해당 정점과 연결된 정점을 리스트에 저장함으로써 간선 정보를 저장한다. 인접 리스트를 사용할 경우 간선의 갯수만큼만 공간을 할당하여 메모리를 절약할 수 있으나, 연결되어 있지 않은 정점 두개의 연결 여부를 확인하려면 정점의 모든 간선을 찾아봐야 한다는 단점이 있다... 2020. 5. 29. 8. Hash Table Hash Table 데이터를 저장할 때 key 값을 사용하여 저장하면 데이터를 찾을 때 맞는 key 값을 찾는 탐색 과정이 필요하다. 따라서 데이터가 많아질수록 key 값을 위한 탐색 과정이 길어져 느려지게 된다. 이 때문에 key 값을 통해 바로 데이터의 위치를 알 수 있는 방법을 사용하게 된다. key 값에 특정한 산술 연산을 하여 데이터의 주소를 얻어 데이터에 접근하게 되며, 이 과정을 Hashing 이라고 한다. Hash Table은 hashing을 통해 데이터를 저장하는 dictionary를 말한다. Hash Function hash table에서는 hash function을 통해 key 값을 일정 범위 내의 integer 값으로 변환하여 저장한다. 따라서 hash function은 어떤 형식으.. 2020. 5. 29. 7. AVL Tree AVL Tree란? BST(Binary Search Tree, 이진 탐색 트리)는 검색, 삽입, 삭제에 모두 O(h)의 시간이 소요된다. 6. Binary Search Tree Binary Search Tree란? Binary Search Tree(BST, 이진 탐색 트리)는 다음과 같은 조건을 만족하는 이진 트리를 말한다. 노드 L을 left child, 노드 R을 right child로 갖는 노드 A가 있을 때, key(L) ≤ key(A).. ju-hy.tistory.com BST의 높이는 데이터의 삽입 순서에 따라 매우 높아질 수 있고 이는 BST의 효율을 낮추는 원인이 된다. 이 때문에 BST를 사용하면서 높이를 최소화하는 방법이 고안되게 되었다. 높이를 최소화하기 위해서는 트리의 left와 r.. 2020. 5. 28. 6. Binary Search Tree Binary Search Tree란? Binary Search Tree(BST, 이진 탐색 트리)는 다음과 같은 조건을 만족하는 이진 트리를 말한다. 노드 L을 left child, 노드 R을 right child로 갖는 노드 A가 있을 때, key(L) ≤ key(A) ≤ key(R)을 만족한다. 즉, 모든 노드의 key 값은 left child의 key 값보다 크거나 같고, right child의 key 값보다 작거나 같다. 따라서 BST를 inorder traversal(전위 순회)를 통해 탐색하면 key 값이 작은 순서대로 방문하게 된다. Search BST에서 원하는 key 값을 찾으려면 다음과 같은 작업을 반복하면 된다. 찾으려는 노드를 T, 현재 방문중인 노드를 C라고 했을 때 key(T)k.. 2020. 5. 22. 5. Map & Dictionary Map이란? Map은 key-value 형태로 데이터를 저장하는 자료구조이며, key 값을 통해서 데이터를 검색, 저장, 삭제한다. 이 때, map은 중복된 key 값은 허용되지 않는다. 예를 들어, 전화번호부의 경우 같은 전화번호에 여러 이름은 저장되지 않는다. 따라서 전화번호를 key 값으로, 이름을 value로 map에 저장하면 된다. Dictionary란? Dictionary는 기본적으로 map과 같이 key-value 형태로 데이터를 저장하지만, map과 달리 중복된 key 값이 허용된다. 예를 들어 단어 사전의 경우 하나의 단어에 여러 가지 뜻이 있을 수 있다. 따라서 단어를 key 값으로, 단어의 뜻을 value로 dictionary에 저장하면 된다. 그렇다면 List를 기반으로 Map을 구.. 2020. 5. 22. 4. Priority Queue & Heap Priority Queue란? Queue의 경우 먼저 들어간 데이터가 먼저 나오게 된다. Priority Queue는 이와 다르게 들어간 순서와는 상관없이 우선순위가 높은 데이터가 먼저 나오게 된다. 그렇다면 Priority Queue를 어떻게 구현해야 할까? 첫번째, 배열로 구현하여 삽입 시마다 우선순위에 맞게 정렬한다. 이 방법은 항상 정렬된 형태를 유지하기 때문에 데이터를 꺼낼 때 용이하지만, 삽입 시 O(n)의 시간이 필요하다. 두번째, 리스트로 구현하여 데이터를 불러올 때 우선순위가 높은 데이터를 찾는다. 이 방법은 삽입 시 상수 시간이 걸려 용이하지만, 데이터를 꺼낼 때마다 O(n)의 시간이 필요하다. 이처럼 배열과 리스트로 Priority Queue를 구현하면 이와 같이 데이터 삽입이나 요청.. 2020. 5. 22. 3-2. Tree Traversal Tree의 노드들을 탐색하는 데에는 여러 가지 방법이 있다. 기본적으로 노드를 방문하는 순서에 따라 preorder, postorder, inorder traversal이 있고, 이 외에도 level-order traversal, Euler tour traversal 등 여러 가지 순회 방식이 있다. 하나씩 순회 과정을 살펴보자. Preorder Traversal (전위 순회) 전위 순회는 현재 노드를 먼저 탐색하기 때문에 붙여진 이름이다. 따라서 1.현재 노드 2. 왼쪽 child 노드부터 차례대로 순으로 방문하게 된다. 실제 위 트리를 예시로 전위 순회를 실행해보자. 먼저 root 노드인 0번 노드를 방문하고, 그 다음으로 left child인 1번 노드를 방문하게 된다. 1번 노드를 방문했다면, 다.. 2020. 5. 21. 3-1. Binary Tree Binary Tree Binary Tree(이진 트리)는 각각의 노드가 최대 2개의 child 노드를 갖는 tree를 말한다. 이진 트리는 노드들이 어떻게 구성되어 있는지에 따라 다음과 같이 부르기도 한다. Full Binary Tree (정 이진 트리) 모든 노드가 0 또는 2개의 child를 갖는 binary tree. Perfect Binary Tree (포화 이진 트리) 모든 internal 노드가 2개의 child를 갖는 binary tree. 모든 leaf 노드가 같은 level에 있다. (Proper Binary Tree라고도 함) Degenerate Tree (변질 트리) 모든 parent 노드가 하나의 child만 갖고 있는 tree. (Pathological Tree라고도 함) Comp.. 2020. 5. 21. 3. Tree Tree Tree의 기본적인 정의는 Circuit이 없고, 서로 다른 두 노드를 잇는 길이 하나뿐인 Graph를 말한다. 따라서 Tree는 Graph의 종류 중 하나이며 다음과 같은 특징을 갖는다. Parent, Child 연결 리스트의 경우 다음 노드 하나를 가리키지만 Tree의 경우 여러 개의 노드를 가리킬 수 있다. 이렇게 가리켜진 노드들을 child 노드라고 하며 가리킨 노드를 parent 노드라고 한다. 예를 들어 4번, 5번 노드는 2번의 child이고, 2번 노드는 4번, 5번 노드의 parent이다. 동시에 5번 노드는 8번 노드의 parent이고, 2번 노드는 0번 노드의 child이다. 이처럼 parent, child 노드는 상대적인 개념이다. 이에 더해 ancestor는 해당 노드의 .. 2020. 5. 18. 이전 1 2 다음
