[ Algorithm ] 분할 정복
분할 정복(Divide-and-Conquer)
문제의 입력 사례를 두 개 이상의 작은 입력 사례로 분할, 분할한 입력 사례의 답을 바로 얻을 수 있으면, 원래 문제의 답은 얻은 답들을 통하여 구할 수 있고 분할한 입력 사례가 여전히 커서 바로 답을 구하지 못하면 그보다 더 작은 입력 사례로 다시 분할한다. 바로 답을 구할 수 있을 만큼 충분히 작아질 때까지 입력 사례를 계속 분할한다. 이는 하향식(top-down) 문제 풀이 방식으로, 상위 입력 사례의 해답은 하위의 작은 입력 사례(들)의 해답을 가지고 구한다. (ex) 재귀 함수가 작동하는 원리)
1. 이분 검색
- 분할 : 배열을 정 가운데 원소를 기준으로 반으로 분할(divide). x가 가운데 원소보다 작으면 왼쪽을 선택, 크면 오른쪽 배열 선택
- 정복 : 선택한 반쪽 배열을 정복, 선택한 반쪽 배열에 x가 있는지 재귀적으로 이분 검색
- 취합 : 선택한 반쪽 배열에서 얻은 답이 해답.
※ 이분 검색은 분할 정복 알고리즘 중에서 가장 간단한 부류에 속한다. 입력 사례를 분할하여 해답을 구하고, 결과를 취합할 필요 없기 때문
ex) 이분 검색 재귀
문제:원소 n개인 정렬된 배열 S에 검색 키 x가 있는가?
입력:양의 정수 n, 정렬된(비내림차순) 배열S(첨자는 1부터 n까지), 검색키 x
출력: location, S에서 x의 위치(만약 x가 s에 없으면 0)
n,S,x는 location 함수의 파라미터일 필요 X(값이 변하지 않는 상수이기 때문, 변수만 파라미터) ->저장 공간 절약 (const 사용 가능)
c++로 구현 시 상수 값을 모두 파라미터로 전달하거나 전역변수로 정의 가능
꼬리 재귀(tail-recursion): 호출 이후 더 이상 연산이 없는 재귀 호출
재귀 호출 종료 후 해야 할 작업을 스택에 저장해 둘 필요가 없어 저장 공간 절약
꼬리 재귀를 반복형으로 변환 시, 스택을 쓸 필요가 없어서 실행 속도 빠름
2. 합병 정렬(Mergesort)
1.분할: 배열을 반으로 분할. 분할한 배열의 원소는 각각 n/2개
2.정복: 분할한 배열을 각각 따로 정렬 (배열 원소가 2개 이상이면 합병 정렬을 재귀 호출 정렬)
3.취합: 정렬한 두 배열을 합병하여 정렬
※ 쌍방 합병(two-way merging): 정렬된 배열 두 개를 정렬 상태를 유지하면서 합치는 것(합병을 이용하여 임의의 배열을 정렬)
※ 제자리 정렬(in-pace sort):입력을 저장하는데 필요한 장소 이외에 추가적인 저장장소를 사용하지 않는 알고리즘
ex) 합병 정렬 구현
3. 분할 정복(Divide-and-conquer) 설계 전략
4. 빠른 정렬(분할 교환 정렬)
배열을 둘로 분할하고, 분할한 배열을 각각 재귀 호출로(recursively) 정렬하여 합병한다는 것에서 합병 정렬과 비슷하지만 배열을 분할 하는 방식이 다르다.
기준 원소(pivot)를 선정하여 기준 원소보다 작은 원소는 모두 왼쪽 배열로, 크거나 같은 원소는 모두 오른쪽 배열로 가도록 분할한다. 중요점은 기준 원소보다 작은 원소는 모두 왼쪽에, 큰 원소는 모두 오른쪽에 두며 분할한 두 배열을 각각 재귀 호출하여 정렬하며 하나 뿐인 배열로 분할 될 때까지 재귀 호출을 계속한다.
5. 쉬트라쎈 행렬 곱셈 알고리즘
$T(n) = n^3$ 일 때, 시간 복잡도는 $Θ(n^3 )$인데, 이보다 좋은 알고리즘.
직관적인 방법으로 2 X 2 행렬을 곱하려면 곱셈 8번과 덧셈/뺄셈 4번 필요 -> 쉬트라센 알고리즘 적용 시 곱셈 7번과 덧셈/뺄셈 18번
6. 큰 정수 계산법
정수를 표현하는 저장 공간의 용량을 초과하는 정수 연산 시, 유효숫자를 모두 보존해야 할 경우 -> 부동 소수점 표현 연산으로도 불가능 (대안은 소프트웨어로 정수를 표현 후 처리) -> 분할 정복으로 이를 성사 가능
1) 큰 정수 표현
덧셈과 기타 1차 시간 연산
큰 정수를 표현하는 직관적인 방법은 숫자(digit)배열을 사용하는 것으로, 배열 S로 표현.
양수와 음수를 모두 표현하기 위해 부호(sign)을 저장하는 배열 슬롯 하나 추가 준비.
0으로 양수를 표현, 1로 음수를 표현 가능
데이터 타입 large integer는 큰 정수를 표현하기에 충분히 큰 배열이라 가정
N을 큰 정수의 숫자 개수라 하면, 덧셈과 뺄셈을 하는 1차 시간 알고리즘을 작성하는 것은 어려운 일 X
단위 연산은 십진수(decimal digit) 조작 연산으로 정함.
여기서 u는 큰 정수, m은 음이 아닌 정수를 각각 나타내고, divide는 정수 나눗셈의 몫을 계산, rem은 정수 나눗셈의 나머지를 계산
1) 2 큰 정수 곱셈
분할 정복을 사용하여 n개의 숫자로 된 수를 n/2개의 숫자로 된 두 개의 정수로 분할.
숫자의 개수가 차이가 많이 나는 경우에도 같은 방법을 적용할 수 있으며 $m = n/2$를 사용하여 두 수를 각각 분할, 여기서 n은 둘 중에 큰 정수의 숫자의 개수이며, 둘 중 하나가 0이 되거나 정해 놓은 임계점에 도달할 때까지 계속 분할.
7. 임계값의 결정
재귀(recursion)는 계산 시간 면에서 보면 많은 양의 추가 비용이 듦. -> 사례를 더 이상 분할하는 것보다 다른 대체 알고리즘을 호출하는 것이 최소한 더 빠르게 되는 n의 값을 결정하는 방법
이상적으로 n의 최적 임계점이 되는 값(optimal threshold value)을 찾는 것으로, 이 값보다 더 작은 입력 사례에 대해서는 계속 분할하는 것보다 다른 알고리즘을 호출하여 사용하는 편이 최소한 빠르고, 더 큰 사례에 대해서는 계속 분할하는 편이 더 빠르게 되는 사례 크기가 임계값.
분할 정복 알고리즘을 수정하여 일단 n이 임계값에 도달하게 되면 분해를 중지하고 대체 알고리즘을 호출
임계값을 정하기 위하여 알고리즘을 구현하는 컴퓨터의 사양(실행 속도)을 반드시 고려 사항에 넣어야 한다.
8. 분할 정복을 사용할 수 없는 경우
크기가 n인 사례가 거의 n에 가까운 크기의 두 개 이상의 사례로 분할
크기가 n인 사례가 n/c 크기의 거의 n개 사례로 분할
첫 번째와 같이 분할하면 지수 시간 알고리즘이 나오고, 두 번째는 $n^(Θ (lgn))$알고리즘이 나온다. 이중 어떤 것도 n값이 크면 받아들일 수 없다.
※ N이 단순히 5나 작은 숫자라면 상관 없지만 2^1000의 경우, 지수 시간 알고리즘에서는 힘들다.
출처: 알고리즘 기초