전기정보공학부: 자료구조의 기초

1. 과목에서 배울 수 있는 내용

0) 과목의 전반적인 개요

자료구조의 기초는 전기정보공학부에서 2학년을 대상으로 개설되는 전공선택필수 과목입니다. 졸업을 위해 필수적으로 들어야 하는 과목은 아니지만, 소위 말하는 컴텍(컴퓨터 테크)을 선택하신다면 듣는 것을 매우 추천합니다. 컴퓨터의 개념 및 실습과 프로그래밍 방법론을 수강한 이후, 프로그래밍을 할 때 사용할 수 있는 자료 구조에 무엇이 있는지, 그리고 각 자료 구조 별 특징(메모리, 연산 속도) 등을 배울 수 있습니다. 각각의 특징을 이해하고 이를 통해 내가 작성하려는 프로그램에 맞는 메모리와 연산 속도를 가지는 자료구조를 잘 선택하도록 하는 것에 수업의 목적이 있습니다.

1) 자료 구조

C++, C, 자바 등 다양한 언어를 이용해서 프로그래밍을 할 때, 프로그램에서 사용하는 데이터를 어떻게 저장할 지 선택하는데, 이 때 선택할 수 있는 다양한 자료구조가 존재합니다. 자료 구조는 그 형태에 따라 다양하게 나뉘는데 대표적인 것만 설명하면 아래와 같습니다.

가장 쉽게 생각해볼 수 있는 자료 구조는 List, Stack, Queue가 있습니다. List의 경우 데이터가 연속해서 이어진 구조로 Single/double linked list로 나눌 수 있습니다. Stack의 경우 후입선출(Last in First Out)의 구조를 가진 자료 구조로, one-ended array 또는 single linked list 등으로 구현이 가능합니다. Queue의 경우, 이런 stack과는 반대로 선입선출 (First In First Out)로, 일반적으로 single linked list 또는 circular array등으로 구현합니다. 

Tree는 계층적인 자료구조로, 각각의 node에 정보를 저장하게 되며, 각각의 parent-child관계로 데이터가 정리되게 됩니다. 말 그대로 나무 모습으로 데이터가 저장됩니다. Tree에도 여러 종류가 존재하는데 AVL tree, RB tree, B tree 및 B+ tree 등이 있습니다. 해당 내용까지 적기에는 너무 깊게 들어가는 감이 있으므로 자세한 내용은 따로 찾아보시거나 수업에서 확인하면 좋을 것 같습니다.

Hash Table의 경우 hash function을 사용해서 연산시간을 상수로 가져가게 하는 자료 구조로 각 데이터는 이 함수를 통해 특정 값을 가지게 되고, 이 값으로 바로 데이터에 접근이 가능합니다. 그러나 이는 이론적인 내용으로 실제로는 데이터 충돌 등의 문제로 여러 가지 어려움이 있습니다. Hash table도 chained hash table, open addressing(linear 또는 quadratic probing) 등으로 다양하게 구현됩니다.

Priority Queue의 경우 일반적인 선입선출의 Queue와 달리, ‘우선순위’를 주어 우선순위가 높은 자료를 먼저 pop하는 자료구조이며, binary heap은 이진 트리의 한 종류로 부모가 자식보다 크거나(max heap) 작은(min heap) 자료 구조입니다.

2) 메모리 및 연산 속도

1)과 같이 자료구조를 항상 같은 것을 선택하지 않고 필요에 따라 취사 선택하는 이유는 이러한 자료구조에 따라 필요한 메모리와 연산 속도가 다르기 때문입니다. 이를 시간/공간 복잡도라고 표현하며 big-o notation O(f(n))을 이용해서 나타냅니다.

f(n) < k * g(n)이 모든 n > n_0 에 대해 만족하게 하는 상수 k와 n_0가 존재한다면 f(n) = O(g(n))이라고 표기합니다.

예를 들어 연산 시간이 f1(n) = 3n+1과 f2(n) = n인 두 경우 모두 O(n)의 시간복잡도를 가진다고 할 수 있으며, f3(n) = n^2 + 3n +2의 경우 O(n^2)의 시간복잡도를 가집니다. 

3) 정렬

정렬은 말 그대로 데이터를 어떤 순서에 의해서 정렬하는 것을 뜻합니다. Insertion, Heap, Merge, Quick, Bucket 등의 다양한 정렬 방법이 있으며 이를 실습 시간을 통해 직접 구현해봅니다. 

