Recursion: Davis' Staircase

문제

 

순수하게 짜려고하면 대략 3중 for문이 나온다.

딱히 그래프 데이터도없고 좌우로 이동하는 내용도 없으니 DFS, BFS는 아닌듯 하다.

이럴땐 수학적으로 접근해 작은 단위부터 규칙을 찾는수밖에...

 

 

다이나믹 프로그래밍(Dynamic Programming):

• 목적: 최적 부분 구조를 갖춘 문제를 해결하기 위한 기법으로, 작은 부분 문제들의 해를 저장하고 활용하여 전체 문제의 해를 효율적으로 계산하는 것이 목적입니다.
• 작동 방식: 문제를 작은 부분 문제들로 나누고, 각 부분 문제에 대한 해를 계산하여 메모이제이션(기억화)하며, 이를 조합하여 전체 문제에 대한 해를 구합니다. Bottom-up 방식과 Top-down 방식이 있습니다.

 

풀이

# n=1
# 1

# n=2
# 11
# 2

# n=3
# 111
# 12
# 21
# 3

def stepPerms(n):
    if n <= 2:
       return n
    if n == 3:
        return 4
    return stepPerms(n-1) + stepPerms(n-2) + stepPerms(n-3)

 

에엣? Time limit exceeded 가 발생했다.

 

문제에서 주어진 stepPerms 함수는 재귀적으로 계단을 오르는 방법의 수를 찾는 방법으로 작성되어 있습니다. 그러나 이 함수는 중복 계산을 많이 수행하므로 큰 입력에 대해서는 시간 초과가 발생할 수 있습니다. 이를 해결하기 위해서는 다이나믹 프로그래밍(Dynamic Programming)의 메모이제이션(Memoization) 기법을 사용하여 중복 계산을 피해야 합니다. 아래는 메모이제이션을 적용한 코드입니다:

 

memo = {}

def stepPerms(n):
    if n <= 2:
       return n
    elif n == 3:
        return 4
    if n not in memo:
        memo[n] = stepPerms(n-1) + stepPerms(n-2) + stepPerms(n-3)

    return memo[n]

 

완성!