[자료구조] 자료구조의 개념과 종류

자료구조란?

자료구조(Data Structure)는 개발자가 데이터를 효율적으로 사용할 수 있도록 정리하는 방법을 말한다.

각각의 자료구조에는 장단점이 있으므로 어떤 자료구조가 최선일지는 해결하고자 하는 문제의 종류와 어떤 부분을 우선적으로 최적화할지에 따라 달라질 수 있다. 그러므로 다양한 자료구조의 장단점을 살펴보며 어떤 자료구조를 사용하는것이 최선일지 판단해야한다.

 

그렇다면, 알고리즘은 무엇일까?

알고리즘은 컴퓨터가 무슨 일을 해야할지 지시하고, 자료구조는 컴퓨터에게 알고리즘에서 사용하는 자료를 어떻게 저장할지 지시한다.

 

 

 

자료구조의 종류

자료구조는 단순 자료구조(Primitive Data Structure)와 복합 자료구조(Non-Primitive Data Structure)로 나뉜다.

단순 자료구조는 int를 포함한 프로그래밍 언어에서 통상적으로 제공하는 기본 데이터 형식을 말한다.

 

복합 자료구조는 다시 선형 자료구조(Linear Data Structure)와 비선형 자료구조(Non-Linear Data Structure)로 나뉜다.

 

선형 자료구조는 다음 그림처럼 데이터 요소를 순차적으로 연결하는 자료구조로, 구현하기 쉽고 사용하기도 쉽다. 배열, 링크드 리스트, 스택, 큐 등이 여기에 해당된다.

 

선형 자료구조는 다시 정적 자료구조(Static Data Structure)와 동적 자료구조(Dynamic Data Structure)로 나뉜다.

 

정적 자료구조는 크기가 고정되있는 자료구조를 말하며 이 크기는 정의한 뒤 고정되어 바꿀 수 없다. 이렇기에, 반드시 일정량의 메모리를 할당해야한다는 문제가 있다. 할당한 메모리보다 사용하는 데이터 요소가 적다면 일정 메모리를 낭비하는 것이 되기 때문. 또한 처음 할당한 메모리 이상으로 요소를 추가할 수도 없다.

 

동적 자료구조는 정적 자료구조와 달리 크기를 자유롭게 바꿀 수 있는 자료구조를 말한다. 크기가 고정되어 있지 않아 효율적으로 요소를 추가하거나 제거할 수 있어 메모리를 더 효율적으로 사용한다. 하지만, 정적 자료구조에 비해 요소 접근 작업의 속도는 느릴 수 있다.

(극한의 효율을 쥐어짜야하는 상황이 아니라면 정적&동적을 선택하는데 시간을 허비할 필요가 없다! 그보다는 선형&비선형 자료구조 중에 무엇을 택할지에 집중하는 것이 더 효율적이다!)

---

 

비선형 자료구조는 선형 자료구조와 달리 데이터 요소를 비순차적으로 연결한다. 다음과 같이 한 데이터 요소에서 여러 데이터 요소로 연결되기도 하고, 여러 데이터 요소가 하나의 데이터 요소로 연결되기도 한다. 트리와 그래프가 바로 여기에 해당한다.

 

비선형 자료구조에서는 원하는 요소에 접근하기 위해 백트래킹(Backtracking)이나 재귀(Recursive)가 필요한 경우가 많기 때문에 개별 요소에 접근하는 작업에는 선형 자료구조가 더 효율적이다. 다만, 선형구조는 데이터를 쉽게 순회할 수 있어 비선형 자료구조에 비해 요소 전체를 변경하는 작업이 쉽고, 백트래킹없이 모든 요소에 접근할 수 있어 자료구조 설계 및 사용에 쉽다는 점이 있다.

 

 

 

자료구조를 왜 공부해야할까?

자료구조는 알고리즘이 데이터를 효율적으로 사용할 수 있게 도와주는 핵심 부품 역할을 한다.

자료구조를 모르면 알고리즘을 공부하는데 어려움이 있다!

 

그렇다!!!! 빠아안히 쳐다본다!!!

 

 

---

[참고 사이트]

[알고리즘 + 자료구조 = 프로그램] 자료구조의 개념과 종류

 

개발자는 반드시 자료구조와 알고리즘을 배워야 할까?