[CS] 자료구조란 무엇인가?

자료구조(Data Structure)

자료구조란 여러 데이터의 묶음을 저장하고, 사용하는 방법을 정의한 것이다.

데이터는 문자, 숫자, 소리, 이미지, 동영상 등 실생활을 구성하고 있는 모든 정보의 값을 말한다. 데이터들은 분석하고 정리하여 활용해야만 의미를 가질 수 있다. 이러한 데이터들의 규칙을 정하고, 체계적으로 정리하여 저장하는 등 여러 상황에 맞게 데이터를 효율적으로 다룰 수 있도록 만든 것이 자료구조이다.

 

자료구조의 종류

자료구조는 크게 단순 구조, 선형 구조, 비선형 구조, 파일 구조 네 가지로 분류할 수 있다.

단순 구조는 2진수, 정수와 실수, 문자, 문자열 등의 데이터를 나타내는 구조를 말하며, 파일 구조는 순차 파일, 색인 파일, 직접 파일 등이 있다.

 

다음은 효율적인 알고리즘을 사용할 수 있게 하는 선형 구조와 비선형 구조가 있다.

 

선형 구조

리스트(배열) : 가장 일반적인 구조로 메모리 상에 같은 타입의 자료가 연속적으로 저장되는 자료구조이다.

 

연결 리스트 : 노드를 단위로 하여, 노드가 가지는 값과 다음 노드를 가리키는 참조값으로 구성되어 있다. 만약, 노드가 다음 노드로 아무것도 가리키지 않으면 리스트의 끝을 나타낸다.

 

스택 : 제일 나중에 저장된 데이터가 가장 먼저 나오는 자료구조로 후입선출(LIFO : Last In First Out) 또는 선입후출(FILO : FirstIn Last Out) 자료구조라고도 한다.

 

큐 : 스택과 반대로 가장 먼저 저장된 데이터가 가장 먼저 나오는 자료구조이다. 선입선출(FIFO: First In First Out) 자료구조라고도 한다.

 

덱 : 양쪽에서 데이터를 저장하고 나오는 동작을 수행할 수 있는 자료구조로, 일반화된 선형 구조이다.

 

비선형 구조

그래프 : 꼭짓점(Vertex)과 꼭짓점을 잇는 변(Edge)으로 구성된 자료구조로, 변이 방향을 갖는 유향 그래프와 방향이 없는 무향 그래프가 있다.

 

트리 : 부모와 자식 관계로 데이터를 저장하는 자료구조로 최상위 노드는 루트 노드라 불리며 그 하위 노드들은 부모 노드와 자식 노드들로 이루어져 있다. 자식 노드의 경우 단 하나의 부모 노드만을 가리키며, 최대로 두 개의 자식만을 가질 수 있는 이진트리가 있다.

 

알고리즘 문제로 자주 등장하는 자료구조로는 스택, 큐, 트리, 그래프 등이 있다.