Java) 피보나치 수열 + Advanced

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

 

 

피보나치 수열은 재귀 함수를 이용한 풀이가 일반적이다.

 

다음 코드와 같다.

 

public int fibonacci(int num) {
    if (num <= 1) return num;

    return fibonacci(num - 1) + fibonacci(num - 2);
}

 

이 코드의 시간복잡도는 n이 1씩 증가할 때마다 2배씩 늘기 때문에, O(2^n)이다. 

그래서, 피보나치 수열 중 35번째 이상의 항의 수를 구할 때면, 시간이 굉장히 오래 걸린다.

 

 

이러한 시간복잡도 문제를 해결하기 위한 효율적인 방법이 바로 메모이제이션(Memoization)이다.

 

다음 코드와 같다.

 

1. List 이용

public long fibonacci(int num) {
    List<Long> memo = new ArrayList<>();

    memo.add(0L);
    memo.add(1L);

    return aux(memo, num);
}
	
public long aux(List<Long> memo, int num) {
    if (memo.size() <= num) {
        memo.add(aux(memo, num-1) + aux(memo, num-2));
    }

    return memo.get(num);
}

2. Map 이용

static Map<Intger, Long> memo = new HashMap<>();

public long fibonacci(int num) {
    if (num <= 1) return num;
    
    if (memo.containsKey(num)) return memo.get(num);
    
    long result = fibonacci(num-1) + fibonacci(num-2);
    memo.put(num, result);
    
    return result;
}

이미 해결한 문제의 정답은 저장해두고, 다시 해결하지 않는다는 점에서 시간복잡도 측면에서 굉장히 효율적이게 된다.

이 코드는 시간복잡도가 O(N)이다.

 

영상이나 구글링을 해보면, 대부분 for문을 이용한 메모이제이션 방법들이 나오는데,

 

위와 같은 코드는

일반적인 기존 재귀의 방법과 for문을 이용한 메모이제이션 방법 사이의 난이도인 것 같다.

 

메모이제이션은 동적 계획법,

흔히 Dynamic Programming이라 불리는 알고리즘 중 재귀 관계를 상향식으로 해결하는 효율적인 방법이다.

 

Dynamic Programming에 대한 학습이 아직 많이 되어있지 않으므로, 추후에 내용을 덧붙일 예정이다.