오늘 공부

알고리즘 문제 풀기(프로그래머스)
https://github.com/hoinlee-moi/Algorithm

JS기본문법 다시 공부
https://github.com/hoinlee-moi/ModernJS

React 강의 듣기
https://github.com/hoinlee-moi/React_prac

슬슬 알고리즘의 난이도가 어렵긴 하다.. 리액트 강의는 재밋어지고 한쪽이 재밋어지니 한쪽이 어려워지는 현상!

오늘알고리즘

피보나치 수 - https://school.programmers.co.kr/learn/courses/30/lessons/12945#

function solution(n) {
    let f0 = BigInt(0)
    let f1 = BigInt(1)
    let fn = BigInt(0)
    for(let i=2; i<=n;i++) {
        fn = f0 + f1
        f0=f1
        f1=fn
    }
    return fn%BigInt(1234567);
}

일단 이렇게 진행을 했다. 맨 처음은 재귀함수를 통해 진행했지만 숫자가 조금만 커져도 엄청나게 잡아먹는 시간과 메모리 때문에 반복문을 이용해 봤다.
하지만 반복문을 할 때도 계속 답이 다르게 나와 왜 그런가 봤더니 피보나치의 수 는 20정도만 돼도 4자리 수가 나오는데 제한 조건이 100000까지이니 엄청난 자릿수 나올거라 생각한다.
그래서 2가지의 방법이 있었는데 먼저 BigInt를 이용해 자릿수를 크게 만들어주니 괜찮아졌다.

그리고 다른 방법은 계산마다 나눗셈을 진행시키는 건데 그러면 훨씬 좋아지긴 한다.
먼저 앞서 재귀 함수를 이용했을 때 만든 함수이다.

function fibonacci(num) {
    if (num === 1 || num === 2) {
        return 1
    } 
    return fibonacci(num-1) + fibonacci(num-2)
}

• 피보나치의 공식이 계속해서 반복되도록 재귀함수를 만들었지만 많은 시간과 메모리를 먹어서 반복문으로 변경

function solution(n) {
   let result = [0 , 1];
   while ( result.length !== n + 1) {
       let fibonacci = (result[result.length - 2] + result[result.length - 1]) % 1234567
       result.push(fibonacci);
   }
    return result[n];
}

위의 코드는 BigInt를 이용한 것이 아닌 계산 마다 1234567의 나머지 계산을 하여 자릿수를 줄였다.

매번 풀어보다 간혹 등장하는 시간적 효율이나 메모리 등을 신경쓰는 단계까지 와야하는 것 같다.