모두의 코드
모두를 위한 자료구조
컴퓨터가 수행하는 작업은 크게 두 가지로 볼 수 있습니다. 하나는 컴퓨터 라는 이름에서도 알 수 있듯이 답게 엄청난 양의 연산(Computation) 을 하는 수행하는 것이고, 다른 하나는 데이터를 저장하고 불러오는 것입니다.
컴퓨터 알고리즘이 첫 번째 항목에 집중을 한다면, 자료 구조는 두 번째 부분에 대해서 중점적으로 다룹니다. 컴퓨터의 자원은 한정되어 있기 때문에 컴퓨터 과학자들은 어떻게 하면 데이터를 효율적으로 저장하고 또 빠르게 불러 올 수 있을까 에 대해서 많은 고민을 하였습니다. 이에 데이터를 효율적으로 컴퓨터에서 다루기 위해서 자료 구조 (Data Structure) 라는 분야가 탄생하게 됩니다.
예를 들어서 간단히 구글의 검색 엔진을 생각해봅시다. 2020년 현재 일반적으로 웹에서 접근할 수 있는 웹 페이지의 양은 대략 60 억개 가량 된다고 합니다. 그런데 우리가 검색을 하게 되면 우리가 검색한 내용과 가장 잘 일치하는 웹사이트들 몇 개를 뽑아서 보여주죠.
만일 적절한 자료 구조를 사용하지 않았다면 우리가 검색을 수행할 때 마다 매 번 60 억 개에 달하는 페이지를 하나 하나 탐색해봐야 했을 것입니다. 이 경우 아무리 구글에 서버 컴퓨터들이 많다고 하더라도 검색 결과를 1 초 만에 볼 수 는 없겠죠.
아니면 우리가 흔히 사용하는 길찾기 기능을 생각해봅시다. 지도 상의 길들과 빌딩들은 그래프로 표현할 수 있기 때문에 알고리즘을 배우신 분들은 아시겠지만 길찾기 기능은 그래프 상에서의 최단 경로 문제와 유사하다고 볼 수 있습니다. 최단 경로를 빠르게 찾는 방법으로 다익스트라(Dijkstra) 알고리즘이 있는데, 아무리 다익스트라가 빠르다고 하더라도 수 백만개의 길들과 집들이 있는 마당에서 매 번 다익스트라로 최단 경로를 찾는 다는 것은 서버에 큰 부담이 될 것입니다.
하지만 한 가지 다행인 것은 길이나 빌딩은 자주 바뀌지 않는 다는 것입니다. 따라서 적절한 자료구조를 사용해서 지도 그래프를 미리 잘 처리해놓는다면 임의의 두 위치의 최단 경로를 요청했을 때 순전히 맨 바닥에서 다익스트라를 돌리는 것 보다 훨씬 빠르게 처리할 수 있습니다.
이렇게 적절한 자료구조를 사용하면 단순히 데이터를 보관했을 때에 비해서 엄청난 성능 향상을 불러올 수 있습니다. 반대로 말하자면, 올바르지 않은 자료 구조를 사용했을 때 많은 컴퓨터 자원을 낭비할 수 도 있다는 이야기 이지요. 따라서 올바른 자료 구조를 사용하는 일은 굉장히 중요합니다.
강의 목표
앞으로의 강의에서는 프로그래머라면 꼭 알았으면 좋겠는 여러 가지 자료 구조들에 대해서 소개할 것 입니다. 이 때 어느 자료 구조를 다루던지 간에 항상 두 가지 측면으로 접근할 것입니다.
자료 구조의 이론적인 측면
자료 구조의 실재적인 측면
먼저 자료 구조의 이론적인 측면이라 하면 수학적으로 이 자료 구조의 작동 방식을 분석한다는 의미 입니다. 쉽게 말해서 실제 코드를 가지고 컴퓨터 상에서 실행한다기 보다면 의사 코드 (pseudo code) 를 통해 이 자료구조가 왜 잘 작동하고 또 수학적으로 이 자료 구조가 어느 정도의 속도를 보장하는지 에 대해 다룬다는 의미 입니다. 이를 통해서 강의를 읽는 여러분들이 해당 자료 구조의 동작 원리에 대해 좀더 잘 이해할 수 있었으면 좋겠습니다.
두 번째로는 자료 구조의 실재적인 측면 입니다. 이 부분에서는 해당 자료 구조를 실제 컴퓨터 언어로 구현해서 (제 경우 보다 많은 독자들을 위해 C++ 과 Python 두 가지 언어를 사용해서 구현할 예정입니다.) 실제로 실행해 보는 것입니다. 컴퓨터는 수학적인 분석에서 가정하는 이상적인 모델과는 거리가 먼 기계이기 때문에 자료 구조 간의 성능 비교는 직접 실행해보아야 정확합니다. 따라서 이 단계에서는 자료 구조를 어떻게 하면 효율적으로 구현할 수 있는지에 대해서 다루어 볼 예정입니다.
아래 다루는 모든 자료 구조들의 작동 방식을 외울 필요는 없습니다. 더군다나 이들을 직접 구현할 필요도 없습니다. 왠만한 언어에서는 이미 남이 만들어는 구현체가 있고 (혹은 언어 차원에서 지원하고) 이를 그냥 가져다 쓰기만 하면 되기 때문이죠. 다만 대략적인 자료 구조들의 실행 성능정도는 기억한 다음, 실제로 필요할 때 뭘 가져다 쓰면 되느지 정도만 알면 많은 도움이 될 것이라 생각합니다.
강의 목차
배열 (Array)
메모리 상에서 연속적으로 원소들이 존재하는 자료구조들에 대해서 다루어본다.
1 - 1. 배열 (Array)
1 - 2. 크기가 바뀌는 배열; 동적 배열 (Vector)
2. 큐 (Queue) 와 스택 (Stack)
연결 리스트 (List)
3 - 1. 연결 리스트 (Linked List)
3 - 2. 스킵 리스트 (Skip List)
트리 (Tree) 와 힙 (Heap)
4. 이진 트리 (Binary Tree)
5 - 1. 이진 힙 (Binary Heap)
5 - 2. 피보나치 힙 (Fibonacci Heap)
5 - 3. 이항 힙 (Binomial Heap)
5 - 4. Union-Find
자가 균형 트리 (Self Balancing Tree)
6 - 1. B 트리 (B tree)
6 - 2. 레드 블랙 트리 (Red-Black Tree)
여러 특별한 트리들
7 - 1. Binary Index Tree (Fenwick Tree)
7 - 2. 구간 트리 (Interval Tree)
7 - 3. 구간 최소 쿼리 (Range Minimum Query)
8. 스플레이 트리 (Splay Tree)
해싱 (Hashing) 을 활용한 자료구조들
9 - 1. 해시 테이블 (Hash table) 기초 (체인 기반)
9 - 2. 선형 탐색 기반 해시 테이블 (Linear Probing)
9 - 3. 뻐꾸기 해싱 (Cuckoo Hashing)
스케치 (Sketch)
10 - 1. 블룸 필터 (Bloom Filter)
10 - 2. Count-min Sketch
문자열 관련
11 - 1. 접미사 트리 (Suffix Tree)
11 - 2. 접미사 배열 (Suffix Array)
댓글을 불러오는 중입니다..