Insertion, Bubble, Selection sort등의 경우 알고리즘 자체가 떠올리기 쉽고 직관적인데요, 그만큼 효율성 면에서는 떨어진다고 볼 수 있습니다. 앞서 언급했던 시간복잡도가 O(N^2)으로 표현이 됩니다. Merge Sort, Quick Sort, Heap sort등은 조금 더 효율적인 O(nlogn)의 시간복잡도를 가집니다. 예를 들어, Merge Sort와 같은 경우에는 자료를 반으로 나눠서 그 각각을 정렬한 후 다시 하나로 합치는 정렬로, bubble sort등과 비교해 더 빠르게 이루어지게 됩니다. 실제로는 Quicksort가 가장 널리 사용이 되나, 이를 포함한 다양한 정렬방법을 여기서 설명하는 것은 과한 것 같고 관심이 있으시면 수업을 수강하시거나 찾아보시면 좋을 것 같습니다. 이러한 정렬 방식에 따라서 자료의 크기가 커질 수록 연산에 필요한 시간이 크게 달라지기 때문에 정렬 알고리즘이 중요하다고 할 수 있습니다.

4) 그래프

그래프는 vertex, edge를 가지는 구조로 adjacency matrix, adjacency list, relation list등을 통해 표현됩니다. 일반적으로 DAG(Directed Acyclic Graph)가 많이 사용됩니다.  이런 그래프를 통해 topological sort, dijkstra’s algorithm 등 여러 알고리즘을 배우게 되는데, 이 부분은 자료구조와 직접적으로 관련된 내용이라기보다는 향후 알고리즘의 기초 수업을 수강하는데 더욱 더 도움이 될 수 있는 부분입니다.

 

2. 선배의 조언

1) 공부법(도움되는 책, 영상자료, 유튜버 등 추천)

대부분 교수님의 수업과 ppt로 공부가 되지만, 혹시 부족한 부분이 있다면 유튜브를 참고하시는 것도 도움이 될 수 있습니다. 특정 유튜브 영상이나 채널을 추천하기 보다는, 기초적인 내용인만큼 다양한 영상이 있기 때문에 적절한 영상을 찾아서 공부하는 것도 도움이 됩니다. 해당 과목을 공부함에 있어서 가장 중요한 것은 과제로 나오는 것처럼 수업시간에 언급된 해당 자료구조, 수업 시간 후반부에 나오는 몇 알고리즘을 본인이 직접 구현해보는 것입니다. 특히 RB tree 등의 비교적 생소한 자료구조는 확실히 직접 구현하는 것이 단순히 수업으로 들을 때보다 이해하기 편하니 혼자 구현해 보는 것을 추천드립니다. 이 때 당연한 말이겠지만 구글링 등은 최대한 하지 말고 혼자 생각으로 하는 것이 중요하다고 생각됩니다.

2) 동시수강/선수강 과목 추천

컴퓨터의 개념 및 실습과 프로그래밍 방법론 수업은 우선적으로 수강하시는 것을 매우 권장드립니다. 강의 자체는 특정 프로그래밍 언어를 몰라도 이해할 수 있지만, 실습 과제에서 사용하는 C++ 언어에 익숙하지 않다면 과제를 해결하기 어렵습니다. “알고리즘의 기초” 수업은 3학년 수업으로, “자료구조의 기초”를 수강한 후에 듣는 것이 학과에서 말하는 순서이지만, 실제로는 이 두 수업을 동시에 수강하는 것도 나쁘지 않은 선택입니다. 

컴퓨터 테크를 타기로 결심하셨다면, 해당 수업과 알고리즘의 기초 수업을 들은 후, 어느 레벨의 컴퓨터를 하고 싶은지에 따라 후속 과목의 수강 계획을 다른 방향으로 설정할 수 있습니다.

컴퓨터공학부에서 개설되는 ‘자료구조’ 수업과 사용하는 언어를 제외하고는 비슷하게 수업이 진행되는데, 해당 내용은 전공 백서 '컴퓨터공학부: 자료구조'에서 확인해주세요.

3) 진로 선택에 도움되는 점

전공선택필수인만큼 수강을 하지 않으면 졸업을 하지 못한다 정도의 중요성을 가지는 과목은 아니겠지만, 그래도 전기과라면 들어서 나쁠 것이 없는 강의입니다. 컴퓨터 테크를 선택한다면 로우 레벨을 한다고 하더라도 자료 구조의 기초 정도는 알아놓는 것이 중요하다고 볼 수 있습니다.

기초 과목인 만큼, 특정 회사나 연구 분야와 연결되어 있기보다는, 어떤 연구 분야든 컴퓨터 프로그래밍이 조금이라도 연관이 되어있다면 필수적이라고 볼 수 있을 것 같습니다.

 

3. 맺음말

이 과목은 컴퓨터 쪽으로 계속 공부할 생각이 있는 학생에게 좋은 과목이며, 다른 쪽으로 나갈지라도 도움될 수업입니다. 프로그래밍을 하면서 적절한 자료 구조의 선택이 속도와 필요한 메모리 등에 큰 영향을 미치게 되는데, 이런 다양한 자료 구조에 대해 배울 수 있으며 실습 시간에서 해당 자료구조를 직접 구현해볼 수 있습니다.