자료 구조(Data Structure)의 개념과 종류

자료구조

프로그램을 구성하는데 있어 자료구조와 알고리즘을 필요로 합니다.

 

자료구조란 자료에 대한 효율적 탐색, 삽입, 삭제 등이 가능하도록 자료들을 구조화 해둔 것을 의미합니다.

 

알고리즘은 문제를 처리하는 절차로, 기술하는 방법에 있어서는 자연어, 흐름도(순서도), 의사코드, 프로그래밍 언어로

구분할 수 있습니다.

 

자료구조는 추상자료형에 따라 다르게 구현될 수 있습니다.

 

여기서 추상자료형(Abstract Data Type, ADT)이란, 자료에 대한 정의 혹은 자료에 대해 가능한 연산에 대한 정의로 볼 수 있습니다.

 

추상 자료형	표현하는 자료	구현 자료구조
리스트 (List)	순서가 부여된 자료 모음	배열 (Array) 연결리스트 (Linked List)
스택 (Stack)	후입선출 (LIFO) 방식으로 동작하는 자료 모음 한 쪽 끝에서만 삽입과 삭제가 가능한 리스트
큐 (Queue)	선입선출 (FIFO) 방식으로 동작하는 자료 모음 한 쪽 끝에서는 삽입, 다른 쪽 끝에서는 삭제가 가능한 리스트
덱 (Deque)	리스트의 양 끝에서 삽입과 삭제가 모두 가능한 리스트
집합 (Set)	중복이 없는 자료 모음	트리 (Tree) 해쉬테이블 (Hash Table)
트리 (Tree)	계층적 관계를 갖는 자료 모음	트리 (Tree)
그래프 (Graph)	관계를 갖는 자료 모음	인접행렬 (Adjacency Matrix) 인접리스트 (Adjacency List)
사전 (Dictionary) 맵 (Map)	키 (Key), 값 (Value)의 쌍으로 구성된 자료 모음	트리 (Tree) 해쉬테이블 (Hash Table)
우선순위 큐 (Priority Queue)	우선순위에 따라 삭제가 발생하는 자료 모음	힙 (Heap)

위 표의 추상 자료형에서 리스트, 스택, 큐, 덱은 선형 자료구조로 구분되고

집합, 트리, 그래프, 사전, 맵, 우선순위 큐는 비선형 자료구조로 구분됩니다.

 

알고리즘 성능 분석

각 자료구조들은 시간복잡도와 공간복잡도를 가집니다.

 

시간복잡도는 프로그램 실행에 필요한 총 시간의 양을 의미하고

공간복잡도는 프로그램 실행에 필요한 총 공간의 양을 의미합니다.

 

현대에 들어서 하드웨어 성능이 올라감에 따라, 공간복잡도보다 시간복잡도를 더 중요하게 보는 경향이 있습니다.

 

효율적 알고리즘을 구사하기 위해서는 시간복잡도와 공간복잡도가 적을수록 효율적이라고 볼 수 있습니다.

 

시간복잡도에는 크게 세가지 표기법이 있습니다.

 

먼저 빅오 (Big O) 표기법은 자료 크기의 증가에 따른 함수 증가율의 최소상한을 의미합니다.

 

다음으로 빅오메가 (Big Omega) 표기법은 자료 크기의 증가에 따른 함수 증가율의 최대하한을 의미합니다.

 

마지막으로 빅세타 (Big Theta) 표기법은 자료 크기의 증가에 따른 함수 증가율의 점근적 상한과 하한의 교집합을 의미합니다. 즉, 빅오 표기법과 빅오메가 표기법이 같으면 빅세타가 존재한다고 볼 수 있습니다.

 

이 세가지 표기법 중 우리는 빅오 표기법을 사용합니다. 그 이유로는 최소상한 즉, 최악의 경우 이 정도는 걸린다는 의미이기 때문에, 시간복잡도를 표기함에 있어 저 최악보다 안좋은 경우는 없기 때문입니다.

 

빅오 표기법은 다음과 같으며 아래로 갈 수록 시간복잡도가 안좋다고 볼 수 있습니다.

 

O(1)	상수형
O(log N)	로그형
O(N)	선형
O(N log N)	로그선형
O(N²)	2차형
O(N³)	3차형
O(2^N)	지수형
O(N!)	계승형

 

이렇게 자료구조의 정의와 종류, 시간복잡도에 대해서 리뷰해보았습니다.