power 문제 뜯어보기

🔍 문제보기

 

문제:

두 수를 입력받아 거듭제곱을 리턴해야 합니다.

 

 

입력:

인자1 : base	인자2 : exponent
number 타입의 자연수 (base >= 2)	number 타입의 정수 (exponent >= 0)

 

출력:

• number 타입을 리턴해야 합니다.
• 실제 계산 결과를 94,906,249로 나눈 나머지를 리턴해야 합니다.

 

주의사항:

• Math.pow, 거듭제곱 연산자 사용은 금지됩니다.
• 시간복잡도 O(logN)을 만족해야 합니다.
• 나머지를 구하는 이유는 계산 결과가 컴퓨터로 나타낼 수 있는 수의 범위를 넘을 수 있기 때문입니다. 하지만 모든 연산이 끝난 뒤에 그 결과를 94,906,249로 나누려고 해서는 안 됩니다. 연산 중간에도 이 범위를 넘을 수 있기 때문에, 연산을 할 때마다 나머지를 구하고 그 결과에 연산을 이어가시기 바랍니다.

 

입출력 예시:

let output = power(3, 40);
console.log(output); // --> 19334827

 

 

 

📝 이 문제는... 

분명 거듭제곱을 구하는 문제이다. 그런데! 출력값이 웬 나머지지?? 싶을 수 있다. 

그리고 94960249는 도대체 또 뭐야... 싶은 생각이 든다.

근데 문제 지문 하나하나 의미가 숨어있는 문제 였다.

그걸 알고나면 쉽게 넘어갈 수 있다.

 

 

---

1️⃣ 첫번째 풀이:  시간복잡도 fail

 

function power(base, exponent) {  

  const divisor = 94906249 
  
  const aux = (accBase,currentExponent) => {
    //edge case
  	if(accBase % divisor === NaN) return NaN
  
  	// base case
  	if(currentExponent === 1) return accBase

  	//recursive case
  	return aux(accBase*base, currentExponent-1)  
  }
  
  return aux(base,exponent) % divisor
}

 

이 풀이법은 가장 먼저 생각한 답이었는데,

답은 다 나오지만, 시간복잡도에서 패스되지 못하는 코드이다.

 

재귀를 활용해서 클로저 안에서 함수를 돌린다음, 제곱근을 다 구한다면 마지막에 94960249로 나눠주는 코드이다.

 

이럴 경우, power(2,8)이 들어온다면 재귀를 돌면서

((((((2*2)*2)*2)*2)*2)*2)*2 그니까, 총 7번의 연산을 해야 답이 나온다. 

power함수에 두번째 인자에 들어오는 숫자 -1만큼 곧이곧대로 계산해줘야하는 것이다.

좀 더 좋은 방법이 있을텐데!

이를 최적화시켜야 모든 테스트를 통과 할 수 있다.

 

---

 

💡 잠깐! 아이디어 생각해보기

 

 

☝🏻 하나,  분할정복 이해하기

 

'분할정복' 수학 공식같아서 말이 어렵지, 아래 예시를 보면 쉽다.

 

5⁵ 은 5² * 5² * 5 으로 나누어 계산할 수 있다.

 

이렇게 나누어서 5²를 변수로 할당하면 아래와 같이 두단계의 계산으로 끝난다.

 

temp = Math.pow(5,2)  // 5²
temp * temp * 5 === Math.pow(5,5)  // 5⁵

 

이 아이디어를 이용해 문제를 풀면, 시간복잡도를 훅! 줄일 수 있다. 

이런 방법이 분할정복이다.

 

 

✌🏻 둘,  94960249 이해하기

 

이 문제를 푸는 내내 이런 의문들이 끊임없이 들었다.

 

 이건 제곱근을 구하는 문제인데,
도대체 왜 94960249이란 근본없는 숫자로 나눠서 나머지를 리턴하라 그러지??
그리고 주의사항에, 
연산을 할 때마다 나머지를 구하고 그 결과에 연산을 이어가시기 바랍니다???
이건 또 뭔소리지?

 

 

이 부분을 이해하느라고 하루를 거의 통으로 날렸다. 

나와 같은 어려움을 겪고 있을 누군가를 위해 최대한 잘 정리해 보겠다!!

 

일단, 컴퓨터가 안정적으로 계산할 수 있는 최대의 숫자는 2⁵³ 이다.

그리고 놀랍게도 근본 없는 (줄 알았던) 숫자 94906249는 2⁵³의 제곱근이다. 

 

 

94906249 * 94906249 = 2⁵³ (9007199254740992)

 

 

이건 진짜 우연히 이거저거 눌러보다 알게된 사실이었다.

우리가 분할정복으로 접근하여 숫자를 제곱근으로 나누어서 계산할때,

 

 

 

 

그니까, 이미지의 C**(n-1)/2 나 C**2가 94960249이하여야지 최종 결과값이 2⁵³ 안짝으로 들어올 수 있는 것이다.

