알고리듬이란게 나름의 스토리가 있고 등장 자료구조가 있기 때문에 한번 이해가 되었다면 쉽게 잊혀지지 않는것이 정상이다. 따라서 잘 까먹는 알고리듬이 있다면, 그것은 내가 그 알고리듬(의 핵심)을 잘 모를 가능성이 높다.

머지소트는 잘 까먹는 알고리듬중에 하나이다.

내가 무슨 붕어도 아니고 잘 까먹는 이유를 고민해봤더니, 내가 익숙한 재귀함수 달라서이다는것을 깨달았다. 사실, 근본적으로 내가 재귀함수를 잘 모르는것이 머지소트를 잘 까먹는 이유였던 것이다.

기저사례

재귀함수를 자기를 호출하기전에 보통 기저사례(Base case)를 확인하다. 만일 어떤 조건이 기저사례에 도달하면 더이상 자신을 호출하지 않고 함수를 종료한다. 이런식으로 자신을 호출하여 쌓은 Call stack을 빠져나온다 (이 과정을 call stack unwinding 이라고 한다)

Augmenting recursion vs Tail recursion

기저사례를 통한 종료 및 콜스택이라는 형태는 어느정도 익숙했으나 내가 익숙하지 않은것이 바로 콜스택 끝부분에서의 형태 - Augmenting / Tail - 이다. 그렇기 때문에 단순히 합을 구하는 재귀함수조차도 낯설었다.

Augmenting recursion은 우리가 흔히 봐온 재귀함수이다. 즉, 대부분의 재귀함수는 call stack에 돌다갈 지점들을 쌓아둔후 끝을 지나 (base case에서 종료조건을 확인한후) unwinding시점에 call stack의 상태와 관련된 어떤 상태를 변경한다. 예를들면 머지소트의 경우에는 unwinding을 하며 split을 한 자료들을 merge 한다.

// start, end는 모두 inclusive
static void split_and_merge(std::vector<int>& partialOrdered, std::vector<int>& tmp, int start, int end){
    // split base condition
    if(start >= end){
        return;
    }

    // split until element remains just one
    int mid = start + (end-start)/2;

    // left side
    split_and_merge(partialOrdered, tmp, start, mid);

    // right side
    split_and_merge(partialOrdered, tmp, mid+1, end);

    // merge
    merge(partialOrdered, tmp, start, mid, mid+1, end);
}

left side, right side가 모두 call stack 에 도달한후 unwinding되면서 merge가 수행된다. (전체 소스는 github algostudy에서 확인 가능)

반면 tail recursion은 augmenting이 발생하지 않는다. - call stack loop만 돈다는지, 적층을 해야하는 값들을 parameter로 넘긴다든지 하는 형태로 적층을 일부러 피하는 경우도 많다.

int factorial(int n) {
    if (n == 0) return 1;
    return n * factorial(n - 1);
}

int factorial1(int n, int accumulator) {
    if (n == 0) return accumulator;
    return factorial1(n - 1, n * accumulator);
}

(출처 : http://c2.com/cgi/wiki?TailRecursion)

Tail recursion으로 하면 call stack을 쌓을 필요없이 loop로 최적화 하기 쉽기때문에 여러 함수형 언어에서는 tail recursion을 최적화의 한 수단으로 이용한다.

잘 이해하기와 조각맞추기

대부분의 학습에서 core라는 부르는 부분은 많은것들을 생략하기 마련이다. 어떤이는 이런 core만으로 잘 활용하기도 하지만 내 경우는 전체적인 조각들이 다 모였을때 활용을 잘하는 편인것 같다. 이 바보 같은 나는 머지소트도 몰라.. 라는 반성에서 글을 쓰기 시작했는데, 지금와서 보니 여러가지를 찾아보고 고민해서 “적층”이라는 지점까지 도달한것에 좀더 칭찬을 해주어야겠다. - 사실 이글을 처음 쓰고 마지막 마무리까지 거의 보름이 걸렸다.. -_-;;

모르는 조각들을 이어 붙이고, 모르는 상태를 계속해서 고민하면 문제해결의 영역이 더 넓으질것이다. (-_-;; 정말 수습 안되는 마무리. 어쨌거나 끗.)