자료구조란
데이터 보관방법과 데이터 연산을 말한다.
한정된 공간과 성능을 효율적으로 사용하기 위해 적절한 자료구조를 사용해야 한다.
도서관으로 예를 들어보자.
도서관 어느 한 켠에 하나의 장르, 분야에 관한 책들을 보관한다고 했을 때
적절한 위치와 적절한 공간을 분배해야 할 것이다.
순서도 없고 규칙도 없으며 어느 한 공간은 텅텅 비어있고 어느 공간을 물샐틈 없이 꽉꽉 채워져 있다면 아무도 이 비효율적이고 불편한 도서관을 이용하려 하지 않을 것이다.
자료구조에 대해 개괄적인 내용을 다뤄보겠다.
자료구조에는 단순 자료구조(Primitive Data Structure)와 복합 자료구조(Non-Primitive Data Structure)가 있다.
단순 자료구조에는
Int, Double, Float, Boolean 와 같은 기본 데이터형식을 말한다.
이는 각 책(데이터)마다 적절한 공간을 분배하는 역할을 한다.
복합 자료구조는 선형 데이터형식과 비선형 데이터 형식이 있다.
선형 데이터 형식은 1:1의 관계이며
비선형 데이터 형식은 1:N, N/M의 관계이다.
이는 각 책(데이터)들을 적절한 방식과 위치에 저장하는 방식이다.
예시를 들면 스택은
선형 데이터 형식으로
데이터를 쌓아올렸다가 가장 마지막에 들어갔던 데이터를 먼저 꺼내게 되는 방식이다.
큐 또한 선형 데이터 형식으로
처럼 먼저 들어간 것이 먼저 나오게 되는 방식이다.
비선형 데이터구조를 설명하자면
트리는 계층적 관계로
부모 자식 관계로 이루어진다. 가계도나 회사 조직도를 생각할 수도 있다.
트리의 여러 구조중에 하나인 이진트리를 설명하겠다.
이진트리는
이진 트리는 부모노드가 2개 까지의 자식 노드를 가져서 붙여진 이름이다.
왼쪽의 자식노드는 항상 부모노드 보다 작고
오른쪽의 자식노드는 항상 부모노드 보다 크다.
이렇게 되면 가장 마지막 (자식)노드의 가장 왼쪽은 최솟값이 되고 가장 오른쪽 (자식)노드는 최댓값을 가지며
최상위 (부모노드=)루트노드는 중간즈음의 값을 가지게 된다.
이 구조는 특정 값을 탐색하는데 상당히 효율적이다.
선형데이터 구조의 경우는 처음부터 끝가지 훑어보며 찾아야하는 반면
이진트리는 한번한번 탐색에 절반을 날릴수 있다.
위의 트리에서 8을 찾는다 했을때
8이 루트노드 10보다 작으므로 오른쪽 자식노드는 볼 필요도 없으며 다음 6으로 넘어가도 마찬가지로 왼쪽 자식노드는 볼 필요도 없다.
이상이 개괄적인 자료구조이며 각각의 데이터는 적절한 공간 배분과 배치가 필요하다.
깊게 파고 들고자 한다면
단순자료구조의 종류와 크기,
비선형 데이터구조의 종류와 알고리즘에 대해 공부해 볼 필요가 있다.