PlanB의 백엔드 엔지니어링

최근에 Markov Chain이라는 것을 듣게 됐다. 이게 사실은 확률론의 '확률 과정'이라는 곳에서 나오는 개념인데, 필자는 수학 찐따라 기본적으로 위키피디아에서 설명하는 정의는 이해하지 못한다.

첫 문장부터 확률 공간, 가측 집합, 가측 공간같은 소리를 하는데다, markov chain에 대해 잘 정리된 것 같은 글들은 수학적 배경이 너무 많이 필요해서 여기에 좀 정리해보려고 한다.

Markov Chain

Markov Chain은, Markov Property를 지닌 이산 시간 확률 과정(Discrete-time Stochastic Process)을 의미한다(라고 설명하고 있다). 무작정 정리하기 전에, 그냥 Markov Chain의 예를 직접 보도록 하자.

Markov Chain의 예와 이의 해석

위 그림의 s, c, r을 state(상태)라고 부르고, 각 state 사이에 이어진 유향 선분(화살표)에 대해 할당된 가중치들은 해당 상태 전이가 이루어질 수 있는 확률을 의미한다(확률론에서 항상 그러는지는 모르겠으나, Markov Chain에서는 확률을 표현할 때 0~100%에 대한 구간을 [0, 1]로 두어 대응시키고 있다). 위 그림의 경우, s에서 c가 될 확률이 0.3(30%)이고, c에서 r이 될 확률이 0.5(50%)같은 식으로 해석하면 된다. 조건부 확률을 떠올려서 P(s|c)=0.3, P(c|r)=0.5같이 봐도 되고. 그렇다면 위 markov chain을 기준으로 했을 때, 오늘 날씨가 맑음(s)이고, 내일 날씨가 비(r)이며 모레 날씨가 맑음(s)이 될 확률은 P(s|r) * P(r|s) = 0.1 * 0.4 = 0.04가 될 것이다.

다시 정리하면

Markov Chain은 그냥 어떤 state를 정의하고, 그 state들 각각에 대한 전이 확률을 정의해둔 채 이거 갖고 짝짝꿍 하는 거다. 다시 정리하면, 위처럼 sunny, cloudy, rainy같은 state(상태)가 존재하고, 각 state를 넘나드는 확률값이 존재해서 이게 chain처럼 구성되어 있고, 상태 전이 확률이 항상 현재 state에만 의존한다면(예를 들어 s → c라는 전이의 확률이 r에 의존하지 않는다면), 이를 Markov Chain이라고 부른다. 여기서 '상태 전이 확률이 항상 현재 state에만 의존하는 것'이 Markov Property를 나타낸다.

근데 뭐 sunny, cloudy, rainy 이런 것만 봐서 이게 도대체 얼마나 유의미한 것을 도출해낼 수 있을까 싶을텐데, real world에선 이런 곳에 쓰이고 있다.

• Markov Chain에서, chain이 커지면(상태 전이 횟수가 늘어나면) 특정 state에 전이될 확률이 고정된 값으로 수렴한다고 한다. 웹 전체를 markov chain으로 두었을 때, '서핑이 오랜 시간 이루어진다'고 가정하면 특정 웹 페이지 X에 도달하는 것은 고정 확률이라고 볼 수 있다. Google의 Page Rank 알고리즘이 markov chain 이론을 기반으로 만들어졌다고 한다.
• 안드로이드의 Google 키보드에는 'Google 키보드를 개선하기 위해 Google 어플리케이션에 입력하는 내용 공유'라는 옵션이 있다. 이게 켜져 있으면, 우리가 타이핑하는 단어들이 Google로 보내져서 Markov Chain에 반영되고, 이를 통해 Google은 단어 예측(Typing Word Prediction)을 수행한다.
• 음성 인식, 추천 엔진 등 상태 전이 확률을 통해 뭔가 예측할 필요가 있는 곳들에서 Markov Chain을 자주 사용하고 있다고 한다.

Binary search tree(이진 탐색 트리)는 아래의 전제조건들이 존재하는 이진 트리다.

• 모든 노드의 값은 유일하다.
• 값들은 전순서가 있다(임의의 두 원소의 비교가 가능하다).
• 어떤 노드의 왼쪽 서브트리는 그 노드보다 작은 값을 가진 노드들로 이루어져 있다.
• 어떤 노드의 오른쪽 서브트리는 그 노드와 같거나 큰 값을 가진 노드들로 이루어져 있다.
• 좌우 서브트리는 각각이 이진 탐색 트리여야 한다.

