카테고리 없음

자바스크립트로 하는 자료구조와 알고리즘(3장) - 숫자

sunnykim91 2019. 10. 16. 15:37

자바스크립트 숫자

자바스크립트는 64비트 부동소수점 표현을 사용한다.

 

0.1 + 0.2 === 0.3  // false 

 

자바스크립트에서는 0.1이라는 숫자를 정확하게 표현이 불가능하다. 

ex) 0.1은 즉 1 / 10 이다. 

10은 이진수로 나타내게 되면 1010이다.

1을 1010으로 나눠보면 즉 0.00011..... 무한대의 숫자로 표현되게 된다.

 

자바스크립트 숫자 객체 중에 정수로 표현하기 위한 Number객체에 다양하게 내장되어있는 것들이 있음.

 

Math.floor 내림

Math.round 반올림

Math.ceil 올림

 

Number.EPSILON

두 개의 표현 가능한 숫자 사이의 가장 작은 간격(최소 차이)을 반환한다.

ex)

function numberEquals(x,y){
	return Math.abs(x-y) < Number.EPSILON;
}

numberEquals(0.1 + 0.2, 0.3)  // true

 

Number.MAX_SAFE_INTEGER 는 가장 큰 정수를 반환함

Number.MAX_VALUE 는 가능한 가장 큰 부동 소수점을 반환

MIN은 반대

 

무한대 Infinity , -Infinity

 

숫자 알고리즘

 

소수 찾기 

 

일반적인 방법 ( O(n) )

function isPrime(n){
  if(n<=1){
    return false;
  }

  for(let i =2;i<n;i++){
    if(n%i === 0){
      return false;
    }
  }

  return true;
}

 

2와 3을 제외하고는 모든 소수는 6K 플마1의 형태를 지님

 

또한 n이 소수인지 알아보기 위해 반복문을 n의 제곱근까지만 확인해보면 된다.

n의 제곱은이 소수가 아니면 n은 수학 정의에 의해 소수가 아니기 떄문

 

아래와같이 하면 O(루트n)시간

function isPrime(n){
  if (n <= 1) return false; 
  if (n <= 3) return false;

  if (n%2 ==0 || n%3 == 0) return false;

  for(let i=5; i*i <= n; i=i+6){
    if(n%i ==0 || n%(i+2) == 0){
      return false;
    }
  }

  return true;
}

 

 

소인수분해

function primeFactors(n){

  // 2로 나누었을때 떨어지면 그만큼 2를 출력하면서 를 나눠간다.
  while(n%2 === 0)  {
    console.log(2);
    n = n/2;
  }


  // 여기선 n이 홀수일 것이다. 그 홀수에 대해서 다시한번 나눠떨어지는 수가 있는지 찾고 그수를 출력한다.
  for(let i=3;i*i <=n;i=i+2){
    while(n%i ===0){
      console.log(i);
      n = n/i;
    }
  }

  // n이 아직도 분해가 안됬다는것은 소수라는 뜻이므로 그것을 출력
  if(n>2){
    console.log(n);
  }
}

primeFactors(1568);

시간복잡도 O(루트n)

 

무작위 수 생성 

Math.random() : 0과 1사이의 부동소수점을 반환한다.

 

연습문제

1. x와 y,p 라는 세개의 숫자에 대해 (x^y) % p 를 계산하라 (= 모듈러 거듭제곱)

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

  let value = 1;

  for(let i=0; i < exponent; i++){
    value = (value * base) % modulus;
  }
  return value;
}

암호화알고리즘에 사용되는 경우 기저가 6*10^77 , 지수가 27, 모듈러가 497 이런식으로 되는 경우가 있다.

이 경우에는 위코드로 푸는것이 효과적이다.

 

시간복잡도는 O(n)

 

2. n보다 작은 모든 소수를 출력한다.

위의 isPrime함수를 호출해서 true,false값을 통해서 검사하면서 출력하면 된다.

 

 

반응형