개념 정리 - (5) 알고리즘 편
우리가 배운 개념이 어디서 어떻게 쓰이는지 알아보자
알고리즘은 어떠한 문제를 해결하기 위한 여러 동작들의 모임이다. 유한성을 가지며, 언젠가는 끝나야 하는 속성을 가지고 있다. 또한, 다음의 조건을 만족해야만 한다.
입력 : 외부에서 제공되는 자료가 0개 이상 존재해야 한다.
출력 : 적어도 1개 이상의 서로 다른 결과를 내어야 한다.(즉 모든 입력에 하나의 출력이 나오면 안 됨)
명확성 : 수행 과정은 명확하고 모호하지 않은 명령어로 구성되어야 한다.
유한성 : 알고리즘의 명령어들은 끝이 있는 계산을 수행한 후에 종료해야 한다.
효율성 : 모든 과정은 명백하게 실행 가능(검증 가능) 한 것이어야 한다.
출처 : http://www.webopedia.com/TERM/A/algorithm.html알고리즘을 이야기하면서 복잡도 이야기도 빼놓을 수 없다. 알고리즘의 정의는 수학에서 온 것인데, 컴퓨터로는 유한한 자원상에서 알고리즘을 실행해야 하기 때문에 공간 복잡도, 시간 복잡도가 중요하다. 아무리 빠른 알고리즘이더라도 그 알고리즘을 실행할 컴퓨터의 메모리보다 더 많은 공간을 요구하는 알고리즘이라면 실행할 수 없다. 예를 들어 깊이의 끝을 알 수 없는 검색을 깊이 우선으로 하게 되는 경우 무한히 노드를 검색해나가다가 메모리가 부족하여 실행을 종료하게 될 것이다.
알고리즘은 보통 분할 정복법(Divide & Conquer), 동적 계획법(Dynamic programming), 탐욕적인 방법(Greedy approach), 백트래킹(Backtracking) 설계 기법을 기반으로 개발된다. 너무 많은 알고리즘들이 있기 때문에 각 항목 별 유명한 알고리즘을 소개하면서 어떤 설계 방법인지 전달하고자 한다.
분할 정복법
풀려는 문제가 큰 문제일 경우 그 문제를 작게 나누기를 재귀적으로 반복하여 작은 문제들로 나누고, 그 문제를 푼 뒤 다시 합쳐나가는 방식의 접근 방식을 분할 정복법이라고 한다. 이렇듯 위에서부터 아래로 문제를 나누어가는 방식을 보고 하향식 접근(Top-down approach)라고도 말한다. 분할 정복법의 대표적 예인 이진 검색과 합병 정렬을 살펴보자.
이진 검색은 이미 정렬되어 있는 배열에 적용할 수 있다. 찾으려는 값과 현재 고려 중인 배열의 중앙에 있는 값을 비교하여 값을 찾기를 성공하거나, 왼쪽 배열에서 다시 찾거나, 오른쪽 배열에서 다시 찾는다. 비교 대상이 지수적으로 줄어들기 때문에 시간 복잡도가 O(logN)이 된다. 정렬되어 있지 않은 배열에서 값을 찾기 위해서는 O(N)의 시간 복잡도였던 것에 비해 비약적으로 빠르다. 정확히 같은 값을 찾는 것이 아니라 하한 값을 찾는 등의 변형도 가능하다. B-tree는 트리의 차수를 크게 높여 인덱스 파일에 대한 디스크 접근을 줄임으로써 검색 속도를 향상한다.
합병 정렬은 O(NlogN)의 시간 복잡도를 가진 정렬 알고리즘이다. 실제로는 캐시 미스에 의한 성능 저하 때문에 퀵 정렬이 많이 이용되나 합병 정렬은 정렬하고자 하는 데이터의 양이 메모리 크기를 초과하더라도 적용 가능하다는 이점이 있다. 정렬하고자 하는 배열을 재귀적으로 반 씩 쪼개나가고 최종적으로 단일 원소가 되었을 때 합병을 시작하는데, 합병을 할 때는 원하는 정렬 순서에 따라 작거나 큰 원소를 먼저 복사해나감으로써 각 합쳐진 배열이 정렬된 배열이 된다.
동적 계획법
동적 계획법도 분할 정복법과 비슷하게 하위 문제를 이용하여 상위 문제를 푸는 방식의 설계 방법이다. 분할 정복법과의 차이점으로는 나뉘어진 부분 문제가 서로 중첩되는 특징을 가진다는 점이다. 이런 문제에 대해서 동적 계획법은 이전에 계산해둔 것을 재활용함으로써 더 복잡한 문제를 빠르게 계산할 수 있게 된다. 동적 계획법을 기반으로 설계된 알고리즘으로 최장 공통 부분 수열(LCS : Longest Common Subsequence), 다익스트라의 최단 경로(Dijkstra's shorted path), 플로이드-워셜 알고리즘(Floyd-Warshall Algorithm) 등이 있다.
다익스트라의 최단 경로 알고리즘은 실제 네트워크 망에서 빠르게 패킷을 라우팅하기 위해 쓰이는 알고리즘 중 하나이다. 현재까지 검증된 노드들과 연결된 검증되지 않은 노드를 하나씩 선택해나가면서 최종 목적지까지의 최단 경로를 계산해나간다. 이전에 계산해둔 최단 경로에서 새로운 간선을 추가할 때는 그 간선의 가중치만을 더하면 또다시 최단 경로가 되기 때문에 최적 부분 구조를 가진 문제가 된다. 이 알고리즘은 O(|V|^2)의 시간 복잡도를 가졌지만 우선 순위 큐 등을 활용하여 다음 노드 선택을 더 빠르게 함으로써 O((|E| + |V|)log|V|)의 시간 복잡도로 계산 가능하기도 하다.
다익스트라의 최단 경로 알고리즘과 달리 플로이드-워셜 알고리즘은 전체 노드 간의 최단 경로를 모두 계산하는 알고리즘이다. 노드 하나씩을 더 고려해나가면서 최단 경로를 갱신해나가는 방식으로 구현되기 때문에 O(N^3)의 시간 복잡도를 가진다.
탐욕적인 방법
탐욕적인 방법은 매우 쉽다. 그때그때 최적의 선택만 하면 되는 알고리즘이다. 알고리즘 원칙 자체는 쉬우나 실제 최적해를 찾기 위한 방법으로 적용하기는 어렵다. 실제로 최적해를 계산할 수 있는지 증명해야 하기 때문이다. 그런데 정말 최적해를 계산 가능한 경우가 있다! 대표적으로 최소 신장 트리를 만드는 알고리즘인 프림의 알고리즘과 크러스칼의 알고리즘이 있다. (최소 신장 트리는 모든 노드가 연결되어 있는 상태라는 점에서 의의를 가지는 트리 구조이다.) 프림의 알고리즘은 cycle을 만들지 않는 간선을 하나씩 추가해나가는 방식이고, 크러스칼의 알고리즘은 Disjoint set 자료 구조를 이용하여 정점을 합해나가는 방식이다. 자세한 작동 원리는 해당 항목을 참고.
여기서부터 소개하고 싶은 다른 개념이 있다. 최적이 무엇을 의미하는가이다. 빠른 시간 안에(보통 다항 시간) 답을 찾을 수 있는 문제라면 그 답을 찾으면 된다. 하지만 현실적으로 실제 답을 찾기 어려운 문제도 많다. 답을 찾는 것에 계산 시간까지 포함한다면 좀 더 빠르게 계산되면서도 최적까지는 아니어도 최적에 가까운 답을 구하는 것이 의미가 있는 경우도 많다. 그런 점에서 빠르게 최적 근사 해를 구할 수 있는 알고리즘은 의미가 있는 것이다.
나는 통계적인 방법 또한 이런 개념에서 확장된 것이라 생각한다. 예를 들어 경사 하강법(Gradient descent)은 시작점이 어디인가에 따라 지역해(Local optimum)를 구하게 되기도 한다. 그렇기 때문에 여러 점에서 경사 하강법을 실행해보면서 지역해가 아니게 될 확률을 올리는 식의 접근을 한다. 실제 최적해가 무엇인지 알 수 없다. 그런 경우엔 나름대로 구해본 최적해일 가능성이 높은 해도 의미가 있는 것이다.
백트래킹
백트래킹은 모든 경우의 수를 다 시도해보는 방법이다. 문제를 상태 공간 트리로 가정하고 가능한 경우를 다 탐색해보는 것이다. 트리를 탐색하는 방식이기 때문에 깊이 우선 탐색(Depth First Search, DFS), 너비 우선 탐색(Breadth First Search, BFS), 최선 우선 탐색(Best First Search) 등의 여러 가지 탐색 방법을 사용할 수 있다. 회로(Loop)가 존재하는 미로 찾기와 같은 경우 중복 검사를 하지 않으면 깊이가 무한히 깊어질 수 있기 때문에 탐색 방법을 잘 선택하거나 중복 처리를 잘 해야 한다.
백트래킹은 모든 경우의 수를 다 시도해보는 것이기 때문에 느려지기 쉽다. 만약 문제가 비용을 잘 계산할 수 있는 경우 가지 치기를 하는 것이 계산을 줄이는 것이 큰 도움이 된다. 지금까지 100의 비용이 최소 비용이라는 것을 알아냈다면 앞으로 100보다 큰 비용이 들게 될 경우는 더 이상 고려하지 않는 식으로 계산을 줄이는 것이다. 비슷한 맥락에서 가능성이 높은 경우를 먼저 시도해보는 것도 경우의 수를 줄이는 데 큰 도움이 된다. 이를 위해 휴리스틱(Heuristic) 함수를 만들어 두는데, 휴리스틱 함수는 절대 과대평가(Overestimation)를 해서는 안 된다. 예를 들어, 목적지까지의 최단 경로를 찾을 때는 직선거리와 같은 것을 쓸 수 있다. 현실적으로 직선거리보다 목적지에 빨리 도달할 수 있는 방법이 존재하지 않기 때문에 과대평가를 하지 않는다는 조건을 만족한다.
다른 흥미로운 알고리즘들
위 설계 기법들에서 제시하는 기본적인 알고리즘들 외에 좀 더 다양한 알고리즘들을 소개한다.
- 최장 증가 수열(Longest Increasing Subsequence)
- 들로네 삼각분할(Delaunay triangulation)
- 강결합(Strongly connected component)
- Ford–Fulkerson algorithm : Maximum flow를 찾는 알고리즘
- Hungarian algorithm : Bipartite matching을 찾는 알고리즘
이상으로 알고리즘에 대한 정리를 마친다. 자료 구조에 이어 알고리즘은 추상적 소프트웨어 수준의 공부였다. 그러나 컴퓨터는 추상적인 개념을 실행할 수 없다. 결국 컴퓨터가 실행하는 것은 작성한 소스 코드가 컴파일된 목적 코드이다. 목적 코드가 어떻게 실행되는가에 대해 알아보기 위해 다음 편에서는 좀 더 깊이 들어가 컴퓨터 구조에 대해 알아본다.
