인프런 커뮤니티 질문&답변
작성한 질문수
climbing stairs를 top-down 방식으로 풀면 시간초과가 뜹니다
해결된 질문
작성
·
198
1
tabulation 방식의 Bottom-up은 재귀를 호출하지 않기 때문에 당연히 테케 통과하구요
강의를 들었을때도 강사님은 피보나치 코드 그대로 사용하셔서 저도 그대로 제출했는데 시간 초과가 뜹니다... 원래의 코드는 아래와 같구요
def climbStairs(self, n):
memo = {}
if n == 1 or n == 2:
return n
if n not in memo:
memo[n] = self.climbStairs(n-1) + self.climbStairs(n-2)
return memo[n]discuss를 참고해서 수정한 코드는 테케를 통과했는데 아래와 같습니다
class Solution(object):
def climbStairs(self, n):
memo = {}
return self.dp(n, memo)
def dp(self, n, memo):
# base cases
if n == 1 or n == 2:
return n
if n in memo:
return memo[n]
memo[n] = self.dp(n-1, memo) + self.dp(n-2, memo)
return memo[n]제가 봤을 때는 두 코드의 로직에 대한 차이점은 없어보입니다만 왜 아래의 코드는 시간초과가 나지 않는거죠??
답변 1
0
개발남노씨
지식공유자
안녕하세요 Ambition님.
두 코드의 차이는 memo = {}가 함수 내부에 있냐 외부에 있냐 차이에요.
def climbStairs(self, n):
memo = {}
if n == 1 or n == 2:
return n
if n not in memo:
memo[n] = self.climbStairs(n-1) + self.climbStairs(n-2)
return memo[n]
이 코드에서 매번 climbStairs()를 호출할 때마다 새로운 memo를 선언하기 떄문에 기존에 저장된걸 유지하지 못하고 비어있는 새로운 memo를 선언하게 되는거죠.
그래서 해당 코드로 진행하려면 아래와 같이 작성하면 괜찮을 것 같습니다.
class Solution(object):
def climbStairs(self, n):
memo = {}
def dp(n):
if n == 1 or n == 2:
return n
if n not in memo:
memo[n] = self.climbStairs(n-1) + self.climbStairs(n-2)
return memo[n]
return dp(n)
한번 보시고 이해안되시면 다시 질문 주세요 :)
개발남노씨
지식공유자
앗 제가 코드를 틀려서 드렸네요
class Solution(object):
def climbStairs(self, n):
memo = {}
def dp(n):
if n == 1 or n == 2:
return n
if n not in memo:
memo[n] = dp(n-1) + dp(n-2)
return memo[n]
return dp(n)이렇게 구현하면 돌아갈거에요!!
Ambition님이 적어주신대로 dp를 따로 떼어내도 되고, 이렇게 중첩함수를 선언해서 실행해도됩니다.
음... 강사님이 아래에 작성해주신 코드로 실행했을때도 시간초과가 났습니다 ㅠㅠ 디버깅해보니까 self.climbStairs(n-1) 부분을 호출하면 memo가 반복적으로 초기화가 되더군요
강사님께서 제시해주신 핵심 아이디어는 memo를 전역변수에 놓아서 중복되는 함수를 호출하는 것을 방지하는 것이라는 것과 discussion을 참고해서 climbStairs는 입력값을 받고 memo를 전역변수로 설정하는 역할을 하고, dp함수는 기존의 피보나치 수열을 다이나믹 프로그래밍 버전으로 업그레이드해서 문제를 해결하는 역할로 분리하였습니다.
아! 그리고 추가적인 파이썬 지식이 필요했는데요, self는 Solution이라는 동일한 클래스 레벨에서의 인스턴스를 의미해서 climbStairs와 dp의 함수 depth는 동일하게 두어야 했었습니다.
지금에야와서 이해는 된 것 같지만, 여러 번 반복해서 풀어봐야 할 것 같습니다 ..