탐색

이진 탐색 트리에서 값 x를 가진 노드를 탐색하고자 할 때, 트리에 해당 값을 가진 노드가 존재하면 해당 노드를 반환하고, 존재하지 않으면 NULL을 반환한다고 가정해 보자.

• 값이 root node와 일치하는 경우, root node를 반환한다.
• x가 root node보다 작은 경우, 왼쪽 서브트리에서 재귀적으로 탐색한다.
• x가 root node보다 큰 경우, 오른쪽 서브트리에서 재귀적으로 탐색한다.
• 더이상 탐색할 서브트리가 없다면, NULL을 반환한다.

기본적인 탐색 알고리즘인 이진 탐색과 매우 유사하다.

삽입

• 삽입을 하기 전, 탐색을 수행한다.
• 탐색을 모두 마친 뒤, 삽입하려는 key와 일치하는 노드가 존재하면 삽입에 실패한다.
• 일치하는 노드가 존재하지 않으면(위에 작성한 탐색 순서에 따라, NULL이 반환되면), 가장 마지막으로 탐색한 서브트리의 root node와 값을 비교한 뒤 작으면 왼쪽, 같거나 크면 오른쪽에 해당 노드를 삽입한다.

각 노드들은 값에 대해 unique해야 하기 때문에, 삽입 전 탐색 과정이 존재한다.

삭제

삭제도 삽입과 동일하게 먼저 탐색을 수행하고, 노드가 존재하는 경우에만 삭제를 수행한다. 삭제는 삭제 대상이 되는 노드의 자식 수에 따라 동작이 달라진다.

• leaf node 삭제 : 해당 노드를 단순히 삭제한다. 가장 단순한 형태의 삭제.
• child node가 하나인 노드 삭제 : 해당 노드를 삭제하고, child node를 그 자리에 대입한다.
• child node가 두 개인 노드 삭제 : 해당 노드를 삭제하고, 왼쪽 서브트리에 있는 값 중 가장 큰 값, 또는 오른쪽 서브트리에 있는 값 중 가장 작은 값을 parent node와 연결시켜 준다.

삽입과 삭제가 일어나는 경우, 트리의 한 쪽이 비대해지는 경우가 생긴다. 이로 인해 높이 균형이 맞지 않는(unbalanced) 이진 탐색 트리는, 높이 균형이 맞는(balanced) 이진 탐색 트리에 비해 탐색에 대한 평균 노드 접근 수가 높다. 이는 시간복잡도에 영향을 미치므로, 삽입과 삭제가 일어나는 경우 트리를 높이 균형이 맞도록 변형시켜 트리의 높이를 작게 유지하는 self-balanced binary search tree(자가 균형 이진 탐색 트리)라는 ADT가 있다. 따라서 다음 몇 개의 글에서 self-balanaced binary search tree를 구현하기 위한 이론들에 대해 더 깊게 알아볼텐데, 따라서 Red-black tree처럼 조금 더 우리에게 익숙한 이름들이 보일 것이다.

Tree의 순회는 트리에서 각각의 노드를 정확히 한 번만 방문하는 과정이다. Linked list나 array와 같은 선형 자료 구조는 논리적으로 한 가지의 순회 방법만이 존재하지만, 트리의 순회에는 많은 방법이 존재한다. 순회는 모든 n-ary tree에 대해 일반화될 수 있으나, 가장 자료가 많고 일반적인 binary tree의 순회에 대해서 알아보도록 하겠다.

순회

tree 내부의 tree를 sub-tree라고 부른다. 순회에는 이러한 sub-tree 개념이 등장한다.

전위(preorder) 순회(root-left-right)

• 현재 node를 방문한다.
• 왼쪽 sub-tree를 전위 순회한다.
• 오른쪽 sub-tree를 전위 순회한다.

전위 우선 순회는 깊이 우선 순회(depth-first traversal)라고도 한다. 전위 표기법에서 자주 사용된다.

중위(inorder) 순회(left-root-right)

• 왼쪽 sub-tree를 중위 순회한다.
• 현재 node를 방문한다.
• 오른쪽 sub-tree를 중위 순회한다.

후위(postorder) 순회(left-right-root)

• 왼쪽 sub-tree를 후위 순회한다.
• 오른쪽 sub-tree를 후위 순회한다.
• 현재 node를 방문한다.

