3장 자바스크립트 숫자
- 자바스크립트에서는 숫자에 대해 64비트 부동소수점 표현을 사용한다
→ 부호 1비트 + 지수 11비트 + 소수 52비트 - 십진분수로 인해 반올림 오류를 일으킬 수 있다
0.1 + 0.2 === 0.3; // false - Number 객체에 내장된 속성들
- 정수 반올림
1
2
3Math.floor // 내림
Math.round // 반올림
Math.ceil // 올림 - Number.EPSILON : 두 개의 표현 가능한 숫자 사이의 가장 작은 간격을 리턴함
- 가장 큰 정수 : Number.MAX_SAFE_INTEGER
Number.MAX_SAFE_INTEGER + 1 === Number.MAX_SAFE_INTEGER + 2 // true - 가장 작은 정수 : Number.MIN_SAFE_INTEGER
Number.MIN_SAFE_INTEGER - 1 === Number.MIN_SAFE_INTEGER - 2 // true - 양의 무한(Infinity)값은 Number.MAX_SAFE_INTEGER보다 큰 유일한 값이며 음의 무한(-Infinity)값은 Number.MIN_SAFE_INTEGER보다 작은 유일한 값이다
- 정수 반올림
- 숫자 알고리즘
- 소수 테스트1-1. 개선된 소수 테스트
1
2
3
4
5
6
7
8
9
10
11function isPrime(n) {
if (n <= 1) return false;
for (let i = 2 i < n; i++){
if (n%i == 0) {
return false
}
}
return true
}
// 시간 복잡도 O(n)1
2
3
4
5
6
7
8
9
10
11
12
13
14
15// 소수는 6k±1의 형태를 지님
// ex) 5 = 6-1, 7 = ((1*6) + 1), 13 = ((2*6) + 1) 등
function isPrimeAdvanced(n) {
if (n <= 1) return false
if (n <= 3) return true
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;
}
// 시간 복잡도 O(sqrt(n)) - 소인수분해
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19function primeFactors(n) {
while (n%2 == 0) {
console.log(2);
n = n/2
}
// n%2가 0이 아닐때까지 나눠 n은 이 시점에서 홀수가 됨
for (let i = 3; i * i <= n; i = i+2){
// i가 n을 나눌 수 있는 한 계속해서 i가 출력되고 n을 i로 나눈다
while (n%i == 0) {
n = n/i
}
if (n > 2) {
console.log(n);
}
}
}
primeFactors(10) // 5, 2를 출력
// 시간 복잡도 O(sqrt(n)) - 무작위 수 생성
1
Math.random() * n + x // x부터 (n+x)까지의 랜덤한 정수를 생성한다
- 모듈러 제곱거듭(modular exponentiation) : 단순한 계산법4-1. 모듈러 제곱거듭(modular exponentiation) : 큰 지수도 다룰 수 있는 함수
1
2
3const modularExponentiation = (x, y, p) => {
return Math.pow(x, y) % p
}
→ 임의의 a와 b에 대해c % m = [(a % m)(b % m)] % m이 성립1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34const modularExponentiation = (base, exponent, modulus) => {
if (modulus == 1) return 0;
// 1. 값 = 1로 설정한다. 지수는 0이다
let value = 1;
// 2. 현재 지수를 1만큼 증가시킨다
for (let i = 0; i < exponent; i++) {
// 3. 현재 지수가 목표의 지수가 될 때까지
// '값 = (값 x 기저) % 모듈러'를 반복한다
value = (value * base) % modulus;
}
return value;
}
```
5. n보다 작은 소수 찾기
```javascript
const allPrimesLessThanN = n => {
for (let i = 0; i < n; i++){
if (isPrime(i)) console.log(i);
}
}
const isPrime = n => {
if (n <= 1) return false
if (n <= 3) return true
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;
} - 소인수 집합 확인
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25// 모든 소인수는 2와 3과 5로 나눠질 수 있다
const maxDivide = (number, divisor) => {
while (number % divisor === 0) number /= divisor;
return number
} // 시간 복잡도는 O(divisor를 밑으로 하는 log (number))
const isPrimeFactor = number => {
number = maxDivide(number, 2)
number = maxDivide(number, 3)
number = maxDivide(number, 5)
return number === 1;
} // 시간 복잡도는 O(log2(n))
const primeFactorArr = n => {
let count = 0, currNum = 1, primeNums = [];
while (count != n) {
if (isPrimeFactor(currNum)) {
count++;
primeNums.push(currNum)
}
currNum++
}
return primeNums;
} // 시간 복잡도는 O(n(log2(n))) O(n번 * isPrimeFacor의 BigO 값)4장 자바스크립트 문자열
- 소수 테스트
- 자바스크립트의 기본 자료형인 String에는 다양한 함수가 존재
- 문자에 접근할 때엔 .charAt()을 사용한다
'dog'.charAt(1) // "o"
1-1. substring(startIdx, endIdx)을 사용하면 지정된 값 사이의 문자열의 리턴이 가능하다
1-2. 이때 endIdx를 입력하지 않는다면 자동으로 문자열 마지막까지 리턴한다 - 문자열을 비교할 때에는 < 나 > 기호를 통해 쉽게 비교할 수 있다
1
2
3
4
5
6
7
8
9
10
11
12
13let a = 'a'
let b = 'b'
console.log(a < b) // true
/*------------------------------*/
// 길이가 다른 문자열을 비교한다면 문자열의 시작부터 비교하여
// 더 짧은 길이의 문자열길이만큼만 비교한다
a = 'add'
b = 'b'
console.log(a < b) // true
/*------------------------------*/
a = 'add'
b = 'ab'
console.log(a < b) // false - 문자열 내 특정 문자열을 찾기 위해 .indexOf(searchValue[, fromIndex])를 사용할 수 있다
3-1. 검색하고자하는 문자열을 매개변수로 받으며 선택적으로 검색 시작의 인덱스를 받을 수 있다
3-2. 이 함수는 일치하는 문자열의 위치를 리턴하며 대소문자를 구분한다
3-3. 없다면 -1을 리턴하므로 -1을 반환하는지 아닌지를 확인하면 된다 - 문자열을 분해할 때에는 .split(separator)를 사용할 수 있으며 분리자 매개변수를 받아 부분 문자열 배열을 생성한다
- .replace(string, replaceString)함수는 문자열 내 특정 문자열을 대체하는 함수이다
- 정규 표현식은 검색 패턴을 정의한 문자열의 집합으로 기본 객체 RegExp를 사용할 수 있다
6-1. RegExp의 생성자는 정규 표현식과 일치 관련 설정의 두 가지 매개변수를 받는다
6-2. i는 대소문자를 구분하지 않고 일치하는 문자열을 검색하며, g는 전역적으로 ((모든) 문자열을 검색하며, m은 다중열 문자열에 대해서도 일치하는 문자열을 검색한다
6-3. RegExp는 search()와 match() 함수가 존재하며 search()는 찾은 문자열의 인덱스를, match()는 모든 일치하는 문자열을 리턴한다
6-4. String 객체에서 RegExp를 매개변수로 받는 함수는 일치하는 문자열을 찾는 exec()와 문자열을 찾아 boolean값을 리턴하는 test()가 있다1
2
3
4
5
6
7
8
9
10
11
12<--- 기본 정규 표현식 --->
^ :문자열/줄의 시작을 나타냄
\d : 모든 숫자를 찾는다
[abc]/[^abc] : 괄호 내 모든 문자를 찾는다 / 제외한 문자열을 찾는다
[0-9]/[^0-9] : 괄호 내 모든 숫자를 찾는다 / 제외한 숫자를 찾는다
(x|y) : x나 y 문자열을 찾는다
<--- 자주 사용되는 정규 표현식 --->
/\d+/ : 숫자를 포함하는 문자
/^\d+$/ : 숫자만 포함하는 문자
/^[0-9]*.[0-9]*[1-9]+$/ : 부동 소수점 문자
/[a-zA-Z0-9]/ : 숫자와 알파벳만 포함하는 문자
/([^?=&])(=([^&]*))/ : 질의 문자열 - 자바스크립트의 base() 함수는 문자열로부터 Base64 인코딩된 ASCII 문자열을 생성하며 atob() 함수는 Base64 인코딩된 문자열을 디코딩하는 함수이다
7-1. 단축 URL은 이 base() 함수를 응용하여 사용하는 것이다 - RSA 암호화는 키 생성, 암호화, 복호화의 3단계가 있으며 매우 큰 소수를 사용하여 소인수분해(4096비트 소수 곱을 사용)의 역계산을 어렵게 한다
