• 카테고리

    질문 & 답변
  • 세부 분야

    알고리즘 · 자료구조

  • 해결 여부

    미해결

return

20.12.16 19:29 작성 조회수 109

0

L은 dfs를 진행할수록 증가하기 때문에 만약 L에서 sum이 m인 부분을 찾았으면 더 진행할 필요없이 L이 최소라고 생각해서 dfs함수에서

    if L>=res:
        return

을 생략하고

def DFS(L, sum):
    global res
    
    if sum>m:
        return
    if sum==m:
        if L<res:
            res=L
            return #
    else:
        for i in range(n):
            DFS(L+1, sum+a[i])

sum이 m을 되자마자 return 하는게 나을거라 생각했는데 제 생각과는 달리 더 오래걸리더라구요. 왜 그런지 이유를 모르겠어요.

답변 2

·

답변을 작성해보세요.

0

jhj13062004님의 프로필

jhj13062004

2021.03.27

위와 같을 경우 return이 아니라 아예 exit으로 종료시키면 되나요?

안녕하세요^^

exit는 답을 찾았을 때 답을 출력하고 프로그램을 종료하는 논리입니다. 이 문제는 exit를 쓰는 문제가 아니라 가지치기를 잘 해야하는 문제입니다. 그리고 어떤 회사는 테스트에서 exit를 막아놓는 회사도 있습니다. 

0

안녕하세요^^

sum이 m이 되자마다 return 한다고 해서 호출되어 스택에 저장되어 있는 모든 함수가 종료되는 것은 아닙니다. 방금전 호출된 함수만 종료되는 것입니다.