• 두 수를 입력받아 거듭제곱을 구하여라

Math.pow 사용

• 컴퓨터가 계산할 수 있는 범위를 넘지 않기 위해 94,906,249로 나눈 값을 리턴해야한다.

function power(base, exponent) {
	return Math.pow(base, exponent) % 94906249;
}

for문 사용

function power(base, exponent) {
	
	if(exponent = 0) {
		return 1;
	}

	let pow = 1;

	for(let i=1; i<=exponent; i++) {
		pow = pow * base;
	}

	return pow;
}

분할정복을 이용한 풀이

• 분할정복을 이용하면 시간복잡도는 O(logN)이된다.

function power(base, exponent) {
	// 지수가 0이면 1이다.
  if (exponent === 0) {
    return 1;
  }

	// exponent를 반으로 나눠준다. 홀수의 경우를 대비해서 Math.floor를 사용한다.
	let halfExponent = Math.floor(exponent / 2);

	// 반으로 된 exponent를 재귀적으로 돌려준다. 
	// 2^10 => 2^5 * 2^5가 되는거처럼 재귀적으로 계속 돌려주면 같은 결과값을 뽑아내게 된다.
	let recursive = power(base, halfExponent);

	let result = (recursive * recursive) % 94906249;

	// 지수가 홀수의 경우 base를 한번 더 곱해준다.
	// ex) 2^11 = 2^5 * 2^5 * 2
	if(exponent % 2 !== 0) {
		result = (result * base) % 94906249;
	}
	// 최종 result를 리턴한다.
	return result;
}