💡 계단을 오르는 방법은 한 계단을 오르거나 두 계단을 오르는 두 가지 방법이 존재합니다.
2.2. 계단을 오르는 방법 연산식
💡 계단을 오르는 방식은 마지막에 한 계단을 오르는 경우와 마지막에 두 계단을 오르는 경우가 있습니다.
해당 연산은 마지막에 한 계단을 오르는 경우(n-1)의 경우가 되고 마지막에 두 계단을 오르는 경우 (n-2)의 경우가 됩니다.
그래서 피보나치의 수열은 [1, 1, 2, 3, 5, 8, 13, 21, 34,...]인데 계단을 오르는 경우의 수는 처음 두 항이 1, 2 인 피보나치 수열이 되므로 계단을 오르는 경우는 F(n+1)이 됩니다.
2) Java에서 피보나치 수열을 이용한 구현
💡 N개의 계단을 올라갈 때, 한 번에 1 계단 또는 2 계단 씩 오를 수 있다면, 몇 가지 방법으로 올라갈 수 있는지 계산할 수 있습니다.
💡 아래에서는 반복문, 재귀함수, 동적계획법을 이용하여 피보나치 수열 알고리즘을 구현하며 경우의 수를 계산하는 방법에 대해서 확인합니다.
구현 방식
장점
단점
반복문
코드가 간결하고 직관적이다
피보나치 수열 이외의 문제에 대한 확장성이 낮다
재귀함수
구현이 쉽고 이해하기 쉽다
시간 복잡도가 높아 큰 수를 계산하기 어렵다
동적 계획법
이미 계산한 값을 활용하여 계산 시간을 줄일 수 있다
메모리 사용량이 높아질 수 있다
1. 반복문을 이용한 구현 방식
💡 해당 방법은 N개의 계단에 대해서 배열의 사이즈로 지정하고 반복문을 순회하면서 경우의 수를 확인하는 방법입니다.
1. 값이 1인 경우는 즉시 값을 반환하고 종료합니다. 2. 계단을 오르는 방법에는 한 계단과 두 계단 방법으로 첫 번째와 두 번째 배열에 값을 지정합니다. 3. 3번째 요소부터 배열을 순회하면서 이전 계단을 오르는 방법의 수를 더하여 계산을 합니다.
💡 4개의 계단을 오르는 경우 5가지의 경우의 수를 반환합니다.
public class FibonacciStairs {
/**
* 피보나치수를 이용한 경우의 수 계산방법 : 반복문을 이용한 방법
*
* @param n
* @return
*/
public static int calcLoopFibonacci(int n) {
int answer = 0;
// [CASE1] 값이 1인 경우 해당 값을 반환합니다.
if (n <= 1) return n;
// [STEP2] 계단을 오르는 방법에는 한 계단과 두 계단 방법으로 첫번째와 두번째 값을 지정합니다.
int prevPrev = 1;
int prev = 2;
// [STEP3] 3번째 요소부터 배열을 순회하면서 이전 계단을 오르는 방법의 수를 더하여 계산을 합니다.
for (int i = 3; i <= n; i++) {
answer = prev + prevPrev;
prevPrev = prev;
prev = answer;
}
return answer;
}
public static void main(String[] args) {
int n = 4;
System.out.println("계단을 오르는 방식 : " + calcLoopFibonacci(n)); // 계단을 오르는 방식 : 5
}
}
2. 재귀함수를 이용한 구현 방식
💡 해당 방법은 N개의 계단에 대해서 재귀 함수를 이용하여 경우의 수를 확인하는 방법입니다.
1. 해당 방식은 자기 자신을 호출하는 함수를 호출하여 계산을 하여 반환을 하는 방식입니다.
- 재귀 알고리즘으로 구현하는 경우는, 불필요하게 같은 값을 다시 계산하게 되어 계산 속도가 엄청 느리다는 단점이 있습니다. - 이를 위해 실제로 구현할 때는 한 번 계산한 값을 저장해 두고 재 계산하지 않는 메모라이제이션 기법을 사용하여 구현해야 합니다.
💡 4개의 계단을 오르는 경우 5가지의 경우의 수를 반환합니다.
public class FibonacciStairs {
/**
* 피보나치수를 이용한 경우의 수 계산방법 : 재귀함수를 이용한 방법
* @param n
* @return
*/
public static int calcRecursiveFibonacci(int n) {
if (n <= 1) {
return n;
} else {
return calcRecursiveFibonacci(n - 1) + calcRecursiveFibonacci(n - 2);
}
}
public static void main(String[] args) {
int n = 4;
System.out.println("계단을 오르는 방식 : " + calcRecursiveFibonacci(n + 1)); // 계단을 오르는 방식 : 5
}
}
[ 더 알아보기 ]
💡 재귀함수(Recursive Function)란?
- 자기 자신을 호출하는 함수입니다. 이는 함수 내부에서 동일한 함수를 호출하여 반복적으로 실행되는 함수입니다.
- 재귀함수는 일반적으로 두 가지 주요 요소가 있습니다. 첫째, 재귀함수는 기본 케이스(base case)와 재귀 케이스(recursive case)로 구성됩니다. 둘째, 재귀함수는 스택 메모리를 사용하며, 스택 메모리는 모든 함수 호출의 복사본(로컬 변수 등)을 저장하는 데 사용됩니다. - 재귀함수를 작성할 때, 재귀 케이스가 한 번은 기본 케이스로 수렴해야 합니다. 그렇지 않으면 무한 루프가 발생할 수 있습니다.
💡 메모이제이션(Memoization) 이란?
- 메모이제이션은 계산한 결과를 저장해 놓고, 동일한 입력 값이 나타날 때마다 저장된 결과를 반환하는 방식입니다.
3. 동적 계획법을 활용하여 구현 방식
💡 해당 방법은 N개의 계단에 대해서 동적 계획법을 활용하여 경우의 수를 확인하는 방법입니다.
1. 값이 1인 경우는 즉시 값을 반환하고 종료합니다. 2. 계단을 오르는 방법에는 한 계단과 두 계단 방법으로 첫번째와 두번째 배열에 값을 지정합니다. 3. 3번째 요소부터 배열을 순회하면서 이전 계단을 오르는 방법의 수를 더하여 계산을 합니다.
4개의 계단을 오르는 경우 5가지의 경우의 수를 반환합니다.
public class FibonacciStairs {
/**
* 피보나치수를 이용한 경우의 수 계산방법 : 동적 계획법을 이용한 방법
*
* @param n
* @return
*/
public static int calcDynamicFibonacci(int n) {
// [STEP1] 계단이 1개일 경우 값을 즉시 1로 리턴합니다.
if (n <= 1) {
return n;
}
// [STEP2] 계단을 오르는 방법에는 한 계단과 두 계단 방법으로 첫번째와 두번째 배열에 값을 지정합니다.
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
// [STEP3] 3번째 요소부터 배열을 순회하면서 이전 계단을 오르는 방법의 수를 더하여 계산을 합니다.
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
public static void main(String[] args) {
int n = 4;
System.out.println("계단을 오르는 방식 : " + calcDynamicFibonacci(n)); // 계단을 오르는 방식 : 5
}
}
[ 더 알아보기 ]
💡 동적 계획법(Dynamic Programming)이란?
- 복잡한 문제를 간단한 하위 문제로 나누어 푸는 방법입니다. 이전에 계산한 값을 저장하고 재활용함으로써 중복 계산을 줄이는 특징이 있습니다. 이 방법은 피보나치 수열 계산뿐만 아니라, 최단 경로, 최장 공통부분 문자열 등 다양한 분야에서 사용됩니다.
💡동적 계획법과 반복문의 차이는 무엇인가?
- 동적 계획법은 이전에 계산한 값을 저장해 두고 필요할 때마다 불러와서 사용한다는 점이 반복문과 차이가 있습니다. 동적 계획법은 계산 시간을 줄일 수 있습니다. 하지만 반복문이 동적 계획법보다 코드가 간결하고 직관적이라는 장점이 있습니다.
