멀리뛰기 문제

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)의 결과를 저장해두지 않는다는 것. 5의 피보나치 수열을 구할때 재귀의 방식은 다음과 같이 아래로 내려가면서 재귀 함수를 호출한다.

// 5를 구하기 위해서 4와 3을 구해야하는데, 4를 구하기 위해서는 3과 2를 구해야하고, 다시 3을 구하기 위해서 .... 

5 : backtrack(4) + backtrack(3)
4 : backtrack(3) + backtrack(2)
3 : backtrack(2) + backtrack(1)
2 : backtrack(1) + backtrack(0)
1 : 1
0 : 0

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

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

답안

수정안이 오답이라고 나온 원인은 마지막에 답을 반환할 때에만 모듈러 연산을 넣어줬기 떄문이다. 피보나치 수열을 구할 때 1477부터 자바스크립트의 Number.MAX_VALUE를 초과하게 되고, 그 뒤로 모든 숫자는 infinity라고 저장된다. infinity % 1234567은 숫자가 아니니 NaN이 되는것이고 그래서 틀렸던것.

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;
}

모듈러 연산의 특징

그런데 모듈러 연산을 배열에 추가할때 하는것과 마지막에 반환할때만 하는것이 결과적으로 같은 값을 가질까? 즉 자바스크립트의 한계를 넘어서 진짜 숫자를 계산할 수 있다고 가정하고

arr.push((arr[i-2] + arr[i-2]) % 1234567);
//...
return arr[n];

이것 처럼 배열에 넣을때 마다 모듈러 연산을 한 후에 넣는 것과

arr.push(arr[i-2] + arr[i-1])
//...
return arr[n] % 1234567;

이것 처럼 마지막에만 모듈러 연산을 거치고 반환하는것이 수학적으로 같은 값을 가질까?

작은 예시

6의 피보나치 수열을 두 가지 방법으로 구해본다.

1. 숫자를 배열에 담을때마다 3 모듈러 연산을 한다.
2. 최종 결과를 반환할때만 3 모듈러 연산을 한다.

1번 방법

시작 : arr = [0,1]
2 : 0+1=1, 1 % 3 = 1 , [0,1,1]
3 : 1+1=2, 2 % 3 = 2 , [0,1,1,2]
4 : 1+2=3, 3 % 3 = 0 , [0,1,1,2,0]
5 : 2+0=2, 2 % 3 = 2 , [0,1,1,2,0,2]
6 : 0+2=2, 2 % 3 = 2 , [0,1,1,2,0,2,2]

arr[6] = 2

2번 방법

시작 : arr = [0,1]
2 : 0+1=1, [0,1,1]
3 : 1+1=2, [0,1,1,2]
4 : 1+2=3, [0,1,1,2,3]
5 : 2+3=5, [0,1,1,2,3,5]
6 : 3+5=8, [0,1,1,2,3,5,8]

arr[6] % 3 = 2

원리

숫자 n과 m이 있다. 이 두 숫자는 a라는 숫자로 나누었을때 이렇게 표현될 수 있다.

• n = xa + r1
• m = ya + r2

n+m = (xa + r1) + (ya + r2) = a(x + y) + (r1 + r2)

위의 식에서 앞에 부분 a(x + y) 는 당연히 a로 나누어 떨어지는 부분이기 때문에 r1 + r2 만 남게 된다. 그래서 결과적으로 나머지끼리 더하는것과 같게 된다.