2015112119   5년 전

아무래도 dfs로 하니 시간초과가 뜨네요 혹시 다른 방법으로 풀어야 하는 건가요?

아니면 이 방법으로 할 문제를 풀 다른 방법이 있을까요?

dyk777   5년 전

예를 들어, n=5라면

dfs(5)는 dfs(2),dfs(3),dfs(4)를 호출합니다.

그런데 dfs(2)는 dfs(3),dfs(4)에서도 호출됩니다.

즉, 이미 한번 이상 수행되어 필요 없는 연산이 너무 많이 수행된다는 뜻입니다.

zxwnstn   5년 전

N이 1000000까지인데 저런식의 재귀형태라면 시간초과가 안나더라도 스택오버플로어(메모리초과)가 날 가능성이 매우 큽니다.

일반적으로 dp문제는 전부 재귀로 풀 수 있는것으로 알고 있습니다만, 가급적 memoization으로 푸는것이 더 좋습니다.

입력이 커지면 스택오버플로어의 가능성이 너무 커지기 때문이지요..


댓글을 작성하려면 로그인해야 합니다.