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