Merge Sort

Divide & Conqure Algorithm 패턴을 살펴보고 있다.

다른 알고리즘 패턴 (greedy, dynamic, backtracking, branch & bound) 보다도

패턴의 감을 잡기가 어려웠다.

더 작은 것으로 나누고 작게 나눠진 것을 각개 격파해서 답을 구한다는 것인데,

대표적인 예가, Merge Sort, Binary Search, Quick Sort 이다.

다른 알고리즘 패턴은 기반에 흐르는 원리가 비교적 명쾌해서

이 기법을 활용하면 문제 해결에 도움이 되겠구나라는 감이 잡혔는데,

Divide & Conqure는 책에 나온 예 말고, 진짜 실제 프로그래밍을 하며

적용할만한 원리를 체득하기가 어려웠다.

--------------------------------------------------------------------------------------------

backtracking은 그래프 탐색, 트리 탐색과 연관되어

정답을 트리로 구성해버려서 그 트리를 탐색해버리면 많은 컴퓨터 관련 문제들을

해결할 수 있다는 중요한 원리를 얻을 수 있었다.

--------------------------------------------------------------------------------------------

Merge Sort의 원리만 읽은 다음에 그것을 어떻게 코드로 구현할까를 생각해내는데

2 시간이 걸린 거 같다.

Recursion함수를 사용하는데도 꽤 익숙해진 상태에서도 말이다.

어떻게 요소가 하나가 될 때까지 간 다음에 그것들을 다시 합칠까?

샤워를 하면서 고민하다가 겨우 생각해 낸게,

List<Integer> divide(List<Integer> array) {

    if (array.size() == 1)  return array;

    List<Integer> smaller = array.subList(0, array.size()/2);
    List<Integer> bigger = array.subList(array.size()/2, array.size());

    return merge(divide(smaller), divide(bigger));
}

merge함수는 인자로 주어진 두 array를 순서대로 비교하면서
정렬된 array를 반환하면 된다.

굵게 표시한 재귀함수를 돌리면서 다른 함수를 쓰는 구조를 생각해내는게 어려웠다.

어려웠던 것은 recursion 내에서 다른 함수를 사용하는 형태를 처음  접했던 것이다.

지금까지는

public int fibo(int n) {
    if (n == 1) return 1;
    if (n == 2) return 2;
    return fibo(n-1) + fibo(n-2);
}

와 같은 종류의 recursion만을 생각해 왔다.

recursion은 아무리 생각해도 꼬리에 꼬리를 물고 헷갈리는 거 같다.