알고리즘을 어떻게 공부해야할지 몰라서 구글링을 하던중 알고리즘 공부한답시고 처음 접했던게 병합정렬이었다. 그래서 그런지 제일 친숙한 정렬방법이기도 하다. 사실 병합정렬은 알고리즘보다는 정렬이라는 분류가 더 어울릴지 모르겠다. 하지만 병합정렬에는 분할정복이라는 중요한 알고리즘이 녹아 들어가 있기때문에 나의 알고리즘 포스팅을 분할정복으로 시작할까한다.
분할정복
분할정복(Divide and Conquer)의 개념은 간단하다.
문제를 작은문제로 분할하여 해결하고 큰 문제를 해결하는 방법
그러나 이 과정을 특정 문제에 적용시켜서 해결하는 방법은 익숙하지않으면 어렵다고 생각한다. 위키백과에서는 분할정복에 대한 의사코드를 이렇게 표현하고있다.
function F(x):
if F(x)의 문제가 간단 then:
return F(x)을 직접 계산한 값
else:
x 를 y1, y2로 분할
F(y1)과 F(y2)를 호출
return F(y1), F(y2)로부터 F(x)를 구한 값이 슈도코드만으로도 분할정복을 설명할 수 있고 실제로 위키백과에서도 이 코드를 제시해주는 것외에 별다른 설명이 없다. 그리고 보다시피 재귀함수를 이용하고있는데, 따라서 크기가 커지면 메모리가 제한적이라는 단점이 있다.
그러나 그 크기가 크지않다면 분할정복은 더할나위없는 효율을 가진다. 이는 직관적으로 시간복잡도를 통해 알수있는데, 시간복잡도는 O(NlogN)을 가지고있다. 여기까지 글을 읽은 사람들 중 알고리즘 경험이 없는 사람들은 이게 무슨 말인가 싶을거다. 내가 그랬었으니..
이 슈도 코드와 시간복잡도 그리고 분할정복에 대해서 설명할 적절한 예제가 바로 병합정렬이다. 병합정렬을 구현해보면서 분할정복을 이해해보자.
병합정렬
먼저 병합정렬의 뜻을 이해해보자. 병합정렬(Merge Sort)은 어떤 리스트를 정렬하기위해서 나눌 수없을때까지 나눈후, 나눈 요소들끼리 정렬을하며 병합(Merge)하는 정렬 방법이다.
즉, 작은요소로 나눠서 해결하는 모습이 분할정복 알고리즘과 동일하다. 이때 나눈다는 개념은 반으로 나누는 것이다.
그렇다면 먼저 임의의 리스트를 뽑아보자.
List<Integer> list = new ArrayList<>();
Random rand = new Random();
for(int i = 0; i < 7; ++i) {
list.add(rand.nextInt(45));
}두번째로는 리스트를 최소한까지 나누어보자.
그런데 여기서 나누는 이유를 앞서 이야기하지 않았는데, 이렇게 구현해보며 이해하는것이 나는 더욱 다가왔던것같아서 그랬다. 우리는 고등학생때 수학을 배웠다. 그렇다면 1/2씩 n번 나눈다면 (1/2)^n으로 수렴하는것을 알 수있다. 즉 반대로 n번을 계산하기위해서는 약 logn만큼의 시간이 필요하다. 그런데 BIG-O표기법에서 밑은 중요하지않으므로 시간복잡도가 O(logn)이 된다.
private static List<Integer> sort(List<Integer> data) {
if(data.size() <= 1) return data;
int mid = data.size()/2;
final List<Integer> left = sort(data.subList(0, mid));
final List<Integer> right = sort(data.subList(mid, data.size()));
return merge(left,right);
}위에서 슈도코드와 비교해보자. 직접 구할수있을때는 직접 구한값을 return라고 기저조건이 걸려있다. 병합정렬에서는 리스트의 사이즈가 1이면 더이상 쪼갤 수없기때문에 기저조건으로 두었다.
또한 left,right로 리스트를 반으로 계속 쪼개며 재귀호출을 하고있다. 재귀호출은 하나의 스택이기 때문에 Last-In-First-Out이다. 따라서 기저조건인 사이즈가 1일때 return된 left값과 right값이 처음으로 merge 함수를 호출하게된다.
merge 함수는 나눈 리스트를 합치는 역할을 하고있다.
private static List<Integer> merge(List<Integer> left, List<Integer> right) {
List<Integer> ret = new ArrayList<>();
int leftIdx = 0;
int rightIdx = 0;
while(leftIdx != left.size() && rightIdx != right.size()) {
if(left.get(leftIdx) <= right.get(rightIdx)) {
ret.add(left.get(leftIdx++));
}
else {
ret.add(right.get(rightIdx++));
}
}
ret.addAll(left.subList(leftIdx, left.size()));
ret.addAll(right.subList(rightIdx, right.size()));
return ret;
}파라미터로 받은 left,right 리스트들을 서로 비교해가며 return할 리스트 ret에 정렬시키고있다. 이 때 최대 left.size() + right.size()만큼 반복을 돌고있기때문에 시간복잡도 O(n)가 소요된다. 따라서 sort 함수 1번에 merge 함수 1번 호출이때문에 총 시간복잡도는 O(nlogn)이 된다.
이렇게 병합정렬을 통해서 분할정복을 알아보았다. 하지만 병합정렬이 분할정복 하나의 방법이 될순있지만 "분할정복은 병합정렬이다"라고 단정지을 수 없다. 그렇기 때문에 작은 문제로 분할하여 해결하는 포인트를 집는 것이 중요하다. 가령 문제를 작게 나눠서 문제를 해결하기위해서 또 다른 알고리즘을 적용 할 수도있다.
그래서 분할정복으로 유명한 이분탐색에 대해서도 정리해보겠다.
이분탐색
이분탐색(Binary Search)도 마찬가지로 선형의 리스트를 반으로 나눠가며 문제를 해결하는 방법이다. 다만 같은 분할정복의 성질을 이용하면서도 앞서 소개한 병합정렬과는 다르게 재귀호출을 이용하지 않는다. 또한 이번에는 문제를 해결하는 주제가 정렬이 아니라, 특정 값을 찾는 느낌이 강하다.
예를들어 선형의 정렬된 리스트가 있는데, 아래 리스트에서 47이라는 값을 찾아보도록하겠다.
for(int i = 1; i <= 50; ++i) {
list.add(i);
}일반적으로 선형으로 탐색할때는 시간복잡도 O(n)을 통해 전체리스트를 순환한다. 따라서 47번째 값을 찾기위해서는 47번을 순환하게된다.
int find = 47;
for(int i = 1; i <= 50; ++i) {
if(list.get(i) == find) {
// find
}
}그러나 이분탐색을 적용시킬경우 아래와같이 반을 쪼개며 계속 탐색할 수 있다. 따라서 시간복잡도는 앞서 말한바와같이 1/2씩 n번 쪼개기때문에 O(logn)이 된다.
int i = 1;
int begin = 0;
int end = list.size();
while(begin <= end) {
System.out.println(i++ + "번째 순회");
int mid = (begin + end) / 2;
if(list.get(mid) == find) {
System.out.println("찾음");
break;
}
else if(list.get(mid) < find) {
begin = mid + 1;
}
else if(list.get(mid) > find) {
end = mid - 1;
}
} 조금 직관적으로 이해하자면, 우리가 어렸을때 업다운 게임을 해봤을것이다. 문제를 내는 사람이 생각한 특정 숫자를 맞추기위해서 처음에는 아무 숫자나 때려맞추고 그 이후에는 최솟값과 최댓값의 반이되는 값을 얘기하며 문제를 맞춰나갔을것이다. 그것과 완전히 동일하다.
결과적으로 47값을 찾기위해서 이분탐색을 이용하면 단 6번만에 찾을 수 있게된다.
정리
분할정복의 대표적인 예 두가지를 정리해봤다. 하지만 이 예제를 아는 것보다 작은문제를 해결해서 큰 문제를 해결한다는 개념이 중요하다는것을 잊지말자.
