[자료구조] 0. 자료구조 시작에 앞서

지난 학기에는 학교에서 자료구조를 수강했었다. 흔히 컴퓨터공학 6대 과목을 자료구조, 알고리즘, 컴퓨터 구조론, OS, 컴퓨터 네트워크, 데이터베이스 이렇게 6가지를 말하곤 한다. 그중 처음 듣는 과목인 자료구조였던 만큼 제대로 된 전공공부를 해보게 된다 라는 느낌으로 수강하였다.

사실 자료구조의 대부분은 따로 커리큘럼을 따라 배운것은 아니지만, 그때그때 배웠던 지식으로 알고 있었기에 대부분 수업을 복습하는 느낌으로 듣게 되었다. 그러나 원래 잘 확실히 이해하지 못했던 Priority Queue와 Heap의 관계를 ADT와 Implemantation의 관계라는 것을 이해할 수 있었고, AVL Tree를 직접 구현해보기도 하고, 여러 자료구조들을 수학적으로 따져보기도 하는 과정도 새로웠다. 또한 그래프 구현시 기존에는 야매로 노드별로 구현하는 편이었는데, 실제로는 Adjacency List를 주로 쓴다는 것도 배웠다.

수강을 끝낸후 드는 생각은 시간복잡도의 계산에 대해서 좀 더 집중해서 들었으면 좋았을 것 같다는 아쉬움이 남는다. 이 부분은 아직도 헷갈리기도 한다.

 

아무튼 이렇게 강의를 끝내고 기억이 휘발되기 전에 나 스스로가 기억이 희미할때 다시 복습하기 위한 글을 간단하게 써두는 게 좋겠다는 생각이 들었다. 그리하여 앞으로 며칠간 자료구조에 대한 정리글을 쓸 예정이다. 목차는 다음과 같이 계획 중이다.

1. 배열 (Array)
2. 연결 리스트(Linked List)
3. 알고리즘 분석 (Algorithm Analysis)
4. 스택 (Stack)
5. 큐 (Queue)
6. 재귀 (Recursion)
7. 동적 배열 (Dynamic Array)
8. 트리 (Tree)
9. 우선순위 큐 (Priority Queue)
10. 힙 (Heap)
11. 맵, 딕셔너리 (Map, Dictionary)
12. 이진탐색트리 (Binary Search Tree)
13. AVL트리 (AVL Tree)
14. 해시테이블 (Hash Table)
15. 그래프 (Graph)
16. 외향그래프 (Directed Graph)
17. DFS
18. BFS

아마 작성을 하며 순서를 조금 손보고, 내용이 길 경우 글을 나눠 작성할 것 같기도 하다. 또한 나의 기억을 환기하기 위한 목적의 글이기에 설명의 형식을 가지는 글이 되지는 않을 것 같다.

ADT(Abstract Data Type)

ADT란 추상적인 자료구조로써, 저장된 데이터 그 자체와 데이터를 다루는 동작들을 포함합니다.

 

이런 식의 설명으로는 이해하기 어려울 수 있으니, 더 자세히 설명해보겠습니다. "추상적"이라고 표현한 이유는, ADT를 사용하는 사람들은 내부 구현에 대해 신경 쓸 필요가 없기 때문입니다. 다시 말해, 스택을 예로 들면 사용자들은 스택의 push()와 pop() 함수를 활용하여 데이터를 넣거나 빼낼 수 있지만, 실제로 스택 내부에서 어떻게 동작하는지에 대해서는 고려하지 않아도 된다는 것입니다.

 

또한 ADT는 데이터와 동작 모두를 아우르는 개념입니다. 스택을 예로 들면, 실제 스택 내부에 저장되는 여러 값들과 이러한 값을 처리하기 위한 push(), pop() 함수 등이 모두 포함되어 있어, 스택이라는 ADT를 완성합니다.