반응형
피보나치 수열을 이용한 재귀 프로그래밍은 대학교 1학년때 처음 재귀를 구하면서 접했었다.
당시에는 재귀의 예제로써 피보나치와 팩토리얼함수를 구현하는 것으로 소개되었다.
하지만 시간복잡도에 대해 다시 공부하던 중 우리가 배웠던 피보나치 수열의 재귀는 좋은 방식이 아니라는 것을 알게되었다.
피보나치 수열의 3가지 방식에 대해 구현해보고 차이를 느껴보자.
우선 피보나치 수열은 현재 값을 구하기위해서는 이전의 값(n-1)과 그 더 이전의 값(n-2)을 더하면서 구한다.
N = (n - 2) + (n -1)
0, 1, 1, 2, 3, 5, 8, 13, 21, 34........
1) 재귀방식
재귀로 구현하는 방식은 가장 익숙한 방법이지만 매번 구할 때 마다 처음까지 가야하는 가장 안좋은 BigO(2^n)의 시간 복잡도를 가지게 된다.
1 2 3 4 5 6 7 8 9 10 11 12 13 | /** * 재귀를 사용한 피보나치 수열 * * @param i * @return */ private static int recurSiveFibo(int i) { if (i <= 1) { return i; } else { return recurSiveFibo(i - 2) + recurSiveFibo(i - 1); } } | cs |
2) Dynamic Programming
이전에 구해놓은 값을 이용하여 값을 구하는 방식인 DP 알고리즘을 구하면 BigO(n)의 시간 복잡도를 가지게 된다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | /** * DP 배열 생성 * * @param i * @return */ private static int getDpFibo(int fiboCnt) { fiboDpArray = new int[fiboCnt + 1]; fiboDpArray[0] = 0; fiboDpArray[1] = 1; if (fiboCnt > 1) { for (int i = 2; i <= fiboCnt; i++) { fiboDpArray[i] = fiboDpArray[i - 2] + fiboDpArray[i - 1]; } } return fiboDpArray[fiboCnt]; } | cs |
3) 반복문
반복문을 통해서 값을 구할 때도 동일하게 BigO(n)의 시간 복잡도를 가지게 된다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 | /** * @param fiboCnt * @return */ private static int getLoopFibo(int fiboCnt) { if (fiboCnt <= 1) { return 1; } else { int a = 0; int b = 1; int sum = 0; for (int i = 2; i <= fiboCnt; i++) { sum = a + b; a = b; b = sum; } return sum; } } | cs |
무턱대고 재귀함수를 사용하면 안되지만, 재귀함수가 그렇다고 어떤경우에도 다 안 좋은것은 아니다.
상황에 따라 시간복잡도를 잘 고려해서 사용하면 좋은 재귀를 쓸 수있을 것 같다.
반응형
'JAVA > 알고리즘' 카테고리의 다른 글
백준 6603번 로또 문제 풀이 (0) | 2018.07.15 |
---|---|
백준 알고리즘 10988번 문제 팰린드롬 문제 풀기 (0) | 2018.07.09 |
백준 알고리즘 2167 2차원 배열의 합 DP 알고리즘으로 풀기 (JAVA) (1) | 2018.07.08 |
정렬알고리즘 - 버블정렬 (0) | 2018.05.28 |
정렬알고리즘 - 삽입정렬 (0) | 2018.05.28 |