프로그래머스 피보나치 수

피보나치 수는 어렸을 때부터 항상 많이 봐왔던 패턴이었습니다. 전에 정처기 공부를 할 때도 재귀함수를 통해 많이 봤었죠. 이번에 문제를 풀 때도 간단하게 재귀함수를 이용하면 쉽겠는데? 라고 생각하고 재귀함수를 통해 간단히 구현하였습니다.

 

public int solution(int n) {
    int answer = 0;

    if (n <= 1) {
        return n;
    }

    return (solution(n-1) + solution(n-2)) & 1234567;
}

 

작은 숫자에 대해선 당연히 시간은 오래 걸리지 않아 테스트를 통과했던 것 같습니다.. 하지만 숫자가 커질수록 재귀함수를 통해 반복되는 연산 횟수가 증가하여 시간초과로 테스트를 통과하지 못했었습니다. 방법이 떠오르지 않아 구글링을 통해 방법을 찾아보니 이전 반복되는 값들을 계속 연산하지 말고, 한번 연산했던 값을 메모리에 저장해서 바로 불러와서 사용하는 동적 계획법(Dynamic Programming)을 활용하면 된다고 하는군요.

 

참고한 글은 다음과 같습니다.

https://adjh54.tistory.com/201

[Java/알고리즘] 동적 계획법(DP: Dynamic Programming) 이해하기

 

이전에 계산한 값을 메모리에 저장하는 코드는 다음과 같습니다.

public int solution(int n) {
    int[] answer = new int[n+1];

    answer[0] = 0;
    answer[1] = 1;

    for (int i = 2; i <= n; i++) {
        answer[i] = (answer[i-1] + answer[i-2]) % 1234567;
    }

    return answer[n] % 1234567;
}

 

기존 0, 1의 값을 default로 메모리에 저장시켜 놓고, 배열에 들어가는 i번째 값을 각각 i-1, i-2 번쨰에 저장된 값을 더해 저장해주는거죠. 이렇게 되면 재귀함수를 통해 반복된 연산을 하지 않고 배열에 저장된 값을 바로 가져와서 사용하기 때문에 성능이 개선됩니다.

 

처음에 시간 초과가 떳을 때 Hash함수를 써서 해야하나?? hash함수를 써서 하는 방법이 있을까? 라는 의구심도 들어서 추가로 생각을 해보지 않았는데 위의 동적 계획법을 보면 hash 함수를 통해서 저장된 값을 사용하는 방법도 있겠더군요. 하나 배워갑니다. 

 

반복되는 연산은 성능을 저하시킨다. 반복되는 연산의 이전 값을 메모리에 저장하고 사용하는 것이 성능 개선에 도움이 된다!