개념 정리 - (4) 자료 구조 편
우리가 배운 개념이 어디서 어떻게 쓰이는지 알아보자
드디어 본격적으로 코딩의 영역에 들어서게 됐다. 일상적으로 쓰고 있던 배열부터 시작하여 얼핏 봐서는 잘 이해가 되지 않는 복잡한 자료 구조까지, 자료 구조의 세계는 방대하다. 학부 수준 자료 구조 강의에서는 보통 힙이나 해싱까지 다루는 것 같다. 트리와 같은 자료 구조들은 배우면서도 왜 배우는지 잘 이해하지 못하는 경우가 많은데, 실제 예를 들어가면서 필요성을 설명해보도록 하겠다.
자료 구조들의 공통적인 특징은 정해진 규칙대로 자료를 다룬다는 것에 있다. 예를 들어 이진 검색 트리는 부모 원소의 왼쪽 자식이 부모보다 작고, 오른쪽 자식이 부모보다 크다는 규칙이 있다. 이러한 규칙 하에 이진 검색이 가능하기 때문에 검색 속도가 빨라질 수 있다.
모든 경우에 적합한 자료 구조는 없다. 예를 들어 배열은 순차 탐색이 빠르게 가능하지만 중간 삽입, 삭제가 매우 느리다. 연결 리스트는 중간 삽입, 삭제를 빠르게 할 수 있지만 임의 접근이 느리다. 매우 적은 자료를 다루는 경우엔 두 자료 구조상의 차이를 느끼기 어렵지만 데이터베이스와 같이 수 백 만개 이상의 자료를 다뤄야 하는 경우 시간 복잡도 O(N)과 O(logN)의 실제 연산 시간 차이가 어마어마하게 난다. 일반적인 서비스를 운영하는 상황에서 한 물리 서버가 1초에 몇 개의 요청도 처리하지 못한다고 생각해보면 허용될 수 없는 일이라는 것을 알 수 있을 것이다. 그렇기 때문에 주어진 상황에 알맞은 자료 구조를 선택해야 한다.
기억해두자. 우리가 원하는 것은 방대한 자료들을 다루면서도 매우 빠른 시간 안에 원하는 결과를 낼 수 있도록 하는 것이다.
추상적 자료 구조
추상적 자료 구조에서는 구현을 분리하여 생각한다. 후술 할 스택 자료 구조를 정의할 때 push나 pop과 같은 연산을 정의하고, 그 연산이 연산 복잡도 O(1)을 만족하기만 한다면 어떻게 구현하든 상관하지 않는다. 인터페이스와 구현을 분리하여 생각하자는 것이다. 그렇기 때문에 큐를 배열로 구현된 것을 쓸 수도 있고, 연결 리스트로 구현된 것을 쓸 수도 있다.
종종 자료 구조 전체를 순회하는 작업이 필요할 때가 있다. 구현이 어떻게 되어 있는지 알지 못하기 때문에 이를 해결하는 방법으로 Iterator 패턴이 나타난다. Iterator 패턴이 아주 잘 정의되어 있는 것이 바로 C++ STL의 Iterator이다. 각 컨테이너마다 Iterator가 제공되어 begin부터 end까지 순회 가능하게 한다.
더불어 이 항목에서 설명하고 싶은 것으로 비교자(Comparator)가 있다. 숫자에 대한 비교는 이미 정수론적으로 정의되어 있지만, 문자열 자료만 봐도 어떤 경우에는 문자열 길이가 긴 것이 더 큰 것이라 생각할 수도, 사전 순에서 나중에 있는 것이 더 큰 것이라 생각할 수도 있다. 이렇듯 자료에 대한 비교 자체도 추상적 개념에서 접근해야 한다. 그렇기 때문에 비교 연산이 필요한 자료 구조의 경우 자료 구조 선언 시 비교자를 함께 제공해줘야 하는 경우도 있다. 가장 대표적인 예가 우선순위 큐이다.
스택과 큐
배열을 제외하고 가장 기본적인 자료 구조라고 할 수 있는 스택과 큐. 선입 후출(First In Last Out), 선입 선출(First In First Out) 방식인 자료구조가 뭐가 유용하겠나 싶겠지만 실제로 곳곳에서 많이 쓰인다. 함수 호출 스택과 메세지 큐가 스택과 큐 자료 구조를 활용한 대표적인 예이다. 웃기게도 이름에 이미 자료 구조가 드러나있다. 자료를 앞 뒤로도 삽입과 삭제를 가능하게 고안한 덱(dequeue)이라는 자료 구조도 있지만, 이 글에서는 스택과 큐까지만 다루겠다.
출처 : http://russell.ballestrini.net/occupy-wall-street-stack-vs-queue/함수를 호출하면 실행 흐름이 그 함수로 넘어간다. 그 함수에서 또 다른 함수가 실행될 수도 있고, 실행을 끝내고 함수를 빠져나올 수도 있다. 함수에서 빠져나오면 마지막에 함수를 실행했던 곳으로 돌아온다. 이렇게 작동될 수 있도록 하기 위해 프로그래밍 언어론적으로 함수 실행 시 활성 레코드(Activation Record)를 쌓는다고 말한다. 활성 레코드에는 함수를 종료한 뒤 돌아가야 할 주소와 현재 활성 레코드의 크기에 대한 정보가 포함되어 있기 때문에, 함수 스택을 정리할 때 활성 레코드를 참고하여 규칙적으로 운영할 수 있다. 함수 스택에 새로운 활성 레코드를 추가할 때 스택에 활성 레코드를 push 하고, 함수를 종료할 때 활성 레코드를 pop 하는 것이다.
메세지 큐는 다양한 곳에서 응용된다. scanf와 같은 동기 입력 함수를 실행하면 사용자의 입력을 기다리는데, 터미널에 키보드를 입력하면 입력이 수행되는 것을 볼 수 있다. 이는 OS가 키보드에서 생긴 이벤트를 프로세스의 이벤트 큐에 넣어주는 것인데, 이벤트 큐는 메세지 큐의 대표적인 예 중 하나이다. 메세지 큐 자체가 또 하나의 추상적인 개념이기 때문에 프로세스 간 통신(Inter Process Communication)을 비롯한 여러 곳에서 활용되는 개념이다.
연결 리스트
10개의 원소를 가진 배열을 선언해서 사용하고 있다고 생각해보자. 그런데 보관해야 할 원소가 11개로 늘어났다. 갖고 있던 데이터를 버릴 수는 없다. 해결 방법은 11개 이상의 원소를 가질 수 있는 배열을 선언하고 기존의 배열 내용을 복사하는 것이다. 만약 1억 개의 데이터를 보관하고 있던 상황이라면? 배열을 복사하는 것 자체가 엄청난 연산을 요구하는 작업이 된다. 중간중간의 원소에 대해 삽입과 삭제가 빈번히 발생한다면 그 또한 배열 구조에서는 부담이 크다.
출처 : https://en.wikipedia.org/wiki/Linked_list연결 리스트가 이러한 상황에 유용한 구조이다. 연결 리스트의 원소는 다음 원소를 가리키는 포인터를 갖고 있기만 하기 때문에 중간 삽입이나 삭제를 할 때면 포인터만 잘 처리해주면 된다. 배열을 사용할 때처럼 한 칸씩 원소를 다 밀어내거나 당겨오는 복사 작업을 해야 할 필요가 없기 때문에 유용하다. 그러나 임의 원소 접근이 느리기 때문에 잦은 임의 원소 접근이 필요한 경우엔 적합하지 않다.
파일 시스템의 가용 디스크 블록을 연결 리스트로 관리하는 것이 연결 리스트를 활용한 예 중 하나이다. 디스크의 물리 디스크는 블록이라는 단위로 파일 시스템에 의해 관리되는데 파일이 더 많은 공간을 필요로 하게 될 경우 파일 시스템에게 추가적인 디스크 블록을 요청하여 할당받는다. 파일 시스템은 가용 디스크 블록 리스트에서 하나를 빼내어 파일에게 할당해준다.
데이터베이스에서 없어서는 안 될 자료 구조인 B-tree에서도 단말 노드 간의 연결을 위해 연결 리스트가 사용된다. 단말 노드를 순차적으로 순회하기 위해서는 단말 노드의 연결 리스트를 차례로 순회하면 된다.
트리
트리는 마치 나무가 자라는 것처럼 생긴 자료 구조이다. 이름도 그래서 트리다. 아마 직관적으로 의미를 느끼기 어려워지기 시작하는 자료 구조일 것이다. 배열로 구현할 수도 있긴 하지만, 개념 자체는 배열처럼 생긴 구조가 아니다 보니 순회 방법 또한 따로 정의되어 있어서 더욱 이해를 어려워하는 것 같다. 트리는 connected component이면서 cycle이 존재하지 않는 특수한 그래프라고 볼 수 있다. 문제를 그래프 개념으로 탐색을 적용할 때도 트리 순회 개념이 적용된다.
출처 : https://www.raywenderlich.com/138190/swift-algorithm-club-swift-tree-data-structure트리를 자료 구조로서 활용하는 대표적인 예가 검색일 것이다. 익히 알고 있듯이 이진 검색은 O(logN)의 시간 복잡도를 보인다. 이는 검색을 해나갈 때 고려 대상을 1/2씩 줄여나갈 수 있는 방법이기 때문이다. 이 개념을 좀 더 확장하여 정확히 값이 같지 않더라도 비교가 가능한 점을 이용한 것이 데이터베이스의 B-tree 구조이다. 트리 구조를 발명해내지 못했다면 지금처럼 빠르게 동작하는 프로그램들이 만들어질 수 없었을 것이다.
검색을 빠르게 수행하려면 필수적인 것이 트리의 깊이를 최대한 키우지 않는 것이다. 깊이가 깊어지면 깊어질수록 비교를 수행해야 하는 횟수가 늘어난다. 트리 전체가 메모리에 올라와있는 경우에는 큰 문제가 되지 않지만 디스크에 저장된 트리(데이터베이스의 인덱스 트리)는 비교를 수행할 때마다 디스크에 접근해야 하기 때문에 깊이가 1만 증가해도 매우 느려진다. 그렇기 때문에 균형 트리(Balanced Tree)를 유지하는 것이 중요한 문제가 되며, AVL 트리를 배우는 것은 자가 균형 트리를 유지하는 방법 중 하나를 알아보기 위함이다.
힙은 완전 이진 트리(Complete Binary Tree)이며 최댓값이나 최솟값을 빠르게 찾아내기 위한 자료 구조로 활용된다. 신묘한 방법으로 노드를 추가하거나 삭제할 때마다 일정한 처리를 함으로써 루트 노드는 항상 최댓값이거나 최솟값이 되도록 한다. 이 방식을 이용하여 우선순위 큐를 구현할 때 힙을 이용하여 구현하기도 하며, 힙 정렬 또한 힙 구조를 이용한 정렬 방법이다.
최소 신장 트리(Minimum Spanning Tree)라는 개념도 있다. 네트워크 망을 그래프 개념으로 볼 때 최소 신장 트리를 만들면 최소한 각 네트워크 노드들이 모두 연결되어 있음을 보장한다. 파일 시스템의 디렉토리 구조 또한 트리 구조로 이루어져 있다. 이렇듯 트리 구조는 다양한 분야에서 그 개념을 적용할 수 있다.
그래프
그래프는 일련의 꼭짓점(Vertex)들과 그 사이를 잇는 변(Edge)들로 구성된 조합론적 구조이다. 정의가 간단한만큼 세부 종류도 다양하다. 꼭짓점은 노드(Node)라고 부르기도 한다. 변이 방향성을 가지는지에 따라 유향 그래프 또는 무향 그래프로 분류하고 꼭짓점을 이분할 수 있는지에 따른 이분 그래프, 변과 변이 교차하지 않을 수 있는지에 따른 평면 그래프 등 다양한 그래프가 존재한다.
출처 : http://www.introprogramming.info/english-intro-csharp-book/read-online/chapter-17-trees-and-gra그래프를 자료 구조로써 표현하는 방법도 여러 가지다. 2차원 배열을 이용하여 인접 행렬로 표현하기도 하고, 각 정점마다 연결된 정점을 리스트로 표현하는 인접 리스트로 표현하기도, 변들을 리스트로 가지는 엣지 리스트로 표현하기도 한다. 희소 그래프일 경우 인접 행렬보다 인접 리스트로 표현하는 것이 메모리를 많이 절약할 수 있으나 인접 리스트로 구현할 경우 특정 노드와 노드 사이가 연결되어 있는지 확인하는 것이 느리기 때문에 상황이나 알고리즘에 따라 잘 선택해야 한다.
문제를 그래프로 형상화하여 푸는 경우가 많기 때문에 알고리즘을 많이 생각해야 하는 문제를 만나게 될 경우 그래프를 심심찮게 만나게 된다. 한 노드에서 다른 노드까지의 이동 비용을 변의 가중치로 두고 최단 거리 경로를 구하는 문제가 익숙할 것이다. 이 문제의 실제 예는 네트워크 망에서 패킷을 빠르게 이동하기 위한 라우팅 알고리즘이다. 여기서 다익스트라의 최단 경로 알고리즘이 등장한다. 알고리즘까지 다루는 것은 이번 편의 주제를 벗어나므로 다음 편에서 다루겠다.
해시 테이블
해시 테이블은 해시 함수로 인덱스를 결정하여 O(1)의 시간 복잡도로 원하는 데이터를 찾기 위해 고안된 자료 구조이다. 어떤 값을 해시 함수를 거쳐 나온 결과 값을 인덱스로 하여 해당 인덱스의 버킷으로 바로 접근하는 아이디어이다. 당연히 해시 함수가 고르고(uniform) 무작위(random)하게 값을 해시해야 한다. 어떤 해시 함수가 고르고 무작위한지 증명하는 것은 매우 어려운 문제이기 때문에 완전히 고르고 무작위한 해시 함수를 만들기보다는 적당한 해시 함수를 사용하면서 충돌을 잘 처리해주는 방식을 사용한다. 충돌 처리를 위해서는 Overflow chaning, Open hashing 등의 방법을 사용한다.
출처 : http://vhanda.in/blog/2012/07/shared-memory-hash-table/앞서 말한 정적 해싱 방법은 충돌 처리가 실용적이지 않기 때문에 실제 자료 구조로 쓰기 위해서는 동적 해싱 방법을 사용하며, 동적 해싱을 이용한 자료 구조는 데이터베이스의 인덱스 방식 중 하나로 활용된다. 자꾸 데이터베이스를 예시로 쓰는 것 같지만, 실제로 데이터베이스는 자료 구조를 잘 활용해야 하는 프로그램 중 하나이기 때문에 자료 구조의 예로 많이 들 수밖에 없다. 동적 해싱 방법으로는 Exendible hashing, Linear hashing 등이 존재한다.
이것으로 몇 가지 주요 자료 구조들을 알아보았다. 다음 편에서는 알고리즘을 다루겠다.