때문에 제곱했을 때의 숫자가 94960249가 넘지 않도록 하기위해서 이 숫자로 나머지를 구한다.

이 사실을 잘 기억해두고, 마지막 세번째 사항을 이해해보자!

 

 

🤟🏻 셋, 나머지의 성질 이해하기

 

나머지 연산자를 사용한 아래의 사례를 잘 보면

나누어지는 수(1~4)가 나누는 수(5)보다 작다면 그 숫자 그대로 나온다.

1 % 5 = 1
2 % 5 = 2
3 % 5 = 3
4 % 5 = 4
5 % 5 = 0
6 % 5 = 1
...

 

이건 큰 숫자에서도 마찬가지 일것이다.

 

1 % 94960249 = 1
2 % 94960249 = 2
...
5000 % 94960249 = 5000
...
94960248 % 94960249 = 94960248
94960249 % 94960249 = 0
94960250 % 94960249 = 1

 

그러니까 , 94960249 이하까지는 나누어지는 수가 그대로 나온다.

다시말해, 안정적인 숫자범위를 다루기 위해서,

구하고자하는 수가 94960249 보다 커지면, 나머지로 숫자가 작아지도록 장치를 설치해 놓는것이다.

 

따라서, 작은 숫자에선 저 나머지 연산자가 별다른 결과값의 차이를 불러오지 못하고 그대로 제곱근이 나올 것이지만,

큰 숫자가 나오면 값이 달라질 것이라는 뜻이다.

 

Math.pow(5,1) % 94906249 === Math.pow(5,1) //true
Math.pow(5,2) % 94906249 === Math.pow(5,2) //true
Math.pow(5,3) % 94906249 === Math.pow(5,3) //true
Math.pow(5,4) % 94906249 === Math.pow(5,4) //true
// ...
Math.pow(5,12) % 94906249 === Math.pow(5,12) //false

 

 

 

위 세가지 사항들을 미루어 보아 아래와 같은 결론이 나온다.

 

나머지 연산자는 사실상 작은 숫자에선 효력을 발휘하지 못하나,
큰 숫자에서도 안정적으로 계산할 수 있도록 대비책으로 문제에 심어놓은 것이다.
(때문에 무시하고 재귀를 돌려도 상관없다.)

결국 메인은 제곱근을 구하는 것이 맞고, 큰 숫자일때 edge case로 나머지 연산자가 잘 작동되면 된다.

 

---

 

2️⃣ 두번째 풀이:  시간복잡도 success

 

일단 정답 코드부터 보면...

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

  const half = power(base,parseInt(exponent / 2));
  const result = (half * half) % 94906249; //🛑 여기서 나머지를 해줘도 

  if (exponent % 2 === 1){
  	return (base * result) % 94906249; //🛑 여기 값에 지장없다. (단! 작은수에선, 큰수에선 갭이 생긴다.)
  } 
  else return result;
}

 

🛑 으로 표시한 부분이 매우매우 헷갈릴 수 있는데, 여기서 위에서 설명했던 나머지의 성질을 잘 적용해서 생각해봐야한다.

큰 숫자일때를 먼저 보자,

 

Math.pow(5,23) % 94906249 //66123042

//위와 아래의 숫자는 비슷하긴 하지만 다르다!!

5 * (Math.pow(5,22) % 94906249) % 94906249 //66123043
5 * (Math.pow(5,11) * Math.pow(5,11) % 94906249) % 94906249 //66123043

 

근데 작은 숫자일땐??

 

Math.pow(5,5) % 94906249 //3125

//위와 아래의 숫자가 같다!!

5 * (Math.pow(5,4) % 94906249) % 94906249 //3125
5 * (Math.pow(5,2) * Math.pow(5,2) % 94906249) % 94906249 //3125

 

' % 94906249'가 실질적으로 효력을 발휘하지 않으므로, 같은 숫자가 된다.

 

결국, 큰 숫자일때, 약간의 부정확한 결과값이 예상되더라도,

모든 연산에서 너무 큰 숫자(2⁵³ 이상)가 들어가버리면 안되기 때문에, 연산마다 안전장치로 넣어주는 것이다.

 

아래의 경우도 그 예시라고 봐도 된다. 

 

Math.pow(5,1000) % 94906249 === NaN

//Math.pow(5,1000)까지 다 계산하고 NaN을 리턴하는 것보다
//분할정복접으로 쪼개서 계산하는 와중에 Math.pow(5,500)에서 NaN이 리턴된다면?

let half = Math.pow(5,500) % 94906249 === NaN
half * half % 94906249
//NaN * NaN % 94906249 === NaN 
//훨씬 연산이 빨라진다.

 

거의 없는 경우인 큰 숫자일 때에 값의 약간의 부정확함보단,

성능면을 더 고려한 문제라고 보면 될 것 같다. 

 

그냥 문제의 의도 자체가

엄청 큰 숫자까지 완벽대응할 필요는 없지만, 시간복잡도를 고려할줄 알아야되는 문제라고 보면 된다.

 

 

와... 이해하느라 진짜 너무 힘들었다...