CS/Algorithm 검색 결과

해당 글 9건

[AL] 9. 자료구조 (Trie)

9. 자료구조 (Trie) 트라이(Trie) 구현 방법 1. 트라이(Trie) 1.1. 개념 트라이(Trie) 는 Retireval(탐색) 에서 나온 단어이며, 문자열에서의 검색을 빠르게 해주는 자료구조이다. 만약 정수형에서 BST 를 이용한다면 O(logN) 의 시간만에 검색을 할 수 있다. 하지만 문자열에서 BST 를 사용한다고 할 때, 문자열의 길이가 M 이라면 O(M logN) 의 시간 복잡도를 갖는다. 이 때, 트라이를 이용한다면 O(M) 의 시간만에 원하는 문자열을 검색할 수 있게 된다! 1.2. 예시 우선 문자열 5개 {"blog", "he", "her", "supreme", "superm"} 이 있다고 가정해보자. 트라이는 이때 아래와 같은 트리를 형성하게 된다. 루트 노드가 되는 최상위 ..
CS/Algorithm 2019. 4. 23. 15:00

[AL] 8. 최단 경로 알고리즘

8. 최단 경로 알고리즘 최단 경로(Short Path) 알고리즘 다익스트라(Dijkstra) 알고리즘 플로이드-와샬(Floyd-Warshall) 알고리즘 1. 최단 경로(Short Path) 알고리즘 1.1. 알고리즘의 종류 Single-Source (One-to-All) 하나의 출발 노드로부터 다른 모든 노드까지의 최단 경로 Dijkstra Algorithm 을 사용하여 해결 Single-Destination 모든 노드로부터 하나의 노드까지의 최단 경로 모든 Edge를 뒤집으면 One-to-All 과 동일함 Single-Pair (One-to-One) 하나의 출발 노드로부터 하나의 목적 노드로까지의 최단 경로 시간복잡도에서 One-to-All 보다 비효율적 All-Pair (All-to-All) 모든..
CS/Algorithm 2019. 4. 20. 17:01

[AL] 7. 최소 비용 신장 트리(MST) 알고리즘

7. 최소 비용 신장 트리(MST) 알고리즘 신장 트리 (Spanning Tree) 최소 비용 신장 트리 (MST) Kruskal MST 알고리즘 Prim MST 알고리즘 1. 신장 트리 (Spanning Tree) 1.1. Spanning Tree 그래프 내의 모든 정점을 포함하는 트리 Spanning Tree는 그래프의 최소 연결 부분 그래프 이다 트리의 특수한 형태로 모든 정점들이 연결되어 있고 사이클은 존재하지 않는다 n 개의 정점을 정확히 n-1 개의 간선으로 연결한다 BFS, DFS 를 이용하여 그래프에서 Spanning Tree를 찾을 수 있다 하나의 그래프에는 많은 Spanning Tree가 존재한다 2. 최소 비용 신장 트리 (MST, Minimum Spanning Tree) 2.1. M..
CS/Algorithm 2019. 4. 17. 20:09

[AL] 6. Union-Find 알고리즘

6. Union-Find 알고리즘 Union-Find Union-Find 구현 최적화 (Optimization) 1. Union-Find 1.1. Union-Find 란? 서로소 집합(Disjoint Set) 라고 불리며, Union(x,y) 과 Find(x) 연산을 수행한다 Union(x,y) 를 수행하면 x와 y는 같은 집합에 속하게 되며, Find(x) 와 Find(y) 는 x, y 가 같은 집합에 속할 때만 같은 값을 가진다. 따라서, 전체 요소들을 서서히 묶어나가는 상황에서 유용하게 사용할 수 있는 자료구조이다. 1.2. 원리 배열을 이용해서 Tree 자료구조를 만들어 구현하며, 최상단 노드를 Root 노드로 하여 집합을 구분한다 주어진 두 원소 또는 집합을 합하는 Union 부분과 원소가 어떤..
CS/Algorithm 2019. 4. 5. 00:04

