트라이 (Trie) ? 도입 정수나 실수형 변수는 크기가 항상 정해져 있기 때문에 비교하는데 있어서 상수 시간이 걸린다고 가정해도 된다. 하지만 문자열 변수는 최악의 경우 문자열의 길이에 비례하는 시간이 걸리기 때문에 다르게 다뤄야 한다. N개의 원소를 갖는 이진 탐색 트리에서 원하는 원소를 찾는 경우, 원소 간의 비교를 상수 시간에 할 수 있을 때는 시간 복잡도가 O(log N) 라고 할 수 있다. 하지만, 문자열의 비교에는 길이에 비례하는 시간이 걸리므로 문자열의 최대 길이 M을 곱한 O(M * log N) 의 시간 복잡도가 된다. 이러한 문제들을 해결하기 위해 고안된 자료구조가 트라이이다. 소개 트라이는 문자열의 집합을 표현하는 트리 자료구조이며, Prefix Tree 또는 Digital Tree라..
플로이드 와샬(Floyd Warshall) ? 모든 쌍 간의 최단 거리를 구하고 싶다면 다익스트라, 벨만-포드 알고리즘보다 좀더 빠르고 간단한 플로이드 (Floyd) 의 모든 쌍 최단 거리 알고리즘을 사용하면 된다. 플로이드 알고리즘은 그래프의 모든 정점 쌍의 최단 거리를 저장하는 2차원 배열 dist[][] 를 계산한다. 이 배열의 원소 dist[u][v] 는 정점 u에서 v로 가는 최단 거리를 나타낸다. 정점의 경유점들 플로이드 알고리즘의 동작 과정을 이해하기 위해서는 경로의 경유점의 개념을 소개할 필요가 있다. 두 정점 u, v를 잇는 어떤 경로가 있다고 하자. 당연하지만 이 경로는 항상 시작점 u와 끝점 v를 지난다. 이 외에 이 경로는 다른 정점들을 지나쳐 갈 수도 있다. u와 v를 직접 연결하..
그래프 탐색 (Graph Search) ? 하나의 정점 (Vertex) 에서 시작하여 간선 (Edge) 을 따라 차례대로 모든 정점들을 한 번씩 방문하는 것. 그래프를 탐색하는 두 가지 방법 DFS (Depth-First Search) BFS (Breadth-First Search) DFS (Depth-First Search) 깊이 우선 탐색이라고 하며, 해당 노드의 자식들을 모두 탐색한 후 다른 형제 노드를 탐색한다. 즉, 넓게 (Wide) 탐색하는 것이 아닌 깊게 (Deep) 탐색하는 것이다. 보통, 모든 노드를 방문하고자 할 때 사용한다. 자기 자신을 호출하는 순환 알고리즘 형태를 가지므로, 스택 (Stack) 혹은 재귀함수 (Recursive Function) 로 구현한다. DFS 특징 전위 (P..
1. 해시 (Hash) 해시 함수 (Hash Function) : 효율적인 데이터 관리를 위해 임의의 길이를 가지고 있는 데이터를 고정된 길이의 데이터로 매핑 (Mapping) 하는 함수 키 (Key) : 매핑 전 원래 데이터의 값 해시 값 (Hash Value) : 매핑 후의 데이터 값 해싱 (Hashing) : 매핑하는 과정 자체 특징 해시 함수는 언제나 동일한 해시 값을 반환하고, 해당 인덱스만 알면 해시 테이블의 크기에 상관없이 데이터에 빠르게 접근할 수 있으며, 인덱스는 간단한 함수 (상수 시간) 로 계산되기 때문에 매우 효율적이다. 결국, 해시는 데이터 액세스 (삽입, 삭제, 탐색) 시 계산 복잡도가 \(O(1)\) 이 되도록 한다. 해시 함수는 원래의 문장을 복호화 할 수 없게 뭉개버린다는 ..
1. 스택 (Stack) ? 한 방향에서만 데이터를 뽑아낼 수 있는 선형 구조인 LIFO 형태의 자료구조이다. LIFO - Last In First Out의 줄임말이며, 말 그대로 마지막에 들어온 데이터가 첫 번째로 빠져나간다는 의미이다. 화물차안에 짐을 넣을 때를 생각해보자. 가장 먼저 넣은 짐은 가장 나중에 빠지고, 가장 늦게 넣은 짐은 가장 먼저 빠지는 원리이다. 1-1. Stack의 연산 Top : 연산이 아닌 Stack의 최상위층 인덱스라고 보면 된다. push : Stack내에 데이터를 삽입할 때 사용한다. pop : Stack내에서 맨 꼭대기인 Top부분에 위치한 데이터를 꺼낼 때 사용한다. peek : pop과의 차이점은 peek은 데이터를 조회만 할 뿐 꺼내지는 않는다. empty : S..
1. Array (배열) ? 동일한 자료형의 데이터를 한꺼번에 관리하기 위한 자료구조이다. 배열을 이용하여 하나의 변수에 여러 데이터를 담을 수 있으며, 반복문을 이용하여 효율적으로 처리가 가능하다. 1-1. 배열의 특징 크기가 정해져 있기 때문에 바꾸지 못한다. 고유한 인덱스 값을 가지고 있으며, 인덱스를 통해 특정 위치의 데이터를 빠르게 조회할 수 있다. 데이터가 중간위치에서 추가 또는 삭제 될 경우, 빈번한 이동을 요구하며 남아있는 공간으로 인해 메모리 낭비가 발생할 수 있다. 특별한 기능이 없기 때문에 다른 자료구조의 부품으로 사용할 수 있다. 2. List (리스트) ? 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 노드의 포인터가 다음이나..