1 개요
資料構造 / Data Structure
프로그래밍에서 데이터를 구조적으로 표현하는 방식과 이를 구현하는 데 필요한 알고리즘에 대해 논하는 기초이론, 혹은 과목. 컴퓨터 과학/공학에서 알고리즘과 함께 가장 중요한 기초이론이다. 이것을 공부하지 않고 상위 과목을 공부하는 건 사실상 불가능하다. 영어로 치면 알파벳을 모르는 상태로 독해를 공부하겠다는 것과 마찬가지다.
컴퓨터의 메모리는 1차원 구조이기 때문에[1] 현실 세계의 다차원데이터를 다루기 위해서는 이것을 1차원인 선 형태로 바꾸는 것이 필요하다. 대학교 1학년 과정에서 배우는 기초 알고리즘들은 바로 이 방법을 학습한다. 2차원 배열, 이진 트리, 그래프 등의 자료구조가 2차원 데이터를 1차원으로 욱여넣는 방법을 배우는 것이다. 더 나아가 3차원 데이터를 다루고, 더 지나면 3차원 데이터 이상의 다차원 데이터를 처리하는 자료구조를 만날 수 있다. 물론 B트리나 R트리의 경우처럼 같은 2차원 데이터도 어떻게 조직화하느냐에 따라 자료구조가 달라진다.
자신이 프로그래머가 되고 싶다면 최소한 연결 리스트와 이진 트리는 평생 머릿속에 담아두고 있어야 한다. 이 두 자료구조를 이해하지 못하면 스스로 알고리즘을 설계하는 데 엄청난 애로사항이 꽃핀다. B트리나 AVL트리 같은 건 몰라도 된다. 따지고 보면 B트리와 AVL트리는 그냥 균형이 자동으로 잡히는 이진 트리로, 전용 알고리즘에 의해 관리되는 특수 자료구조에 불과하다. 즉 이진 트리의 응용형이다. 그래프는 연결 리스트의 응용형. 이진 트리는 그래프에 어떤 제약이 가해진 특수 형태. 이런 식으로 가지쳐나가는거라(책에 따라 반대로 서술하는 경우가 있다. 그래프는 이진 트리에서 제약을 제거한 거라는 식으로) 저 두 자료구조는 가장 중요하다.
데이터를 컴퓨터로 처리하는 방식을 다루는 것이기 때문에, 구현을 생각하지 않는 아주 추상적인 이론이 아닌 이상 반드시 사용해야만 하는 기초 이론이다. 프로그래머와 코더의 차이는 이 자료구조와 알고리즘의 이해 정도에 달려 있다고 해도 좋다. 최소한 메모리가 1차원 구조라는 사실을 인지하고 있질 않으면 그 사람은 코더다.
그러니까 2차원 배열에 접근할 때 C언어로 arr[y][x] 과 arr[0][y * width + x] 이 왜 같은지를 이해하지 못하면 그 사람은 코더다. [2]
학교에서는 주로 기초 컴퓨터 프로그래밍 언어를 익힌 후 배우므로, 대학교 컴퓨터 계열 학과의 1학년 2학기에서 2학년 1학기 쯤 대부분 수강하게 되며, 가끔가다 1학년 1학기에 같이 시작하는 곳도 있다. 다만 정보계열 실업계 고등학교 학생들의 경우 2학년부터 배우게 되는데 덕분에 프로그래밍 기초나 작업과 같은 과목에 대해선 의외로 강세를 보이기도 한다. 다만, 과목 이름만 자료구조이고, 엑셀, 파워포인트 등을 하는 경우도 있다.
간단한 리스트부터 수업에 따라 B-트리까지 익히는 편이다. 이 과목이 자료구조를 직접 활용하기 때문에 중요하다기 보다는, 프로그램을 작성할 때 되는대로 막 짜는 게 아니라 한 번이라도 전체적인 프로그램의 흐름(혹은 구조)에 대해 생각하게 만들기 때문에 중요하다. 한국에서 거의 이러한 일이 일어나지 않지만, 운영체제 또는 특정 목적으로 동작하는 프로그램 엔진 등을 제작하게 될 때에는 정말 잘 알아야 하는 과목이다. 자료 구조에 따라 프로그램 자체의 지원 가능한 기능과 성능 자체가 확확 바뀌는 경우가 발생하기 때문이다. 이러저러한 이유로 여러 컴퓨터 과목에서 전공심화 과목들은 기본적으로 이 과목을 요구하는 경우가 많다.
정렬과 이진 탐색은 엄밀히 말해 자료구조가 아닌 알고리즘에 속하지만, 배열 등의 자료구조와 밀접하게 연관되고 알고리즘 중에서도 비교적 쉬운 축에 속하므로 대부분 함께 배우는 경우가 많다. 자료구조도 좀 깊이 들어가 보면 어떤 알고리즘을 사용하기 위해 개발된 것들이 많다.
2 자료구조의 종류
- 혼합 자료구조(Composite Data Structure)
- 배열 (Array)
- 선형 자료구조(Linear Data Structure)
- 추상적 자료구조(Abstract Data Structure)