왼쪽 sub-tree 순회-오른쪽 sub-tree 순회라는 순서는 고정이고, root node를 언제 방문하는지에 따라 전위, 중위, 후위로 나뉜다. sub-tree들을 동일한 order로 순회하므로 재귀적인 특성이 강하고, 실제로 코드에 옮길 때도 재귀함수를 사용한다.

sub-tree를 순회하는 구조라 순회의 대상이 계속해서 바뀌기 때문에 조금 헷갈릴 수 있으나, 아래의 사진을 보면 이해에 조금 도움이 될 수도 있다.

레벨 순서(level-order) 순회

이는 sub-tree 개념이 들어가지 않고, 낮은 level부터 왼쪽에서 오른쪽 방향으로 순회한다. 너비 우선 순회(breadth-first traversal)라고도 한다.

위 tree를 전/중/후위, 레벨 순서 순회 각각의 방식으로 순회하면,

• 전위 순회 : F-B-A-D-C-E-G-I-H
• 중위 순회 : A-B-C-D-E-F-G-H-I
• 후위 순회 : A-C-E-D-B-H-I-G-F
• 레벨 순서 순회 : F-B-G-A-D-I-C-E-H

n-ary tree는 degree의 최대 수가 n인 tree를 의미한다. '모든 노드가 n개를 초과하는 자식 노드를 가지지 않는 트리'라고도 정의한다. k-way tree, k-ary tree, m-ary tree라고도 불린다. n이 2이면 binary tree가 되고, 3이면 ternary tree가 되는 식이다.

n-ary tree의 특징

높이가 h인 n-ary tree는 최대 n의 h제곱-1만큼의 노드를 가질 수 있다. 예를 들어, 높이가 3인 binary tree는 최대 7개의 노드를 가질 수 있다.

n-ary tree의 종류

complete n-ary tree

완전 트리라고 부른다. 마지막 level을 제외한 모든 level이 완전히 채워져 있으며, 마지막 level의 모든 노드는 가능한 한 가장 왼쪽에 있는 tree다.

perfect n-ary tree

포화 트리라고 부른다. leaf node를 제외한 모든 노드의 차수가 n이며, 모든 leaf node가 동일한 level을 갖는다. 어떤 트리가 perfect tree라면, complete tree이며 full tree다.(모든 노드의 차수가 n이므로)

balanced n-ary tree

균형 트리라고 부른다. 모든 leaf node의 level 차이가 최대 1인 트리를 말한다. 균형 트리는 트리의 주 목적인 '탐색'을 위한 AVL tree, red-black tree 와 같은 자료구조들의 기반이 된다.

skewed n-ary tree

사향 트리라고 부른다. root node를 제외한 노드들이 모두 parent node의 왼쪽에 있거나, 모두 parent node의 오른쪽에 있는 트리다.

Tree도 ADT기에, 여러 방식의 표현법이 존재한다. 트리의 차수나 노드의 수 등에 영향을 끼치지 않는, 모든 경우의 트리를 표현할 수 있는 표현 방식들을 알아보자.

Linked list 표현

선형 자료구조인 linked list를 응용하는 방식이다. 단방향/양방향에 관계 없이 연결 리스트는 오직 연결되어 있는 값과의 link를 위해 사용했는데, 여기서는 child node와의 연결을 표현하기 위해 사용한다.

노드의 삽입과 삭제가 용이하나, 각 노드의 차수만큼 가변적인 포인터 필드를 가져야 한다는 문제가 있다.

Left-Child Right-Sibling(LCRS) 표현

Sibling은 동일한 parent node를 가지고 있는 노드를 의미하며, right sibling은 바로 오른쪽에 있는 sibling을 의미한다. 따라서 LCRS 표현에서는 각 노드가 데이터|가장 왼쪽 child의 주소|바로 오른쪽 sibling의 주소로 이루어진다. 아래 그림은 tree를 LCRS로 표현하는 예다.

대표적인 선형 자료구조가 Stack과 Queue라면, 대표적인 비선형 자료구조로는 Tree와 Graph가 있다고 이야기할 수 있다. 그래프 이론에서는 tree도 graph에 속하고(회로가 없는 연결 무향 그래프를 tree라고 하기 때문) 자료구조에서도 tree가 그래프의 일종이라고 보는 듯 하다.

'나무'라는 의미에 맞게, 뿌리와 가지, 잎 개념이 들어가 있는 계층적 구조를 띄고 있다. 주된 목적은 탐색이며, 따라서 검색 엔진, 데이터베이스, 라우터 알고리즘 등 계층적 데이터를 다루는 수많은 곳에서 응용되고 있다. 아래는 tree의 예다.

