HashTable 또는 HashMap이란 키값을 이용하여 값을 저장하는 구조로 키값을 해시함수에 넣어 인덱스로 변환한 후 테이블에 접근해 저장하는 자료구조이다. 해시테이블은 해시함수를 통해 테이블의 인덱스를 계산하고 이 값을 통해 테이블에 직접 접근하기 때문에 O(1)의 빠른 접근시간을 가지고 있다. 위 그림을 보면 왼쪽에 사람의 이름에 해당하는
DisJointSet은 집합을 나타낼 수 있는 간단한 자료구조이다. 집합은 어떠한 원소들이 하나의 공통 요소에 의해 묶여 있다는 것을 말한다. 위의 그림을 보면 p q r s는 X라는 요소에 묶여 있고 1 2 3 4 5 는 Y라는 요소에 묶여 있다. 즉 이를 구현하기 위해 생각해보면 각 원소들은 X나 Y라는 요소를 가리키고 있다고 생각하면 편하게 된다.
우선순위 큐는 Heap의 구조를 이용해 정렬을 수행하는 이진 트리 구조이다. Heap은 원소를 삽입시 가장 큰 원소가 루트 노드에 오도록 노드의 위치를 재배열한다. 이 재배열을 하는 과정은 매번 O(logn)의 시간복잡도를 가지게 된다. 우선순위 큐를 구현하면서 가장 큰 두가지의 기능인 Push와 Pop의 기능을 생각해보자. Push 연산을 하게 되
Stack은 Last In-First Out의 자료구조로 가장 나중에 들어온 원소가 가장 먼저 나오게되는 자료구조이다. Stack은 top이라는 포인터 변수를 두어서 push, pop하며 이 top포인터를 조절하도록 구현된다. Stack 자료구조는 주로 재귀 호출에 주로 사용되게 되고 재귀 호출로 불린 함수는 가장 나중에 불린 함수가 가장 먼저 실행되
Queue는 First in First out의 자료구조로 가장 먼저 들어온 원소가 가장 먼저나가는 선입선출 구조이다. 순서대로 처리해야 할 일을 큐에 집어 넣고 처리할 때 주로 사용되며 알고리즘에서 BFS를 주로 큐를 이용해 구현한다. 12345678910111213141516171819202122232425262728293031323334353637
Linked List는 노드 들간의 연결된 포인터들로 구성되는 자료구조이다. 배열과 같이 원소가 선형으로 저장된다는 특성이 있지만 배열과는 달리 중간에 원소의 삽입 삭제가 가능하고 중간에 있는 원소에 접근하기 위해서는 Head에서부터 순차적으로 접근해서 찾는 방식을 취할 수 밖에 없다. 배열과 Linked List는 다음과 같은 차이점을 가지고 있다.