[220105] Lv.2 피보나치 수열 / 메모이제이션으로 풀기

수업중에 피보나치 수열의 예제로 나왔던 문제. 꾸역꾸역 일단 풀음. 손에 익히는게 먼저야.

 

 

교수님 답변

let num=[];
//계산한 결과값 저장
//첫번재 원소값 1, 두번째 원소값 2

function fibo2(n){

	//조건1
	if(num[n] > 0) {
		return num[n];
        
	//조건2
	} else if(n===1 || n===2) {
		return num[n]=1;
        
	//조건1이랑 조건2는 중요도가 같아서 뒤바뀌어서 시간복잡도 상관 ㄴㄴ    
	} else {
		return num[n] = fibo2(n-1) + fibo2(n-2);
	}
}

 

이건 내가 문제를 한번 풀고 기억을 더듬어서 풀어본 방법

function solution(n) {
    let answer = [];
    
    //확률적으로 값이 0~2인것보다 다른 숫자일리가 더 많으니까 계산 횟수를 줄이기 위해 제일 큰 경우를 조건으로 걸어주자.
    if(answer[n]>0){
        return answer[n];
    
    //그러면 너 0~2냐? 하고 묻는 코드
    } else if(n<=2) {
        if(n==0){return answer[n]=0;}
        else{return answer[n]=1;}
        
    //둘 다 아니면 너임마 계산해야겠구나! 코드
    } else {

        //여기에서 자기자신을 불러서 콜스택에 쌓아놓기
        //끝까지 콜스택에 쌓아놓았으면 위부터 불러내서 계산때리기
        return answer[n]=solution(n-1) + solution(n-2);
    }
    
    return answer;
}

 

 

내가 이해한 내용

    let numbers = [];
    function solution(n) {
        if (numbers[n]>0){
            return numbers[n];
        } else if(n ===1|| n===2){
            return numbers[n]=1;
        } else {
            return numbers[n] = fibo2(n-1) + fibo(n-2);
        }
    }



    n=4일때
    코드가 실행된 순서대로 번호를 붙였다.

    5) fibo(1) <Call-4> = else if에 걸려서 1이 저장됨.              //numbers[1] = 1
    4) fibo(2) <Call-3> = if에 걸려서 1이 반환됨 (Call-2 참조)       //저장된 값 반환
    3) fibo(2) <Call-2> = else if에 걸려서 1이 저장됨               //numbers[2] = 1
    2) fibo(3) <Call-1> = fibo(2) <Call-3> + fibo(1) <Call-4>   //numbers[3]=fibo(2) + fibio(1)
    1) numbers[4]=fibo(3) <Call-1> + fibo(2) <Call-2>           //numbers[4]=fibo(3) + fibo(2)
    ----> 콜 스택에 쌓기 끝




    | 4) numbers[1]=1      |  ---> 콜스택에서 맨 위에서부터 꺼내서 실행 
    | 3) numbers[2]=1      | 
    | 2) fibo(2) + fibo(1) |
    | 1) fibo(3) + fibo(2) | (콜스택)
    --------------------



    4) fibo(3) + fibo(2) --> 연산해서 계산
    3) fibo(2) + fibo(1) --> 연산해서 계산
    2) numbers[2] =1
    1) numbers[1] =1