천천히 가는 것을 걱정하지 말고 서있는 것을 걱정하라.

그래프 (Graph) ? 도입 그래프는 현실 세계의 사물이나 추상적인 개념 간의 연결 관계를 표현한다. 우리 주변에서 찾을 수 있는 예를 들면, 여러 도시들을 연결하는 도로망, 사람들 간의 지인 관계, 웹사이트 간의 링크 관계 등이 있을 것이다. 그래프의 정의 그래프 \(G(V, E)\) 는 아래 요소들로 구성된 자료 구조이다. 어떤 자료나 개념을 표현하는 정점 (Vertex) 들의 집합 \(V\). 정점들을 연결하는 간선 (Edge) 들의 집합 \(E\). 아래 그림은 1 ~ 5까지의 번호가 주어진 정점들과 이들을 연결하는 간선으로 구성된 그래프들의 예시다. 그래프는 정점들과 간선들로 정의되며, 정점의 위치 정보나 간선의 순서 등은 그래프의 정의에 포함되지 않는다. 따라서 다른 모양이지만 위 그림은 모..

상호 배타적 집합 공통 원소가 없는, 즉 상호 배타적인 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료 구조가 바로 유니온-파인드 자료 구조이다. Example 어떤 파티에 n명의 사람들이 왔다고 하자. 생일이 동일한 사람들끼리 팀을 구성할 때, 같은 사람을 한 번 찾게 되면 이 사람들은 팀을 이뤄 같이 움직인다. 그리고 다른 팀과 생일이 같다는 것을 확인하면 곧장 두 팀은 합쳐지게 된다. 상황 표현 및 연산 우선 각 사람을 0 ~ n - 1 까지의 원소로 표현한 뒤, 각 1개의 원소를 포함하는 n개의 집합을 만든다. 두 사람 a와 b가 서로 생일이 같다는 사실을 알 때마다 두 사람이 포함된 집합을 합치게 된다. 이와 같은 일들을 구현하기 위해 세 가지 연산이 필요하다. 초기화 : n개..

접미사 배열 (Suffix Array)? 어떤 문자열 S (아래의 경우 "alohomora") 의 모든 접미사를 사전순으로 정렬해 둔 자료구조이다. 접미사들을 그대로 문자열 배열에 저장하면 문자열 길이의 제곱에 비례하는 메모리가 필요하기 때문에, 보통 각 접미사의 시작 위치를 담는 정수 배열로 구현된다. i A[i] S[A[i]] 0 8 a 1 0 a l o h o m o r a 2 3 h o m o r a 3 1 l o h o m o r a 4 5 m o r a 5 2 o h o m o r a 6 4 o m o r a 7 6 o r a 8 7 r a 접미사 배열을 이용한 문자열 검색의 핵심은 '짚더미 H'가 '바늘 N'을 포함한다면 항상 N은 H의 어떤 접미사의 접두사라는 점을 이용한다. ex) "al..

트라이 (Trie) ? 도입 정수나 실수형 변수는 크기가 항상 정해져 있기 때문에 비교하는데 있어서 상수 시간이 걸린다고 가정해도 된다. 하지만 문자열 변수는 최악의 경우 문자열의 길이에 비례하는 시간이 걸리기 때문에 다르게 다뤄야 한다. N개의 원소를 갖는 이진 탐색 트리에서 원하는 원소를 찾는 경우, 원소 간의 비교를 상수 시간에 할 수 있을 때는 시간 복잡도가 O(log N) 라고 할 수 있다. 하지만, 문자열의 비교에는 길이에 비례하는 시간이 걸리므로 문자열의 최대 길이 M을 곱한 O(M * log N) 의 시간 복잡도가 된다. 이러한 문제들을 해결하기 위해 고안된 자료구조가 트라이이다. 소개 트라이는 문자열의 집합을 표현하는 트리 자료구조이며, Prefix Tree 또는 Digital Tree라..

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 (리스트) ? 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하는 자료 구조이다. 노드의 포인터가 다음이나..