[C++] 계단 오르기 알고리즘

예로 들어서 n이 3이라면 꼭대기에 도달 하는데까지 총 3가지의 방법이 존재한다.

 

다른 예시로는

n = 1
// 한 가지의 방법만 존재하므로 1을 출력

n = 2
// 2, (1 , 1)과 (2)

n = 4
// 5, (1, 1, 1, 1), (1, 1, 2), (2, 1, 1), (1, 2, 1), (2, 2)

재귀를 사용한 방식

방법의 수(n) = 방법의 수(n - 1) + 방법의 수(n - 2)

 

피보나치 수열을 이용하여 구할 수가 있다.

방법의 수(1) = 피보나치(2) = 1
방법의 수(2) = 피보나치(3) = 2
방법의 수(3) = 피보나치(4) = 3

int fib(int n)
{
    if (n <= 1)
        return n;
    return fib(n - 1) + fib(n - 2);
}

int countWays(int s) { return fib(s + 1); }

int main()
{
    int s = 4;
    cout << "Number of ways = " << countWays(s);
    return 0;
}

시간 / 공간 복잡도

시간) O(2 n제곱)  2개의 선택지가 주어졌고 n개의 계단 수

공간) O(n) 재귀 스택메모리 공간이 필요

DP (메모이제이션 / 업다운) - 시간 / 공간 복잡도 O(n)

1. 목표지점 n에 도달할 수 있는 방법인 1차원 배열인 dp[i]를 생성한다.
2. 이전에 값을 구했는지 확인한다.
3. 재귀해서 이전 값들의 결과를 저장한다.  예) dp[n] = 방법의 수(n - 1, dp) + 방법의 수(n - 2, dp)
4. 결과는 dp[n]이다.

int countWays(int n, int dp[])
{
    if (n <= 1)
        return dp[n] = 1;
 
    if (dp[n] != -1) {
        return dp[n];
    }
    dp[n] = countWays(n - 1, dp) + countWays(n - 2, dp);
    return dp[n];
}

int main()
{
    int n = 4;
    int dp[n + 1];
    memset(dp, -1, sizeof dp);
    cout << "Number of ways = " << countWays(n, dp);
    return 0;
}

DP (바텀업) - 시간 / 공간 복잡도 O(n)

다음과 같은 관계로 dp를 생선한다

dp[i] = dp[i-1] + dp[i-2]

1. 1차원 배열 (dp)을 생성한다.
2. 2는 2가지의 방법이 존재하므로 dp[0]이랑 dp[1]을 1로 초기화한다.

// C++ program to count number of ways
// to reach n'th stair when a person
// can climb 1, 2, ..m stairs at a time
#include <iostream>
using namespace std;
// A function to find number of ways to reach the nth stair
int countWays(int n)
{
	vector<int> dp(n + 1);
	dp[0] = dp[1] = 1;

	for (int i = 2; i <= n; i++)
		dp[i] = dp[i - 1] + dp[i - 2];
	return dp[n];
}

// Driver code
int main()
{
	int n = 4;
	cout << "Number of ways = " << countWays(n);
	return 0;
}

 

 

Climbing Stairs to reach at the top. - GeeksforGeeks