Javascript 자료구조 및 알고리즘 공부
공부한 책: 자바스크립트로 하는 자료 구조와 알고리즘 배세민 지음 김무향 옮김. 에이콘 출판사
기초 탄탄..
var vs let
var 범위는 가장 가까운 함수 범위 이다.
let 범위는 가장 가까운 블록{} 범위 이다.
function scopeVar(print){
if(print){
var insideIf = 'hi var';
}
console.log(insideIf);
}
scopeVar(true);이 스크립트는 오류가 발생하지 않는다.
function scopeLet(print){
if(print){
let insideIf = 'hi let';
}
console.log(insideIf);
}
scopeLet(true);이 스크립트는 insideIf변수를 블록 안에서만 사용할 수 있기 때문에 ReferenceError가 발생한다.
if문 참/거짓 확인
자바스크립트는 다음과 같은 표현식을 false로 평가한다.
- false
- 0
- 빈 문자열('' 와 "")
- NaN
- undefined
- null
다음과 같은 표현식을 true로 평가한다.
- true
- 0이 아닌 다른 숫자
- 비어 있지 않은 문자열
- 비어 있지 않은 객체
0.1 + 0.2 === 0.3 은 false다.
자바스크립트는 숫자를 64비트 부동소수점 표현을 사용한다.
따라서 0.1을 정확히 표현할 수 없음.
console.log(0.1 + 0.2) => 0.30000000000000004가 출력된다.
소수 구하기 알고리즘
아래는 시간 복잡도 O(n) 알고리즘
function isPrime(n){
if(n <= 1){
return false;
}
for(var i=2; i<n; i++){
if(n%i == 0){ //2부터 나누어 떨어지는 숫자가 있다면 소수가 아님
return false;
}
}
return true; //나누어 떨어지는 숫자가 없다면 소수
}
아래는 시간 복잡도 O(sqrt(n)) 알고리즘
function isPrime(n) {
if(n <= 1) return false; //1보다 작은 소수는 없음.
if(n <= 3) return true; //2와 3은 소수
//2나 3의 배수는 소수가 아님
if(n%2 == 0 || n%3 == 0) return false;
//5부터 검사하되 제곱근 까지만 검사함.
//제곱근 안에 소수가 판정됨
//또한 2와 3의 배수를 제외하면 5,7 11,13 17,19 등의 숫자만 남게되는데
//이 숫자를 표현하면 6k+1, 6k-1 이 됨
for(var i=5; i*i<=n; i=i+6){
if(n%i == 0 || n%(i+2) ==0){
return false;
}
}
//for문에서 걸러지지 않은 숫자가 바로 소수
return true;
}Modular exponentiation(모듈러 제곱거듭)
(a^b)%p 를 계산하는 함수를 만들어 보자.
function modularExponetiation(base, exponent, modulus){
return Math.pow(base, exponent) % modulus;
}이 함수의 문제는 Math.pow()로 계산되서 나오는 값이 엄청 커서 32비트 부동소수점에 저장할 수 없는 경우는 문제 해결을 할 수가 없다.
Memory-efficient method
모듈러는 다음과 같은 분배 법칙을 갖는다.
(a * b) % m = {(a % m)(b % m) % m}
증명
위 법칙을 이용하면 다음과 같은 연산이 가능하다.
ex) base = 9, exponent = 4, modulus = 5일때 9^4 % 5 = ?
- 9^1 % 5 = 4
- 9^2 % 5 = (9%5 x 9%5) % 5 = (4x4)%5 = 1
- 9^3 % 5 = (9%5 x 9^2%5) % 5 = (4 x 1) % 5 = 4
- 9^4 % 5 = (9%5 x 9^3%5) % 5 = (4 x 4) % 5 = 1
위 처럼 한 계씩 늘려가며 계산하는것 뿐인데 위 식을 아래와 같이 표현 할 수 도 있다.
9%5 = 4 = 4%5라는 걸 이용해 치환하면 다음과 같이 간단하게 계산이 가능하다.
- (1 x 9) % 5 = 9 % 5 = 4
- (4 x 9) % 5 = 36 % 5 = 1
- (1 x 9) % 5 = 9 % 5 = 4
- (4 x 9) % 5 = 36 % 5 = 1
(*이건 단순히 제가 나름 이해한 방법이며, 정확히 알고 계신분이 계시다면 가르침 부탁드립니다.)
위 계산 방법을 다음과 같이 정의할 수 있다.
value = (lastValue x base) % modulus;
이 공식을 recursive 하게 원하는 exponent가 될 때까지 반복한다.
코드는 다음과 같다.
function modularExpoenetiation (base, exponent, modulus){
if(modulus == 1) return 0;
var value = 1;
for(var i=0; i<exponent; i++){
value = (value * base) % modulus;
}
return value;
}시간 복잡도 O(n)으로 아무리 큰 제곱거듭 수라도 모듈러를 구할 수 있게 된다.
