function power(base, exponent) {
// 지수가 0일 경우 바로 1을 리턴.
if (exponent === 0) return 1;
const half = parseInt(exponent / 2);
// console.log("확률을 반으로 나눔 :", parseInt(40 / 2))
//
const temp = power(base, half);
// console.log("위의 나눈 값을 또반으로 나눔 :", power(3,20))
// 스택이 초과됨..
// 왜 이것을 나눌까 ?
const result = (temp temp) % 94906249;
// console.log(power(3,20) power(3,20) % 94906249)
if (exponent % 2 === 1) return (base * result) % 94906249;
else return result;
}
let output = power(3, 40);
console.log(output); // --> 19334827
/*
1. 밑과 지수의 거듭제곱근. power 연산자 사용금지함. 시간복잡도만족
1) 구글링을 해보자! 빅오란 ?
데이터와 사용량에 따른 알고리즘의 성능을 예측하는것이 목표. -> 2진검색
k
parseInt는 (string , radix(진수)) 로 이루어져있다.
그러니까 짧막하게 쉽게 이야기하면,
radix가 2보다 작거나 36보다 큰 경우
첫번째 non-whitespace 문자가 숫자로 변환되지 않는 경우
이면 모두 'NaN'으로 반환하고 그렇지않다면 특정 입력된 진수로 반환이된다.
parseInt 함수는 정수값으로 숫자를 잘라버린다. 그리고 맨 앞의 공백과 그 뒤의 공백들은 허용한다. 이런 정수값을 리턴하는 속성때문에
math.floor와 가끔 혼용되어 사용되긴하나 하지만 엄밀히, 사용하게되면 다른 결과값을
나타낼 수있다.
어떤 로직으로 설계하였는가 ?
ey =6, 숫자 6을 찾기 절반씩 줄여가며 찾아보기.
1,2,3,4,5//,6,7,8,9
--------- 이중에 검색
6 ---- 뒤에도 없음
원하는값 6
하나하나 이렇게 줄여가는 log(n) 로직으로 작성하였다.
하지만 콘솔로그를 찍고 아래와 같이 주석을남겼으나 시간이 초과..
temp*temp 를 해주는 이유
temp temp 는 2^4 2^4 = 2^8 이라는 것을 생각해 보시면 이해가 되실것 같은데요,
2^8을 구하려면 2^1, 2^2, 2^3... 이런식으로 계산해 나가는데,
2^4 2^4 = 2^8 이 되기 때문에 굳이 2^6,2^7, 2^8 까지 올라갈 필요가 없죠.
따라서 temp temp 로 알고리즘의 효율성을 높여주는 것이며,
대신 temp 의 두 번째 인자로 주어진 exponent 의 절반을 넣어주는 것입니다.
- 헬프데스크, newkidsean님의 답변.
1. 문제 흐름 파악 -> 문제에서 나에게 어떤 상황이 주어졌는가?
* 무슨 문제일지 파악할때까지, 레퍼런스 보지않기. 간단히 어떤 전략으로 해결할지 생각
2. 레퍼런스보기 -> 1) 크게 코드를 쭈욱 읽어보고 큰 줄기를 파악 (어떤 로직과 설계를 썼는가.. )
2) RunJs를 통해 실시간으로 console.log를 찍고 컴퓨터와 하나하나 이야기해보기
3) 파악
4) 반복 & 복습(자기전에 간단히) 1~3번 사항을 다시 해봄. (하루에 처음접근, 주어진 시간동안 재귀..)
5) 아침에 일찍일어나서 다음 알고리즘 문제 풀기전에 같은 문제를 또 접근해봄.
6) 2일 혹은 3일 사이클로 문제는 누적하여 , 하루에 3문제
(버블sort 알고리즘, queue 처럼 먼저 배운것은 빼고 나중에.. )
7) 만약에 되면.. 주말에 토요일 3문제, 일요일 3문제 총 5문제에서 6문제 일주일 결산으로 반복.