미처 완성되지 못한 알고리즘

테이블의 시간 복잡도는 O(1)이다. 테이블에 저장되는 데이터는 키와 값이 하나의 쌍을 이룬다. 키가 존재하지 않는 값은 저장할 수 없으며, 모든 키는 중복되지 않는다.

이진 탐색 트리의 탐색 연산은 O(log2n)의 시간 복잡도를 가진다. 이러한 이진 탐색 트리는 균형이 맞지 않을수록 O(n)에 가까운 시간 복잡도를 보인다. 이것이 이진 탐색 트리의 단점이며, 이 단점을 해결한 트리를 가리켜 '균형 잡힌 이진 트리'라 불리운다. 그 종류는 다음과 같이 5가지가 된다. 1.AVL 트리2.2-3 트리3.2-3-4 트리4.Red-Black 트리5.B트리 AVL트리는 노드가 추가될 때, 그리고 삭제될 때 트리의 균형상태를 파악해서 스스로 그 구조를 변경하여 균형을 잡는 멋진 트리다. AVL트리에서는 균형의 정도를 표현하기 위해서 균형 인수라는 것을 사용하며 이 균형 인수는 다음과 같이 계산된다. 균형 인수 = 왼쪽 서브 트리의 높이 - 오른쪽 서브 트리의 높이 AVL 트리는 ..

일반적으로 큐는 FIFO 구조로, 먼저 입력된 데이터가 먼저 출력되지만 우선순위 큐는 각 데이터의 우선순위에 따라 나중에 입력된 데이터가 더 먼저 출력될 수도 있다. 우선순위 큐의 구현 방법에는 3가지가 있다. 1.배열2.연결 리스트3.힙 여기서 1,2방식은 각 각 문제점이 있다. 1. 데이터를 삽입 및 삭제하는 과정에서 데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로 당기는 연산을 수반해야 한다.2.삽입의 위치를 찾기 위해서 최악의 경우 저장된 모든 데이터와 우선순위의 비교를 진행해야 될 수도 있다. 2의 경우는 1,2방식 모두에게 해당하며 1의 경우는 1의 방식에 해당된다. 그래서 우선순위 큐는 힙이라는 자료구조를 이용해서 구현하는 것이 일반적이다. 힙이란? 이진트리이되 완전 이진 트리이며, 모든 노드..

트리는 선형 자료구조인 스택과 큐와 다르게 비선형 자료구조이다. 선형 자료구조들은 보통 삽입,삭제 등 기능에 초점이 맞춰져 있다면 트리는 '표현'에 초점이 맞춰져 있다. 즉, 트리는 계층적 관계를 표현하는 자료구조이다. 트리가 표현할 수 있는 것들 중 예를 들자면, 디렉터리 구조나 기업의 조직도 등이 있겠다. 트리 관련 용어: 1.노드 트리의 구성요소에 해당하는 데이터. 2.간선 노드와 노드를 연결하는 연결선 3. 루트 노드 트리 구조에서 최상위에 존재하는 노드 4.단말 노드 아래로 또 다른 노드가 연결되어 있지 않은 노드 5.내부 노드 단말 노드를 제외한 모든 노드 6.조상 노드 특정 노드의 위에 위치한 모든 노드를 가리켜 '조상 노드'라 한다. 7.후손 노드 특정 노드의 아래에 위치한 모든 노드를 가..

큐는 스택과 함께 대표적인 자료구조 중 하나인데, 스택과는 다르게 큐는 선입선출이라고 하여 먼저 입력된 자료가 먼저 출력된다. 이러한 큐의 예는 실생활에서도 여럿 찾아볼 수 있는데 그 중 하나가 은행에서 순번대로 업무처리 하기 등 순서대로 처리하는 업무가 하나지 아닐까 싶다. 큐를 변형된 형태로 덱이라고 있는데, 이는 앞에서도 삽입,삭제가 가능하며, 뒤에서도 삽입,삭제가 가능한 자료구조이다.

스택은 FILO(first in last out) 또는 LiFO(Last in First out )으로 선입후출,후입선출. 즉, 처음 들어간 데이터가 가장 마지막에 나오는 구조이다. 스택은 한방향에서 데이터의 인풋, 아웃풋이 이뤄진다. 계산기에서 자주 사용된다. 중요 ADT로는 데이터 입력을 Push, 데이터 출력을 Pop이라 한다.

배열은 선형적인 자료구조이며, 메모리에 순차적으로 잡힌다. int a, int b, int c 이렇게 선언을 할 경우 메모리에 순차적으로 잡힐 수도 있지만, 안 잡힐 수도 있다. 반대로 배열 선언을 하여 배열 변수를 생성할 경우에는 메모리에 무조건 순차적으로 잡힌다. 배열의 선언과 사용법은 간단하나 배열은 단점이 있는 자료구조이기도 하는데, 예를 들어 0x00번지부터 0x0C번지까지 잡힌 int형 3개짜리 배열에서 가운데 값을 삭제를 하면 그 뒷번지 값을 끌어오는 연산에 부담이 생긴다. (3개짜리가 아니라, 1000개라 생각해보라. 가운데 400번째 값을 삭제하면 599개의 값을 순차적으로 끌어오는 것이다.) 여기서 약 599번의 연산이 반복되며 퍼포먼스가 떨어진다. 배열은 논리적일 뿐만 아니라 물리적으..