현실에서 볼 수 있는 나무와는 다르게 위에서 아래 방향으로 뻗어나오는 모양이다. 따라서 root(뿌리)도 맨 위에 있다. 트리는 기본적으로 Node와 Edge로 구성된다. A, B, C처럼 각각의 요소를 node라고 부르고, node들을 이어주는 간선을 edge라고 부른다. Node는 종류에 따라 아래처럼 나뉜다.

• Root node : tree의 시작점이 되는 노드. 위 그림에서는 A가 root node이며, tree에서 root node는 최대 하나다.
• Parent node : tree의 부분집합을 sub-tree라고 쳤을 때(위 그림에서는 D, H, I로 이뤄진 tree), sub-tree에서의 root node를 의미한다. Root node만 유일하게 parent node가 없다.
• Child node : Parent node에서 뻗어나온 노드를 의미한다. Parent node와 child node는 상대적인 개념이라, 위 그림에서 C는 A의 child node이면서 F와 G의 parent node이다.
• Leaf node : tree의 끝점이 되는 노드(Child node가 하나도 없는 노드). 단말(terminal) 노드라고도 부른다.
• Internal node : Leaf node가 아닌 노드를 의미한다.

Tree에는 해석학의 이론이 존재하기에, 해석에 관련된 몇가지 개념이 들어가 있다. 그들 중 가장 기본적인 게 차수, 높이, 레벨이다.

• 차수(degree) : 어떤 노드가 가지고 있는 child node의 수를 의미한다. 위 그림에서는 leaf node들을 제외하면 E만 차수가 1이다. leaf node는 child node가 없는 노드를 의미하므로 일반적으로 leaf node에 대해서는 차수를 이야기하지 않는다. Tree에서 발견되는 가장 높은 차수를 tree의 차수라고 말하기도 한다. binary tree, ternary tree 등 n-ary tree의 조건이 되는 개념이다.
• 높이(height) : Root node부터 시작하여, 가장 깊게 뻗어나가 있는 leaf node까지의 깊이를 말한다. root node는 높이를 0으로 둔다.
• 레벨(level) : 각 층의 번호를 의미한다. root node의 level은 0이다.

따라서 위 tree의 차수는 2, 높이는 3이며, root node는 A다. 노드 C는 level 1에 있으며 parent node로 A를, child node로 leaf node인 F와 G를 두고 있는 internal node라고 이야기할 수 있다.

스택과 큐는 '자료구조'하면 대부분이 떠올리는 선형 자료구조이자 ADT이다. 둘 다 값을 삽입하는 push와 값을 제거하며 반환하는 pop 명령을 가지며(다르게 부르기도 함), 자료구조가 비어있는지를 확인하는 empty, 원소가 얼마나 들어 있는지를 확인하는 size 명령이 구현되기도 한다. 스택과 큐는 한가지 큰 차이점이 있는데, 스택은 LIFO(Last In, First Out), 큐는 FIFO(First In, First Out) 구조다. 얼핏 생각해 보면, 스택의 특징인 '가장 최근에 들어간 원소부터 꺼내진다'는 굉장히 쓸데없어 보이지만, 꽤 많은 곳에서 사용된다.

• 함수의 call stack : 함수는 호출되었을 때 스택 프레임을 생성하여 call stack에 push되고, 함수가 종료되면 call stack에서 pop된다. 따라서, main -> a -> b -> c 순서로 함수를 호출하면, 순서대로 스택 프레임이 push되고, 가장 최근에 쌓인 스택 프레임부터 pop되어 c -> b -> a -> main 순서로 제어가 돌아온다.
• 브라우저의 히스토리 : 브라우저는 사용자가 방문한 페이지들을 차례로 스택에 push한다. '뒤로가기' 버튼을 누르면, 히스토리에서 주소를 pop하여 보여준다.

큐는 백엔드를 경험해본 사람이라면 익숙하겠지만, 작업 큐에서 자주 쓰인다. 그 외에도 정말 많은 곳에서 쓰인다. 예를 들자면, 운영체제의 스케줄링 알고리즘 중 FCFS(First-Come, First-Served) 스케줄링도 큐(정확히는 큐의 메커니즘인 FIFO)가 쓰인다.

설명만 무작정 하면 재미 없으니, Go로 스택과 큐를 구현하는 것으로 글을 마무리한다. Slice를 단지 써먹은 데에 지나지 않으므로, 진지하게 구현하려면 메모리를 직접 할당하는 방식(C의 mallic, realloc 등..)을 사용하자.

