cs 기본 정리

순차 자료구조 vs 연결 자료구조

순차 자료구조는 메모리 상에서 일렬로 나열된 데이터형이며 연결 자료구조는 메모리 상에서는 분산되어 있지만 하나의 노드가 다음으로 이어지는 포인터를 가지고 있어 연속적으로 접근이 가능한 데이터형이다.

 

데이터 삽입 : 순차 자료구조의 마지막에 데이터를 삽입하는 경우는 빠르지만 처음과 중간에 삽입하는 경우에는 자리교환으로 인한 오버헤드가 발생하여 느리다. 연결 자료구조는 데이터를 어디에 삽입하던 해당 위치까지 엑세스하는 시간만 소요되지만 자료 추가시 링크만 교체하면 되므로 빠르다.

 

데이터 읽기 : 연결 자료구조는 위치를 알던 모르던 관계없이 헤더부터 찾으려는 위치까지 탐색해야 하므로 느리다. 순차 자료구조는 탐색하려는 위치를 알고 있다면 즉시 엑세스 할 수 있으므로 빠르며 탐색하려는 위치를 모른다고 하더라도 메모리 상에서 근접한 데이터의 접근이 더 빠르므로 연결 자료구조보다 빠르다.

 

스택과 큐

스택은 가장 먼저들어온 개체가 가장 마지막에 나가는(Last in first out, LIFO) 방식을 사용하는 자료구조이며 대부분은 펜케이크에 비유하곤 한다. 아래에서 위로 데이터를 쌓고 위에서 아래로 데이터를 지운다.

큐는 가장 먼저 들어온 개체가 가장 먼저 나가는(First in first out, FIFO) 방식을 사용하는 자료구조이며 대부분은 택시정거장에 비유하곤 한다.

 

트리

트리는 계층구조를 표현하기 위해서 사용하는 자료구조이다. 트리의 크기를 제한하면 트리의 연산이 단순해지고 명확해지는데 차수를 2개 이하로 정의한 것이 이진 트리이다. 이진 트리의 종류로는 스레드 이진 트리, 이진 탐색 트리, AVL 트리 등이 있다.

 

힙(Heap)

힙는 이진트리의 한 종류로 나열한 두 가지 조건이 성립하는 이진 트리를 의미한다. 우선 완전 이진 트리여야 한다. 또한 부모 노드와 자식 노드간에 크기 관계가 성립해야 한다. 루트 노드가 가장 크고 자식 노드가 부모 노드보다 작으면 최대 힙, 반대의 경우는 최소 힙이다. 각각 최댓값과 최솟값에 접근하기 위해 사용하며 성능이 매우 좋다.

 

해쉬

해쉬는 임의의 크기를 가진 데이터를 고정된 크기의 값으로 변환시키는 것을 말한다. 해쉬를 이용하여 임의의 데이터를 숫자로 변경하는 해쉬 함수를 정의하면 배열의 인덱스를 원하는 데이터 값으로 저장하거나 찾을 수 있다. 기존에는 탐색을 위한 시간이 소모됨에 반해 해쉬를 이용하면 즉시 데이터에 엑세스 할 수 있다.

 

그래프

정점과 에지로 이루어진 형태의 자료구조다. 에지의 방향성의 존재 유무에 따라서 유향 그래프와 무향 그래프로 분리되며 에지가 가중치를 가지고 있지고 있다면 가중치 그래프라고 부른다. 그래프는 행렬과 연결리스트를 활용하여 구현할 수 있는데 행렬의 경우 정점의 존재 여부와 상관없이 항상 n^2의 공간 복잡도를 가진다.

 

트리와 그래프의 차이점

구현이나 동작의 형태로는 트리와 그래프는 동일하다고 생각된다. 트리와 그래프의 유일한 차이점은 그래프에는 루트 노드가 존재하지 않는 다는 것. 트리에서는 루트 노드로 되돌아오는 에지가 존재하지 않다는 점이다.