JS, 프로그래머스 - 멀리뛰기

피보나치수 처음에 한눈에 알아보기 정말 어려워....

 

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

프로그래머스

 

문제는

 효진이는 한 번에 1칸, 또는 2칸을 뛸 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567을 나눈 나머지를 리턴하는 함수, solution을 완성하세요.

 

처음에는 문제는 이해해도 규칙성을 파악하지 못해 오래 걸림 n이 3,4,5... 일 경우 각각 답을 구해보아도 규칙성이 안 보였음 시간이 오래 걸려 마침내 규칙성을 찾아내 바로 피보나치 수였던 것!!

 

이렇게 생각하면 되는데 만약 n의 답을 찾는다면 맨 마지막이 1칸 뛰거나 혹은 2칸 뛰거나로 2가지 경우가 됨

그렇다면 마지막을 1칸 뛴다면 그 앞은 한 칸을 제외한 n-1이 되고 2칸을 뛴다면 그 앞은 n-2가 됨

즉 n의 경우의 수 = n-1의 경우의 수 + n-2의 경우의 수가 되는 것(n = n-1 + n-2)

 

function solution(n) {
    const d = [0, 1, 2, 3];

    for(let i = 4; i <= n; i++) {
        d[i] = (d[i - 1] + d[i - 2]) % 1234567;
    }

    return d[n];
}

 

처음에는 피보나치를 생각하여 메모이제이션을 생각하자고 생각함

n+1이 되어도 n과 n-1에 더한 값이기 때문에 값이 누적되는 것이어서 반복적인 작업을 할 필요 없이 값을 저장해 놓는 것이 좋다고 생각했는데 생각해 보니 결론적으로는 n을 구하기 위해 필요한 값은 결국 n-1, n-2이기 때문에 불필요한 값들도 다 저장해 놓는 것인가라는 생각으로 바뀌게 됨 

 

function solution(n) {
    if (n <= 2) return n;
    let a = 1, b = 2, c;
    
    for (let i = 3; i <= n; i++) {
        c = (a + b) % 1234567;
        a = b;
        b = c;
    }
    return b;
}

 

모든 값을 저장하는 것이 아닌 필요한 변수만 사용하여 n-2 이의 값을 저장할 a, n-1의 값을 저장할 b, n의 값을 저장할 c로 해서 c에서 현재 n개의 개수를 구한 값을 저장하고 그 후 다음 턴에 값을 구하기 위해 a와 b을 값을 각각 다음 값으로 저장함

 

😉🤔

아직까지는 문제를 보고 한눈에 패턴을 파악하기 어려워.... 문제의 주어진 값들을 하나하나 계산해 보아 값을 확인해도 어떤 패턴이 있는지 쉽게 이해하기 어려움 다음에는 값으로 패턴을 확인하기 어렵다면 주어진 문제에 풀이에 집중하여 패턴을 찾아보아야겠음 항상 이런 반복적인 계산한 값을 사용할 때는 메모이제이션이 핵심이다라고 생각하여 최종코드라고 생각하고 더 나은 방향으로 코드를 개선할 점이 없다고 생각했는데 시간복잡도 측면이 아닌 좀 더 고민해서 필요한 변수만 사용하여 공간 복잡도를 줄이는 방향으로 코드를 개선해 보니 훨씬 좋아 보임

 

코딩 문제를 해결하는 데 있어서는 직관적으로 규칙을 찾는 능력뿐만 아니라 효율적인 알고리즘을 작성하는 능력 두 개가 모두 중요하다는 생각이 듦 이런 능력을 키워나가기 위해 문제를 반복적으로 풀어보고 더 나은 개선 방안을 살펴보고 더 많은 문제를 풀어야겠음