‘컴퓨터’는 어떤 문제를 해결하는데 있어 자주 사용된다. 단순 계산을 하기 위해 계산기 기능을 사용하기도 하지만, 프로그래밍을 통해 문제를 해결하기도 한다. 프로그래밍을 통해 해결할 수 있는 문제의 예를 들면 다음과 같다. ‘어떤 자연수 수열이 이루어졌을 때, 이 수열에 존재하는 부분 수열들 중 가장 길이가 긴 수열(최장 증가 부분 수열)의 길이를 구하시오.’ 예를 들어, 자연수 수열 ‘2 4 3 1 5’가 주어졌으면, 이 수열의 최장 증가 부분 수열은 ‘2 3 5’로 길이는 3이다. 이 때, 자연수 수열은 임의로 주어지기 때문에, 이런 문제를 해결하기 위해서는 ‘계획’이 필요하다. 이러한 ‘계획’을 알고리즘이라고 한다. 이 글에서는, 프로그래밍을 통해 문제를 해결할 때 자주 사용되는 알고리즘들에 대해 설명하겠다.
먼저, 분할 정복(Divide and Conquer) 방법이 있다. 분할 정복 방법은, 어떤 문제를 여러 개의 부분 문제로 나누어 해결하는 방법이다. ‘퀵 정렬’은 분할 정복을 이용하는 문제는 아니지만, 분할 정복과 비슷한 개념을 이용하는 문제이다. 퀵 정렬은 다음과 같은 과정에 의해 진행된다. 먼저, 기준이 되는 수(pivot)를 정한다. 그리고, 주어진 수열의 수들을 pivot값보다 작은 수들의 집합 A와, pivot값보다 큰 수들의 집합 B로 나눈다. 마지막으로, 집합 A와 집합 B에 대해 각각 정렬을 수행한다. 이 과정을 계속 반복하면, 결국 수열의 모든 수들이 정렬된다. 예를 들어, 자연수 수열 ‘3 4 2 1 5’이 주어졌을 때 퀵 정렬 과정을 설명해 보겠다. 먼저, 기준이 되는 수를 3으로 하면, 이 수열은 프로그램이 실행되면서 ‘2 1 3 4 5’가 된다. 즉, 3을 기준으로 3보다 작은 수들과 3보다 큰 수들이 나누어진 것이다. 이제, 수열 ‘2 1’에 대해 같은 방법으로 정렬을 수행하고, 수열 ‘4 5’에 대해 같은 방법으로 정렬을 수행하면, 정렬이 완료된다.
또한, 퇴각 검색(Backtracking) 방법이 있다. 퇴각 검색은 간단히 말해서, 가능한 모든 경우를 탐색해서 해를 찾는 방법이다. 퇴각 검색으로 해결할 수 있는 대표적인 문제로, N-Queen 문제가 있다. 이 문제는, N*N 체스판에 N개의 queen을 배치하는 방법들 중, queen들이 서로 잡아먹지 못하도록 queen들을 배치하는 방법의 수를 구하는 문제이다. 이 문제를 해결하려면, queen들이 배치될 수 있는, 가능한 모든 경우를 고려하면 된다. 조건을 만족하려면, 한 행에는 반드시 queen이 1개만 있어야 한다. 즉, 각 행에서 N개의 열 중 어떤 열에 queen을 배치시킬지 결정하면 queen들이 배치되는 방법 1가지가 결정되므로, (N^N)개의 배치들에 대해 조건이 만족되는지 확인하면 답을 구할 수 있다. 프로그램 실행 시간을 줄이기 위해서는 다음과 같이 프로그램을 개선할 수 있다. 첫 번째 행에 queen을 배치할 때에는, N개의 열에 모두 queen이 배치될 수 있으므로 N가지 방법이 있지만, 두 번째 행의 queen은, N개의 열 중 첫 번째 행의 queen이 배치된 열에는 배치될 수 없다. 즉, 두 번째 행에 queen이 배치될 수 있는 방법의 수는 (N-1)가지이다. 이렇게 탐색을 하면, N!개(N!은 1부터 N까지의 모든 수들을 곱한 것을 의미한다.)의 배치들에 대해 조건을 만족하는지 확인하면 답을 구할 수 있다.
지금까지 설명한 알고리즘 외에도, 동적 계획법(Dynamic Programming), 그리디(Greedy) 방법, 최단 경로를 구하는 다익스트라(Dijkstra) 알고리즘 등 많은 알고리즘들이 있다. 어떤 문제를 해결할 때 이용되는 알고리즘을 학습하기 전에, 문제를 해결할 수 있는 방법을 먼저 생각해 보고 알고리즘을 학습한다면, 알고리즘에 대한 이해도를 높일 수 있을 것이다.
HOME > 
