Staircase Problem

개요

 

코딩 인터뷰 문제이다.

정리를 통해 확실히 이해하고, 이를 Golang 으로 구현해본다.

 

참고 링크: https://www.geeksforgeeks.org/count-ways-reach-nth-stair/

참고 유튜브: https://youtu.be/5o-kdjv7FD0

 

문제 정의

 

1) N 개의 계단을 1칸, 혹은 2칸 단위로 오를 수 있다고 할 때에 오를 수 있는 방법의 개수는 몇 개인가?

< 이미지 출처: https://www.geeksforgeeks.org/count-ways-reach-nth-stair/ >

예를 들어 N = 4개의 계단이라면 5개의 방법이 있다.   1) {1, 1, 1, 1} 2) {2, 1, 1}, {1, 2, 1}, {1, 1, 2} 3) {2, 2}

 

2) 좀더 일반화 하여 N 개의 계단을 특정 단위들 (의 집합인 x} 로 오를 수 있는 방법의 개수는?

- 예를 들어 10 개의 계단을 1, 3, 5 계단씩 오를 수 있다고 할때에 문제의 정의는

- N = 10, x = [1, 3, 5] 가 되겠다.

 

 

문제에 대한 접근

 

4 개의 계단을 1칸, 2칸 단위로 오를 수 있다고 할 때에, 모두 다 올랐을때 부터 역으로 생각해보자.

 

1) 4번째 계단을 오르려면, 1칸 또는 2칸 아래계단에서 올랐을 것이다. 2-1) 1칸 아래의 계단까지 오는 데에도 또 다시 거기서 1칸 또는 2칸 아래 계단에서 올랐을 것이다. 2-2) 2칸 아래의 계단까지 오는 데에도 또 다시 거기서 1칸 또는 2칸 아래 계단에서 올랐을 것이다. → 이건 재귀적 호출로 구현할 수 있다! 3) 만약 1칸 또는 2칸 아래의 계단이 땅바닥 이라면 (N = 0) 맨 위에서 맨 아래까지 하나의  방법이 완성된 것이다. 그러므로 1을 리턴해주면 된다.

 

개인적 Golang 구현은 GitHub 에 올려두었다.

- https://github.com/nicewook/staircase_problem

 

	재귀적 접근   1) totalSteps 가 0 이라는 건 땅바닥에 도착했다는 것이다. - 위에 언급한 방식대로라면, 하나의 경로가 확인되었다는 것 - 따라서 1을 리턴해준다   2) 현재의 위치 = totalSteps 에 올라올 수 있는 이전 step의 위치를 계산해본다. - 이전 step 의 위치는 stepsLeft 이다. (1) 만약 마이너스 값이라면 가능하지 않다는 말이므로 continue (2) 만약 0 이라면 땅바닥이라는 말이므로 하나의 경로 확인됨. 1 추가 (3) 양수 값이라면 재귀적으로 호출해준다.   3) 가능한 모든 경우를 다 더해주어 리턴해주면 된다.
	Memoize   Dynamic Programming 으로 풀어본 것이다. 재귀적인 해법의 단점은 같은 계산을 반복한다는 것인데 이걸 일종의 전역변수에 넣어버려서, 필요할때에 계산없이 꺼내쓰는 것이다.   Memorize != Memoize 에 주의
	Bottom up   이건 Memoize 의 변주라 할 수 있으며, 상대적인 장점은 재귀적인 호출이 없다는 것이다.

 

테스트 결과

 

1) 모두 테스트를 통과하였음

2) BottomUp 방식이 가장 빠르다.

 

참고. golang uint 문제

 

Test 를 계산 수 100, 한 번에 오르는 스텝의 종류를 1, 3, 5, 7, 9 로 하였었는데

코드상에 uint 로 구현하였더니 그 결과가

하지만 uint 는 현재 사용하는 Window PC 가 64bit 이므로 uint64 를 의미했으며 이 경우의 최대값은 18446744073709551615 이었음

 

실제의 정답: 250,575,442,669,757,757,682

코드 계산값:  10,767,769,711,533,586,674

 

Overflow 가 일어난 것이다.

250,575,442,669,757,757,682 - (18,446,744,073,709,551,616 * 13) =  10,767,769,711,533,586,674

→ 아무튼 이 부분에 대하여 위 코드 예제를 수정하였음. (2019-05-31)

 

Python 구현 (권경모님 코드)

 

- Python 의 경우 bigInteger 에 대해 자동으로 대응해주는 것으로 보인다.