728x90 반응형 dfs4 재귀함수와 스택(Stack) 재귀함수 : 자기자신을 호출하는 함수 이때 stack 이라는 자료 구조를 사용하여 작동한다. 재귀함수는 for문 즉 반복문의 대체자이다. n 입력값을 3으로 가정하고 설명을 해보겠습니다. 12 줄: 입력값 n 즉, 3 을 받음. 13 줄: DFS(3): DFS함수를 호출하여 3을 넘김. 4 줄: 함수 DFS (3) if 문 실행 5 줄: 만약 x 가 0보다 크다면 실행. 0이거나 작으면 종료 6 줄: x 출력 -> 3이 출력됨. 7줄 ; DFS 함수 호출 [이 부분이 재귀함수이다. 왜냐하면 자기자신의 함수를 호출하기 떄문에 ] DFS(3-1) 로 DFS(2)가 되며 함수 DFS를 호출함 다시 4번줄로 올라가서 def DFS(2): 가 되면서 5번줄: if 2> 0 : 가 실행되고 참이므로 6번줄: pri.. 2022. 10. 9. 바둑이 승차(DFS) n 을 5를 입력받았다고 가정. c 는 259를 입력받았다고 가정. 리스트 a에 입력받을 수는 81 , 58, 42, 33, 61 로 가정하겠습니다. 여기서 L은 리스트a 의 인덱스번호를 의미합니다. sum 은 부분집합의 합을 의미합니다. total 은 리스트 a의 모든 값. result 는 제한 무게를 충족하는 우리가 출력하고자 하는 결과값. 25번줄: DFS 함수 호출 result 변수를 전역 변수로 지정하고 만약 sum + (total 에서 tsum을 뺀값)이 result 보다 작다면 return 시킴. 20줄에서 result 값을 -2147000000으로 할당했기 때문에 return 보다 작기 힘들다. 8번줄 만약 더한값(sum)이 무게제한(c) 보다 크다면 return 해서 종료시켜버린다. c보.. 2022. 10. 8. 합이 같은 부분집합(DFS) 18줄 : a 변수에다 n개의 원소를 입력받은 값을 저장한다. 19줄 : total 변수에 a리스트의 모두 더한 값을 저장한다. 20줄: DFS 함수호출! 2022. 10. 7. DFS 문제 1. 변수 n 에 외부로부터 입력받은 값을 저장합니다. 2. ch 라는 리스트를 만들어 줍니다. 값이 0 으로 해서 n+1 크기로 만들어줍니다. v = 1 3. DFS(1) 는 4번줄에 함수 DFS 의 v값에 1을 넣어 실행시킵니다. 4번줄 : 함수 DFS 에 1이 들어가면, n(여기서 n을 3으로 가정한다) +1 의 값은 4이다. 5번줄 : v가 n+1 와 같다면 바로 아래 for문을 실행시킨다. 현재 v에는 1이 들어있기 때문에 1 !=4 이므로 10번줄 else가 실행이 된다. 11번줄: ch[1] =1 이므로 , 이렇게 된다. v = 2 12번줄 : DFS(v+1) 에는 DFS(2)가 될것이고, DFS(2)는 4번줄에 있는 함수 DFS 에 이번에는 1이아닌 2를 넣어서 실행시켜준다. 5번줄 : i.. 2022. 10. 6. 이전 1 다음 728x90 반응형