[AL] 5. 자료구조 (Heap, Hash)

5. 자료구조 (Heap, Hash) 힙 (Heap) 해시 (Hash) 해시 충돌 (Hash Collision) 1. 힙 (Heap) 1.1. 힙이란? 비선형 자료구조로서, 여러 개의 값들 중에서 최대값이나 최소값을 빠르게 찾아내도록 만들어졌다. 힙은 일종의 반 정렬 상태(느슨한 정렬 상태) 를 유지한다. 또한 BST 와는 다르게 중복된 값을 허용한다. 이를 활용하여 우선순위 큐 를 구성할 수 있다!! 1.2. 힙의 종류 최대 힙(max heap) 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리 최소 힙(min heap) 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리 1.3. 힙의 구현 힙을 저장하는 표준적인 자료구조는 배열 이다 특정 위치의 노드 번호..
CS/Algorithm 2019. 4. 1. 21:55

[AL] 4. 자료구조 (Graph)

4. 자료구조 (Graph) 그래프 (Graph) 그래프 탐색 1. 그래프 (Graph) 1.1. 그래프란? 비선형 자료구조로서, 정점의 모음 과 이 정점을 잇는 간선의 모음 간의 결합을 나타낸다. 오일러 경로 (Eulerian Tour) 그래프에 존재하는 모든 간선(edge)을 한 번만 통과하면서 처음 정점(vertex)으로 되돌아오는 경로를 말함 그래프의 모든 정점에 연결된 간선의 수가 짝수일 때만 오일러 경로가 존재함 1.2. 그래프 관련 용어 정점 (Vertex) : 위치라는 개념 (= node) 간선 (Edge) : 위치 간의 관계, 즉 노드를 연결하는 선 인접 정점 (Adjacent Vertex) : 간선으로 연결되어 있는 두 정점 경로 (Path) : 한 정점에서 다른 정점까지 이르는 경로 ..
CS/Algorithm 2019. 4. 1. 17:30

[AL] 3. 자료구조 (Linked List, Stack, Queue)

3. 자료구조 (Linked List, Stack, Queue) Linked List Stack Queue 1. Linked List 각 노드가 데이터 와 포인터 를 가지고 한 줄로 연결되어 있는 자료구조이다. 이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게 된다. 1.1. 특징 각각의 원소들은 자기 자신 다음에 어떤 원소인지만을 기억하고 있다. 따라서, 이 부분만 다른 값으로 바꿔주면 삽입과 삭제를 O(1) 만에 해결할 수 있는 것이다. 하지만 Linked List 는 한 가지 문제를 가지고 있다. 원하는 위치에 삽입을 하고자 하면 위치를 Search 하는 과정에서 첫번째 원소부터 전부 확인해야 한다는 점이다. Array 와는 달..
CS/Algorithm 2019. 3. 28. 05:54

[AL] 2. 자료구조 (Tree)

2_자료구조 (Tree) 2. 자료구조 (Tree) 트리 (Tree) 탐색 (Search) 이진 탐색 트리 (BST) 균형 트리 (AVL 트리, Red-black 트리) 1. 트리 (Tree) 1.1. 트리의 특징 노드로 이루어진 자료구조이다. OS File System, DOM(Document Object Model) 등이 트리 구조를 가지고 있다. DAG(Directed Acyclic Graphs, 방향이 있는 비순환 그래프) 의 한 종류이다 N개의 노드를 가진 트리는 항상 N-1개의 간선을 가진다 루트에서 어떤 노드로 가는 경로는 유일하다 1.2. 트리 용어 루트 노드 (root node) : 부모가 없는 노드 (트리는 하나의 루트 노드만을 가짐) 단말 노드 (leaf node) : 자식이 ..
CS/Algorithm 2019. 3. 11. 17:27