선형 자료구조인 배열(Array)와 연결 리스트(Linked List)는 데이터를 나열한다. 그러나 동일한 operation에 대해 내부적으로 수행되는 작업이 달라, 시간 복잡도 면에서 서로 반대의 장단점들이 존재한다.

Array(배열)

데이터를 논리적 순서에 따라 순차적으로 다룬다. 일반적으로 (메모리에서의)물리적 주소 또한 순차적이다. 또한 인덱스를 가지고 있어서, 무작위 접근(random access)이 매우 빠르다. 그러나 크기가 고정되어 있기 때문에 배열의 크기를 늘리는 연산이 필요한 경우가 있고, 데이터 삽입/삭제 시 그 다음 인덱스부터의 데이터를 모두 한 칸씩 뒤로 밀거나 앞으로 당겨오는 연산을 해야 하기 때문에 데이터 삽입과 삭제 시 느린 속도를 보인다.

Dynamic Array(동적 배열)

동적 배열은 크기가 고정되지 않은 배열을 의미하며, 일반 배열의 '크기가 고정되어 있다'는 문제를 제거한다. C++ STL의 vector, Python의 list 등이 동적 배열의 구현체다. 배열의 번외품처럼 보이지만, 꽤 많은 곳에서 유용하게 사용된다.

Linked List

데이터를 주소의 참조에 따라 순차적으로 다룬다. 배열에서 요소 하나가 값 + 인덱스로 이루어져 있다면, Linked List에서 요소 하나는 값 + next의 주소, 또는 값 + prev의 주소 + next의 주소로 이루어진다. 전자를 단순 연결리스트, 후자를 이중, 또는 양방향(doubly) 연결리스트라고 부른다. Linked List는 배열과 다르게 무작위 접근이 불가능하기 때문에, 특정 노드에 대한 임의 접근은 링크를 계속해서 따라가야 가능하기 때문에 배열보다 느리고, 반대로 데이터를 삽입/삭제할 때에는 앞/뒤 노드의 주소만 끼워넣을 노드의 주소로 바꿔주면 되기 때문에 배열보다 빠르다.

집합, 리스트, 스택, 큐, 트리처럼 자료구조 과목에서 흔히 볼 수 있는 것들을 추상적 자료형(Abstract Data Type)이라고 부른다. 이들은 공통점이 한가지 있는데, 자료 자체의 형태와 그 자료에 관계된 연산들이 수학적으로만 정의되어 있다는 것이다.

• Stack은 삽입한 순서대로 쌓이는 값들의 모임이고, 스택의 제일 위에 값을 삽입하는 push와 제일 위의 값을 하나 빼서 반환하는 pop 연산이 있다. 스택이 비었는지 알아보는 empty 연산, 스택에 쌓인 값이 몇 개인지 알아보는 size 연산이 정의될 수 있다.

형태와 연산이 수학적으로만 정의되어 있다. 구현의 세부사항은 전혀 정의되지 않았다. 따라서 스택이 내부적으로 array로 구현되는지, linked list로 구현되는지, size 연산을 수행할 때 원소의 개수를 일일히 세는지, 아니면 개수를 따로 저장해 두는지와 같은 세부 사항들은 다뤄지지 않는다. 따라서, ADT는 구현 부분을 나타내지 않고 순수한 기능이 무엇인지 나열한 것이다. Java에서 추상 메소드의 집합인 interface와 비슷한 맥락이다.

Binary search tree에 대해 이야기해 보았고, 삽입/삭제 시 생길 수 있는 unbalance 문제에 대해서도 이해할 수 있었다. AVL tree는 가장 초기에 나온 self-balanced binary search tree로, "An algorithm for the organization of information"이라는 논문에 의해 발표되었다. AVL tree의 'AVL'은 논문을 발표한 Adelson-Velskii와 Landis의 이름을 따 지어졌다.

AVL tree에서는 트리의 모든 internal node(leaf node가 아닌 노드)에 대하여, child node들의 높이 차이가 최대 1인 것을 높이 균형 성질이라 부른다. 임의의 binary search tree가 높이 균형 성질을 만족할 때 AVL tree라고 한다. 이진 탐색 트리가 높이 균형 성질을 만족하려면 삽입과 삭제 시 추가적인 동작이 하나 있어야 하고, AVL tree는 이에 대해 '회전'이라는 동작을 수행한다.

삽입

회전

삭제