Jacob's Coding Playground

[문제출처 : Codechef] 세 명의 투표자가 각각 뽑은 숫자들의 리스트를 가지고 있습니다. 집계자는 세명 중에 두명 이상이 선택하는 숫자들을 뽑아내고 싶습니다. 어떻게 하면 될까요?

예를들면,
[23, 30, 42, 57, 90]
[21, 23, 35, 57, 90, 92]
[21, 23, 30, 57, 90]
의 리스트가 있을 때에, 집계자는 결국

[21, 23, 30, 57, 90]
을 뽑아내게 됩니다.

어떤 network에 중심이 되는 사람은 어떤 사람일까요? 이런 질문에 대답하기 위해서 다양한 Centrality라는 개념이 사용됩니다. 그 중에서 가장 처음으로 가장 간단한 degree centrality라는 개념을 알아보겠습니다.



그림으로 쉽게 설명이 되겠지만, 가장 많은 connection을 가지고 있을수록 더 중요한 사람일 것 같다는 추리가 기본적으로 할 수 있는 추리겠죠? 따라서 degree centrality란 가장 많은 connection을 가지고 있는 사람을 가장 중요한 사람이라고 생각하는 개념입니다.

이번에 살펴볼 예제는 graph traverse의 가장 일반적인 스킬인 snowball sampling에 대해서 알아보겠습니다. 해석 그대로 눈덩이를 불리듯이 덩치를 키워나간다는 이 방식은, 중심 노드를 중심으로 계속해서 친구들을 불러들이면서 maximum depth까지 recursive하게 탐색해 나가는 방식입니다.

이번에 살펴볼 알고리즘은 아주 아주 많이 사용되고 또 중요한 Dijkstra 알고리즘에 대해서 알아보겠습니다. 특히나 graph theory에서는 안쓰이는 곳이 없을 정도로 많이 사용되니 반드시 잘 숙지하시면 좋을 것 같네요 :)

Edsger W. Dijkstra라는 computer scientist에 의해 발견된 이 알고리즘은 기본적으로 graph내의 shortest path를 넘어서 weighted graph에서의 minimum cost(weight) path를 찾는 아주 좋은 알고리즘입니다.

원래는 탐색하는 순서에 대한 접근이 달라서 $O(|E|+|V|^2)$의 complexity를 가졌지만, priority queue를 접목시키면서 $O(|E|+|V|\log|V|)$의 complexity로 발전했습니다.(여기서 $|E|$는 Edges의 수를 의미하고, $|V|$는 Vertices의 수를 의미합니다.)

특히나 이 알고리즘은 Artificial Intelligence(인공지능)분야나 Dynamic Programming분야에서 UNIFORM COST SEARCH알고리즘으로 활용되어 아주 무시무시한 활약을 하죠 :) 가장 심플한 예로 아래의 미로찾기를 들 수 있습니다.

이번에 살펴볼 자료구조는 Priority Queue(우선순위 큐)로써, Dijkstra 알고리즘, Huffman 코딩, Prim 알고리즘 등 다양한 application에 적용됩니다. 작동 원리는 굉장히 심플합니다. PQ(Priority Queue)의 각 원소들은 priority값을 가지고 있습니다. 이 값은 낮을수록 급하게 처리되어야 한다는 의미이므로, 보통 queue에서는 들어온 순서대로 원소들을 저장하고 있지만, PQ에서는 낮은 priority의 원소가 먼저 나오도록 정렬되어 있다고 보시면 됩니다.