🍀TIL🍀[프로그래머스] Coding Test 스터디15

썸네일은 졸업 선물로 받은 목걸이🍀 드디어 졸업했다~

Q1. 피보나치 수열

피보나치 수는 F(0) = 0, F(1) = 1일 때, 1 이상의 n에 대하여 F(n) = F(n-1) + F(n-2) 가 적용되는 수 입니다.

예를들어

F(2) = F(0) + F(1) = 0 + 1 = 1
F(3) = F(1) + F(2) = 1 + 1 = 2
F(4) = F(2) + F(3) = 1 + 2 = 3
F(5) = F(3) + F(4) = 2 + 3 = 5
와 같이 이어집니다.

2 이상의 n이 입력되었을 때, n번째 피보나치 수를 1234567으로 나눈 나머지를 리턴하는 함수, solution을 완성해 주세요.

제한 사항

• n은 2 이상 100,000 이하인 자연수입니다.

🐣내 코드

function solution(n) {
    /*
    //재귀 함수 사용 (시간 초과)
    const recurse = (num) => {
        if(num === 0){
            return 0
        }
        if(num === 1){
            return 1
        }
        return recurse(num-1) + recurse(num-2)
    }
    
    return recurse(n)
    */ 
    
    // DP 사용 풀이 
    
    let first = 0, second = 1, target = 0;
    
    for(let i = 2; i <= n; i++){
        target = (first + second) % 1234567;
        
        first = second; 
        second = target;
    }
    
    return target; 
    
}

• 처음에는 시간 복잡도를 생각 못하고 재귀로 풀어봤는데, 시간 초과가 떴다...! 그래서 DP로 다시 풀었다.

• for문을 2부터 n까지 돈다.

  • 0과 1을 안도는 이유: i=2일때 target = (first + second) 에서 이미 F(2) = F(0) + F(1)이 되기 때문에!

• target은 F(n)
first는 F(n-1)
second는 F(n-2)라고 생각하면 된다.

• first = second와 second = target 으로 n를 하나씩 올려 준다.

🦖느낀 점

DP로 푸니까 로직은 재귀랑 비슷한데 시간 복잡도가 더 줄어들어서 신기했다. 다음부터는 문제 풀기 전에 시간 복잡도를 좀 더 꼼꼼히 생각하고 풀자!