정점 찾기 문제와 그것을 해결하는 알고리즘들을 알아봅시다.
스케일이 큰 문제들을 풀 수 있는 어떤 방법들이 있을까요?
있다면 그 효과적인 방법들은 무엇일까요?
입력값이 커짐에 따라서 알고리즘들이 어떻게 일하는가를 알 수 있을까요?
생각해 봅시다.
어떤 입력들이 있다고 합시다.
정점찾기 문제
다음 위치에서 peak 를 찾으려면 어떻게 해야 할까요?
p1 p2 p3 ...
어떤 점
p1 p2 p3
에서
p2 ≥ p1, p2 ≥ p1 일 때, p2 = peak 입니다.
그러면 점에 숫자를 써서 각 위치를 다음과 같이 표시했다 칩니다.
그러면
p1 p2 p3 ... p8 p9
1 2 3 4 5 6 7 8 9
p9 = 9 ≥ p8 = 8 이므로
p9 = peak 입니다.
정점 찾기를 조금 더 일반화 해 봅시다.
그러면 다음의 경우에 peak 가 있다면 그것을 찾아 봅시다.
1 2 3 ...... n - 2 n - 1 n
p1 p2 p3 pn
알고리즘의 complexity 와 개수 n 개를 명확하게 표시하기 위해서
다음과 같이 표현해 봅시다.
1 2 3 ... n/2 -1 n/2 n/2 + 1 .... n - 2 n - 1 n
그런데 peak 가 가운데에 있다고 가정하면
peak 는 n/2 에 있습니다.
peak 가 오른쪽에 있다고 가정하면
peak 는 n 에 있습니다. 즉, n 개의 원소를 확인해야 합니다.
이런 경우에 complexity 는 O(n) 이라 합니다.
분할 정복(Divide-and-conquer)
분할 정복이라는 것은 바로 어떤 커다란 문제를 여러 개의 작은
하위 문제들로 분할하여 나눠서 푼 다음에 그것들을 다시 합쳐서
원래의 커다란 문제를 해결 하자는 개념의 방법, 알고리즘 입니다.
이 분할 정복 알고리즘을 간략하게 요약한다면
그것은 분할, 정복, 조합으로 설명할 수 있습니다.
즉, 문제를 더 나눌 수 없을 만큼 작게 같은 형태의
하위 문제들로 분할합니다.
그런 다음 가장 작은 하위 문제들을 정복, 즉 해결 합니다.
그리고 하위 문제들의 결과들을 다시 조합하는 것입니다.
즉, 분할 정복 알고리즘은 하위 문제들을 재귀적으로 풀며
각각의 하위 문제들은 원래 문제 보다는 그 크기가 작아집니다.
병합 정렬이나 퀵 정렬과 같은 정렬 알고리즘은 분할 정복의
대표적인 정렬 방법으로 재귀 호출을 그 기반으로 하고 있습니다.
그런데 이러한 재귀 호출은 함수 호출의 오버헤드가 발생하기 때문에
스택 오버풀로우나 실행이 느려진다는 문제점이 있습니다.