자료구조(資料構造, 영어: data structure)는 컴퓨터 과학에서 효율적인 접근 및 수정을 가능케 하는 자료의 조직, 관리, 저장을 의미한다. 위키백과
자료구조(Data Structure)를 공부하는 대상의 수준을 <윤성우, 열혈 자료구조>에서는 아래와 같이 가정하고 있다.
C 언어
- 구조체를 정의할 줄 알고 구조체 대상의
typedef선언을 할 줄 안다. malloc함수와free함수를 사용할 줄 알고, 이는 메모리의 동적 할당과 관련 있음을 이해한다.- 포인터 변수의 선언과 포인터 연산에 부담이 없다.
- 헤더파일이 필요한 이유를 이해한다.
- 헤더파일을 정의할 줄 알고 헤더파일에 들어가야 할 것들이 무엇인지 알고있다.
- 헤더파일의 정의에 사용되는 매크로
#ifndef~#endif의 의미를 알고 있다. - 하나의 프로그램을 둘 이상의 소스파일과 헤더파일에 나누어 담을 줄 안다.
- 재귀함수의 동작방식을 안다. 그리고 재귀함수와 관련된 아주 간단한 예제는 분석할 수 있다.
사실 위의 내용에 대해서는 C언어 책 하나를 잡고 공부를 했었다면 문제가 될 것이 없다.
그렇다면 우리는 왜 자료구조를 배워야할까. 자료구조를 몰라도 프로그램을 작성하는 것에 여태 문제가 없었지 않았던가. 그 이유는 당연하게도 효율성 때문이다. 자료구조는 데이터의 접근과 수정을 보다 효율적으로 진행하게 해준다. 이후에 배우게 될 수많은 알고리즘 또한 자료구조를 이용하여 구현한다.
분류
자료구조는 아래와 같이 크게 4가지로 분류할 수 있다.
단순구조 / 선형구조 / 비선형구조 / 파일구조
단순구조: 자료형
정수 / 실수 / 문자 / 문자열
선형구조: 자료가 1:1의 관계
리스트 / 스택 / 큐 / 덱
비선형구조: 자료가 n:m의 관계
그래프 / 트리
파일구조: 디스크 접근(메모리 접근에 비해 느림)을 최소화
순차파일 / 색인파일 / 직접파일
공부
자료구조를 공부하려 한다면 무엇을, 어떤 순서로 공부해야할까. (이 글이 정답은 아니다. 참고만 하자.)
대략적으로 자료구조 범위에서 공부하는 것들은 아래와 같다.
연결 리스트(Linked List), 스택(Stack), 큐(Queue), 트리(Tree), 그래프(Graph),힙(Heap), 해시 (Hash)
공부 순서 또한 쓰인 순서대로 진행해도 무관하다.
해당 내용을 공부하며 다음 내용으로 넘어갈 때가 적절한지를 모르겠다면 아래와 같이 판단해보자.
1. 직접 구현을 할 줄 아는가?
2. 작동 원리를 이해하였는가?
3. 해당 자료구조를 이용한 알고리즘으로 무엇이 있는지 아는가?
1, 2번은 직접적인 이해에 대한 내용으로 볼 수 있다면 3번에 해당하는 내용은 공부한 내용을 어떻게 적용할지에 대한 내용이다.
위에 적힌 내용이 적게 느껴질 수도 있다. 하지만 연결 리스트에도 단순 연결 리스트(Single Linked List), 이중 연결 리스트(Double Linked List) 등이 있는 것처럼 세세하게 나누어지는 경우도 있으니 걱정하지 않아도 된다.
또한, 그래프와 트리를 공부하게 될 때 순회 / 탐색에 대한 공부 또한 진행하게 될 것이다. 게다가 수많은 형태의 그래프와 트리, 그리고 연관된 알고리즘을 이해하는데 꽤 많은 시간을 써야한다.
그래프만 해도 기본적으로 알고 넘어가야 할 것이 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS), 다익스트라(Dijkstra), 플로이드-와샬(Floid-Warshall), 최소 신장 트리(Minimum Spanning Tree)... 굉장히 많다.
트리는 그래프의 특수한 형태로 이 또한 순회(Traversal)와 관련된 내용과 여러 종류의 트리 등 많은 내용을 담고 있다.
이전에 공부를 하고 들어가면 좋은 내용
시간 복잡도(Time Complexity) 와 공간 복잡도(Space Complexity) 이해 >빅-O 표기법 > 재귀(Recursion) > 분할 정복(Devide and Conquer) > 그리디(Greedy), 탐욕법 > 다이나믹 프로그래밍(Dinamic Programming, DP) > 이분 탐색(Binary Search) > 여러 정렬(Sorting) 알고리즘 이해 및 구현 > 비트 연산(Bitwise Operation) 및 비트마스킹(Bitmasking) > C++ STL
자료구조
연결 리스트(Linked List) 이해 > 단순 연결 리스트(Single Linked List) 구현 > 이중 연결 리스트(Double Linked List) 구현 > 스택(Stack), 큐(Queue) 이해 > 스택(Stack), 큐(Queue) 배열 / 연결 리스트 기반 구현 > 트리(Tree) 이해 > 트리(Tree) 의 순회(Travesal) 이해 및 구현(전위순회(Preorder Traversal), 중위순회...) > 후위 표기법과 수식 트리(Expression Tree) 이해 및 구현 > 이진 탐색 트리(Binary Search Tree, BST) 이해 및 구현 > 그래프(Graph) 의 구현 (인접 리스트(Adjacency List), 인접 행렬(Adjacency Matrix)) > 그래프(Graph) 의 탐색(너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)) > 그래프(Graph) 의 최단 거리(다익스트라(Dijkstra), 플로이드-와샬(Floid-Warshall)) > 최소 신장 트리(Minimum Spanning Tree, MST) 이해 및 구현 크루스칼(Kruskal) / 프림(Prim) > 힙(Heap) 이해 및 구현 > 우선 순위 큐(Priority Queue) 이해 및 구현 > 해시(Hash) 이해 및 구현 > 해시 충돌 문제(Hash Collision Problem)
대강 이정도 공부를 마쳤다면 알고리즘을 공부하기 위한 준비를 마쳤다고 볼 수 있다. 알고리즘의 정당성을 증명하며 공부하는 것 또한 좋은 공부법이 될 것이다. 초반에 잘 잡아놓지 않는다면 나중에 헷갈리는 경우가 꽤 있다. 또한 자료구조를 공부하며 C++ STL 내부 구현과 비교하며 공부하였을 때 큰 도움이 될 것이다. STL 에는 사용하지 않는 기능도 있어 직접 필요한 부분만 구현한 것보다 시간을 더 잡아먹는다. 자신이 작성하려는 내용이 무엇인지 확실하게 알고 적절한 상황에 맞게 STL 을 사용하는 습관을 들이자.
