계단 오르기

N(> 0)개의 계단을 한 번에 하나 혹은 둘씩 올라갈 수 있다. N개의 계단을 올라가는 방법의 수를 구하려고 한다.

 

1. 1개의 계단을 올라가는 방법은 몇 가지인가?

- 1가지

2. 2개의 계단을 올라가는 방법은 몇 가지인가?

- 2가지

3. 3개의 계단을 올라가는 방법은 몇 가지인가?

- 3가지

4. N(> 0)개의 계단을 올라가는 방법의 수에 대한 점화식을 작성하라.

- N이 1일 때, F(N) = 1

- N이 2일 때, F(N) = 2

- Otherwise, F(N) = F(N-1) + F(N-2) //피보나치

 

5. 4번의 점화식을 사용하여 N(> 0)개의 계단을 올라가는 방법의 수를 구하는 재귀 알고리즘을 작성하라.

- 알고리즘 countStair(N)

// 입력값 : N(0보다 큰 자연수)

// 반환값 : N개의 계단을 하나 혹은 둘 씩 올라가는 방법의 수

If(N<=2) return N

Else return countStair(N-2) + countStair(N-1)

 

<코드> 

재귀 알고리즘을 사용.

 

재귀가 아닌 반복을 이용한 방법