분할 정복 알고리즘
의미
엄청나게 크고 방대한 문제를 조금씩 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하는 방법
원리
- 분할: 문제를 더이상 분할할 수 없을 때까지 동일한 유형의 여러 하위 문제로 나눈다.
- 정복: 가장 작은 단위의 하위 문제를 해결하여 정복한다.
- 조합: 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다.
코드에 적용하기
function F(x):
if F(x)가 간단 then:
return F(x)를 계산한 값
else:
x 를 x1, x2로 분할
F(x1)과 F(x2)를 호출
return F(x1), F(x2)로 F(x)를 구한 값거듭제곱 구하기
문제
두 수를 입력받아 거듭제곱을 리턴해야 합니다.
입력
인자 1: base
number 타입의 자연수 (base >= 2)
인자 2: exponent
number 타입의 정수 (exponent >= 0)
출력
number 타입을 리턴해야 합니다.
실제 계산 결과를 94,906,249로 나눈 나머지를 리턴해야 합니다.
주의사항
Math.pow, 거듭제곱 연산자 사용은 금지됩니다.
시간복잡도 O(logN)을 만족해야 합니다.
나머지를 구하는 이유는 계산 결과가 컴퓨터로 나타낼 수 있는 수의 범위를 넘을 수 있기 때문입니다. 하지만 모든 연산이 끝난 뒤에 그 결과를 94,906,249로 나누려고 해서는 안 됩니다. 연산 중간에도 이 범위를 넘을 수 있기 때문에, 연산을 할 때마다 나머지를 구하고 그 결과에 연산을 이어가시기 바랍니다.
입출력 예시
let output = power(3, 40);
console.log(output); // --> 19334827첫번째 시도
재귀함수를 사용해서 문제를 풀어봤다.
function power(base, exponent) {
// todo: 여기에 코드를 작성합니다.
if(exponent === 0) return 1;
return base * power(base, exponent - 1) % 94906249
}이슈 발생
코드는 정상적으로 작동하나, 효율적인 알고리즘을 구현해야한다는 마지막 테스트만 통과하지 못했다.
원인
해당 방법을 사용하면 exponent만큼 코드를 반복 실행하므로 시간 복잡도가 O(n)이 된다. 따라서 시간복잡도 O(logN)을 만족해야한다는 조건을 충족하지 못한다.
두번째 시도
지수가 홀수일 때와 짝수일 때로 나눠서 재귀함수 호출하기
예를 들어, 2^16을 계산한다고 할 때 첫번째 시도했던 방법은 2를 16번 곱하는 방법이고, 지금 시도하는 방법은 아래와 같이 문제를 분할해서 해결할 수 있다.
(1) 2^16은 2^8 * 2^8
(2) 2^8은 2^4 * 2^4
(3) 2^4 는 2^2 * 2^2
(4) 2^2는 2 * 2코드 작성하기
지수가 홀수일 때와 짝수일 때로 나눠서 재귀 함수를 호출하되, 각각의 연산마다 94906249로 나눠준다.
function power(base, exponent) {
// todo: 여기에 코드를 작성합니다.
if(exponent === 0) return 1
//지수가 홀수일 때
if(exponent % 2 === 1) {
const odd = power(base, (exponent - 1) / 2) % 94906249;
return (((odd * odd) %94906249) * base) % 94906249
}
//지수가 짝수일 때
if(exponent % 2 === 0) {
const even = power(base, exponent / 2) % 94906249;
return (even * even) % 94906249
}
}결과
모든 테스트를 통과했다.
레퍼런스
- 지수를 무조건 지수를 2로 나누는 방법을 사용했다.
- 지수가 짝수일 때는 2로 나눠떨어지므로 문제가 되지 않지만, 지수가 홀수일 때는 half가 정수로 나눠떨어지지 않는다.
- 이를 대비하고자 pareInt를 사용했다. 즉, 지수가 홀수일 때는 연산 결과 마지막에는 half가 1이 된다.
- 결국은 지수를 짝수/홀수로 나눠서 계산하는 두번째 방법과 비슷한 방법이다.
function power(base, exponent) {
if (exponent === 0) return 1;
const half = parseInt(exponent / 2);
const temp = power(base, half);
const result = (temp * temp) % 94906249;
//지수가 홀수일 때
if (exponent % 2 === 1) return (base * result) % 94906249;
//지수가 짝수일 때
else return result;
}