티스토리 뷰

제목이 제일 고민 많이했..

지난 포스팅에서 재귀함수에 대해 간단한 예제인 팩토리얼을 통해 알아보았습니다.

혹시나 재귀에 대해 처음 접근하신다면, 우선 팩토리얼 포스팅부터 보고 오시는 것을 추천합니다.

이번 포스팅에서는 재귀함수의 또 다른 대표예제인 피보나치(Fibonacci)수열을 통해 알아보도록 하겠습니다.


피보나치(Fibonacci)란?

피보나치를 *위키백과를 참조 해보면 다음과 같다.

첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열
이다. 처음 여섯 항은 각각 1, 1, 2, 3, 5, 8이다. 편의상 0번째 항을 0으로 두기도 한다.

위키백과 이미지 참조

다음과 같은 그림을 보여준 이유는 실제로 문제에서 적용될 수 있는 타일 문제를 이해하기 좋다.

 

 

즉 피보나치 수열이 1,1,2,3,5,8,13,21,34,55... 처럼 증가하는 규칙성을 파악할 수 있는데, 이를 점화식으로 나타내보면 다음과 같습니다.

우리가 알아볼 내용은 피보나치 수열의 수학적 관심이 아닌 프로그래밍 기법에 대한 관심이기 때문에 디테일한 설명은 생략하도록 하겠습니다.

 

바로 구현에 관한 설명으로 넘어가겠습니다.


피보나치 수열을 구현하는 방법은 여러가지가 있습니다.

그 중에서 오늘 알아보고 비교해볼 내용은 재귀함수의 직관적인 사용과 이를 개선한 동적프로그래밍(DP) 방법에 대해 알아보도록 하겠습니다.

 

재귀함수를 이용한 피보나치(Fibonacci) 수열의 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class fibonacci {
 
    public static int fibonacci(int n) {
        if (n <= 1)
            return n;
        else
            return fibonacci(n - 2+ fibonacci(n - 1);
    }
 
    public static void main(String[] args) {
        System.out.println(fibonacci(10));
    }
 
}
cs

 

결과값

매우 직관적이고, 프로그램 동작에도 이상이 없는듯하게 보입니다.

하지만 이러한 프로그래밍에는 문제점이 있는데, 바로 구하려고 하는 숫자가 커질수록 메모리 속도가 현저하게 떨어진다는 점입니다.

예를 들어 우리는 위와 같은 함수에 10이 아니라 1000을 대입해보면, 계산을 못할 것입니다.

엄밀히 말하면 계산을 못하는 것이 아닌 엄청난 시간이 필요한 것입니다.

 

이러한 이유를 설명하기 가장 좋은 그림입니다.

 

위 그림처럼 작은 숫자인 7번째를 구하는데도 매우 비효율적으로 반복되는 함수들을 볼 수 있습니다.

이는 숫자가 커지면 커질수록 반복되는 함수의 사용은 비약적으로 커지게 됩니다.

다음 그림처럼 한 함수는 두개의 함수를 호출합니다. 즉, 호출이 2배로 증가하고, 최대값은 트리의 깊이인 N만큼 늘어나기 때문에, 시간복잡도로 따지면 약 O(2N) 정도가 나오게 됩니다.

 

앞서 설명드린 내용처럼 이러한 프로그래밍은 숫자가 커질수록 비효율적이라는 것을 알 수 있습니다.

 

이러한 중복되는 부분을 제거한다면 보다 훌륭한 프로그램을 짤 수 있는데, 이 때 사용되는 방법 중 하나가 동적계획법 (Dynamic Programming, 동적 프로그래밍) 입니다.

 

 


동적계획법(Dynamic Programming)이란?
큰 문제를 한 번에 해결하기 힘들 때 작은 여러 개의 문제로 나누어서 푸는 기법

추가적으로 설명을 보태자면, 작은 문제들을 풀다보면 같은 문제들을 반복해서 푸는 경우가 생깁니다. 그 문제들을 매번 재계산하지 않고 값을 저장해두었다가 재사용하는 기법이 동적 프로그래밍입니다.

동적프로그래밍의 장점으로 모든 작은 문제들에 대해 한번씩만 풀면서 정답을 어딘가에 저장해 둡니다. 이를 활용하여 보다 큰 문제를 풀어 나갈때 똑같은 작은 문제에 대해 앞서 저장한 메모의 결과값을 이용합니다.

이러한 동적 프로그래밍 기법 중 하나로 메모이제이션(Memoization)이 있습니다.

 

 

 

프로그래밍에서는 동적계획법, 다이나믹 프로그래밍, 동적 프로그래밍, DP 등으로 말하는데, 단어로 의미를 파악할 필요는 없습니다. Dynamic 하지도, 프로그래밍이라는 단어와도 큰 연관은 없으며, 그저 처음 사용한 사람이 Dynamic이라는 단어가 멋있어서 선택한 단어라고 합니다.

 


메모이제이션(Memoization)을 이용한 피보나치(Fibonacci)수열의 구현

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Memoization_Fibonacci {
 
    static long[] memo;
    public static long fibonacci(int n) {
        if (n <= 1)
            return n;
        else if (memo[n] != 0)
            return memo[n];
        else
            return memo[n] = fibonacci(n - 1+ fibonacci(n - 2);
 
    }
    
    public static void main(String[] args) {
        memo = new long[101];
        System.out.println(fibonacci(100));
    }
}
cs

 

결과값

 

기존 재귀함수를 사용했을 때와는 달리 이미 계산된 값을 Memo라는 배열에 저장을 합니다.

fib(5) = fib(4) + fib(3)..

fib(4) = fib(3) + fib(2)..

즉 fib(5)를 구하기 위해서도 fib(3)이 겹치고, fib(4)를 구하기 위해서도 fib(3)이 겹칩니다.

이러한 중복된 부분을 미리 계산을 통하여 값을 저장하여 필요시마다 값을 불러오기만 하면 되는 것입니다.

 

즉 위와같이 딱 한번의 계산으로 불필요한 중복을 제거할 수 있는 것입니다.

메모이제이션을 추가한 방법의 시간 복잡도는 O(N) 입니다.

이러한 방식을 Top - Down 방식이라고 합니다.

 


이러한 동적 프로그래밍은 프로그램의 메모리 관리 및 속도 개선에 큰 장점이 있습니다.

 

동적프로그래밍의 구현 방법에는 Bottom-up( 작은문제부터 풀어 큰문제를 찾는 방법 ) 그리고 Top-down ( 큰 문제로부터 작은문제로 내려오면서 해결하는 방법 ) 이 있는데 추후 포스팅 하도록 하겠습니다.

 

또한 동적계획법(DP) 알고리즘은 최적값을 구할 때 주로 사용합니다.

그렇기에 중요하게 알아둬야 할 알고리즘 중에 하나입니다.

 

동적프로그래밍의 설명은 사실 한 포스팅으로 끝내기 상당히 어렵습니다.

이 한가지만으로 파생되는 여러가지들이 있기 때문입니다.

( ex . 메모이제이션과 비슷한 타뷸레이션(Tabulation), 다양한 DP문제들(막대기,배낭,최장 공통 부분 수열 (LCS) 등등...) )

다양한 문제들은 다른 카테고리(JAVA-Eclipse)에서 다루도록 해보겠습니다.

 

꼭 한번쯤 동적계획법에 대한 자세한 내용을 검색해보시고 , 공부해보시길 추천합니다.

이상 간단한 제 생각과 설명의 포스팅이였습니다.

댓글
공지사항
글 보관함
최근에 올라온 글
최근에 달린 댓글