멀리뛰기 문제

https://school.programmers.co.kr/learn/courses/30/lessons/12914

초안 (재귀)

잘 보면 피보나치 수열을 구하는 문제임을 알 수 있다.
그래서 재귀함수를 사용해 풀었는데 시간 초과로 탈락.

function solution3(n) {
    let answer = 0;
    function backtrack(n) {
        if (n < 2) {
            return 1;
        }
        return backtrack(n - 1) + backtrack(n - 2);
    }
    answer = backtrack(n) % 1234567;
    return answer;
}

수정안 1 (반복문, 배열)

function solution2(n) {
    var answer = 0;
    let arr = [0, 1, 2];
    for (let i = 3; i <= n; i++) {
        let num = arr[i - 2] + arr[i - 1];
        arr.push(num);
        console.log(arr[arr.length - 1]);
    }
    answer = arr[n] % 1234567;
    return answer;
}

이렇게 배열을 사용해 중복 계산을 피하고 뒤의 두 숫자들을 더하도록 만들었다.

재귀방식 풀이의 단점은 backtrack(n)의 결과를 저장해두지 않는다는 것.
피보나치 수열에서 3->3 이고 4->5다.
backtrack(3)의 결과는 3이고, backtrack(4)의 결과는 5 라는 사실을 어디에 저장해 둔다면?
backtrack(5)를 할 때 굳이 3과 4의 경우로 나누어 재귀함수 호출을 하는 대신 두 숫자를 더하기만 하면 된다.
위의 결과도 저장되어있다면 backtrack(6)은 또 굳이 재귀함수 호출을 반복하는 대신 또 두 숫자를 더하는 간단한 연산만 수행하면 된다.

그런데 이렇게 제출해보니 이번에는 시간 초과가 아니라 아예 오답이라고 한다.

답안

function solution(n) {
    var answer = 0;
    let arr = [0, 1, 2];
    for (let i = 3; i <= n; i++) {
        let num = arr[i - 2] + arr[i - 1];
        arr.push(num % 1234567);
        console.log(arr[arr.length - 1]);
    }
    answer = arr[n];
    return answer;
}

Number 타입

원인은 JavaScript에서는 모든 숫자를 Number 타입으로 저장하는데,
이 Number는 64비트 부동소수점 표기법으로 모든 숫자를 저장한다.
(그래서 3/2를 하면 나머지를 버리지 않아 꼬박꼬박 Math.floor(3/2)를 해줬어야 했던가보다)
$6=110_2=1.10*2^2$
위 처럼 정규화를 거치고,
부호(1) | 지수 (11) | 가수 (52) 의 조합으로 총 64비트로 이루어진 이진수가 된다는 것이다.
0 10000000001 1000000000000000000000000000000000000000000000000000

여기서 추측할 수 있는 Number 타입의 한계로는 무엇이 있을까?

지수

지수 11비트 : 2048개(0부터 2047) 숫자 표현 가능.
지수란 위에처럼 6을 $1.10 * 2^k$ 로 나타냈을 때 k에 해당하는 숫자다. 이 경우 k=2.
그런데 1보다 작은 소수를 표현하는 경우에는 지수 k가 음수가 된다.

2의 보수 방식 vs bias 방식

원래 컴퓨터로 음수를 표현하는 방식은 2의 보수 방식을 쓴다.
4비트에서 +5는? 0101이다.
-5는 1011이다. ($ZtS_{3}(−5) = NtS_4(2^4−5)=1011$ )
둘이 더하면 1 0000이 되고 추가로 늘어단 1 비트는 빠지게 되고 0000만 남아서 0이 된다.

그런데 bias 방식은 그냥 11비트 기준으로 1023($2^{11-1}-1$)을 더한다.
지수가 0 이면 거기에 1023을 더한 1023인 01111111111 이 된다.
원래 방식과 반대로 음수(혹은 0)일 경우 앞에 비트가 0 이 된다. (1 부터 1 + 1023 = 1024 = 10000000000)

왜 bias방식을 사용하는가? (장점)

이렇게 하면 직관적으로 01111111111이 10000000000보다 작다는걸 바로 이해할 수 있다. 그리고 그리고 모든 숫자를 부호 비트를 사용하지 않고 양수로 만들기 때문에(-1022+1023=1) 비교가 쉬워진다.

왜 bias방식을 사용하지 않는가? (단점)

그럼 비교가 쉽고 직관적으로 이해하기도 편한 이 방식을 왜 평소에도 모두가 사용하지 않을까?

가수

가수의 52비트가 실질적으로 숫자를 표시할 수 있는 부분이기 때문에 실질적으로 64비트를 사용하지만 52비에 숨겨진 비트 1을 더한 $2^{53}$개의 자연수만을 표기할 수 밖에 없다는 한계가 있다. ```

console.log(Number.MAX_VALUE); // 1.7976931348623157e+308
console.log(Number.MIN_VALUE); // 5e-324
console.log(Number.MAX_SAFE_INTEGER); // 9,007,199,254,740,991
console.log(Number.MIN_SAFE_INTEGER); // -9007199254740991

자바의 long도 64비트를 사용하는데 JS보다 $2^{64}-2{53}=2^{11}$배 더 많은 정수를 표현할 수 있다.

infinity

내 수정안 코드의 문제점도 여기에 있다.
피보나치 수열을 구할 때 1477부터 위의 Number.MAX_VALUE를 초과하게 되고, 그 뒤로 모든 숫자는 infinity라고 저장된다.
infinity % 1234567은 숫자가 아니니 NaN이 되는것이고 그래서 틀렸던것.