-
질문 & 답변
카테고리
-
세부 분야
알고리즘 · 자료구조
-
해결 여부
미해결
수열 추측하기 질문
21.08.26 22:47 작성 조회수 110
0
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
import sys
sys.stdin = open('input.txt','rt')
def DFS(L,sum):
if L == n:
for i in range(n):
print(res[i],end=' ')
print()
print(sum)
else:
for i in range(1,n+1):
if ch[i] == 0:
ch[i] = 1
res[L] = i
sum += res[L]*b[L]
DFS(L+1,sum)
ch[i] = 0
n,f = map(int,input().split())
ch = [0]*(n+1)
res = [0]*(n)
b=[1]*n #이항계수 적을곳 121 1331 14641 ...
for i in range(1,n):
b[i] = b[i-1]*(n-i)//i
DFS(0,0)
|
cs |
안녕하세요 강사님
수열 추측하기 부분에서 강의에서 sum의 변화를 DFS(L+1, sum + (res[L]*b[L]))의 형태로 쓰였는데 이를 위의 코드의 형광팬 쳐진 부분처럼 따로 때어서 결과를 진행하면 sum값이 달라지는 것을 확인할 수 있었습니다.
하지만 제가 생각해봤을때 똑같은 코드라고 생각했는데 sum값이 달라지는 이유가 어떠한 원리인지 알수가 없어서 질문드립니다.
답변 부탁드리겠습니다
답변을 작성해보세요.
0
김태원
지식공유자2021.08.27
안녕하세요^^
DFS(L+1, sum + (res[L]*b[L]))
위에 코드로 짜면 재귀함수 안의 for문이 반복해도 sum은 함수 헤더부분의 매개변수 def DFS(L,sum): 에서 받았던 값을 그대로 유지합니다.
하지만 님처럼
sum += res[L]*b[L]
DFS(L+1,sum)
이렇게 하면 재귀함수 안 for문이 반복할 때 sum값이 자꾸 변합니다.
연필로 스택그리시고, 상태트리그림 그려가면서 진행해보세요. 특히 순열이 하나 완성되고 뒤로 백을 하고 for문이 반복해서 다른 순열을 하나 다시 만들때 sum값이 어떻게 되는지 확인해보세요.
답변 1