Part5.5_완전탐색_부분집합 구하기(DFS)__바둑이 승차__전역변수,지역변수
내가 생각한 코드
import sys
#sys.stdin = open("input.txt", "rt")
def DFS(idx, sum): # L은 인덱스 번호이다. 0번 인덱스는 사용하겠다 >> sum에 인덱스0값 더한다 // 0번 인덱스는 사용하지않겠다 >> sum 유지
if sum > C:
return
if idx == N:
res.append(sum)
if sum==0:
print(max(res))
return
else:
DFS(idx+1, sum+a[idx])
DFS(idx+1, sum)
#if __name__ == "__main__":
C, N = map(int, input().split())
a = []
res = []
for _ in range(N):
tmp = int(input())
a.append(tmp)
a.sort
DFS(0,0)
내가 생각해도 리스트 하나 더 만들어서 append하는 건 비효율 적인데..
time limit 났다..
전역변수와 지역변수
if name == "main ":
이 아래 선언한 변수는 전역변수로,
어떤 함수에서든 접근 가능하다 !!
if name == "main ":
cnt = 5 #전역변수 생성과 값 할당, 기본적으로 어디서나 접근 가능.
DFS1()
DFS2()
print(cnt)해답 : 5
def DFS1()
print(cnt) # 먼저 지역변수인지 확인하고 작동하는 구조이다. 이후 전역변수 인지 확인한다.해답 : 5
def DFS2()
if cnt==5 # 먼저 지역변수인지 확인하고 작동하는 구조이다. 이후 전역변수 인지 확인한다. 함수는 local 변수가 우선이다.
print(cnt)해답 : 5
**그런데 !! 만약 여기서 전역변수 값을 바꾸려고 한다면?
def DFS2()
if cnt==5: # 먼저 지역변수인지 확인하고 작동하는 구조이다. 이후 전역변수 인지 확인한다. 함수는 local 변수가 우선이다.cnt 는 지역변수가 되었고, 초기화된 cnt라는 지역변수 값 자체가 없으므로 오류난다...
cnt==cnt+1 # 새로운 지역변수를 만들게 되는 뜻이다. 따라서 ↑↑↑↑
print(cnt)해답 : 5
list 같은 경우에는
def DFS():
a=[7,8] # 이렇게 하면 local 로 선언되는거다. 근데 만약, 오류가 나는 경우는 a=a+[4] // 리스트 끼리 더해서 로컬 리스트로 만들겠다 ? >> 이건 안된다. >> 만약 그렇게 하고 싶다면 global a 라고 로컬화 선언해 주어라 !!!
print(a)
,,,
if name == "main ":
a=[1,2,3]
DFS()
print(a)위 print 해답 : [7,8] 지역변수가 되었으므로
아래 print 해답 : [1, 2, 3] 전역변수가 되었으므로
그렇다면 전역변수 사용하는 법? :global !!
변수 앞에 global 을 붙여주면 된다 !!!!!!!!!!!!
그래서 리스트 대신 변수로 바꿨으나..
여전히 시간 리밋 난다...
어떻게 하나요 선생님 ??
선생님 코드
타임 limit 까지 해결 방법.. 내가 한 방법에서 시간 복잡도 해결한 부분만 봐라 !!
import sys
sys.stdin = open("input.txt", "rt")
def DFS(L, sum, tsum): # L은 인덱스 번호이다. 0번 인덱스는 사용하겠다 >> sum에 인덱스0값 더한다 // 0번 인덱스는 사용하지않겠다 >> sum 유지
global result # 로컬 변수화!!
# 시간 복잡도 줄이는 방법 ???
if sum + (total-tsum) < result:
return
if sum > c:
return
if L == n:
if result < sum:
result = sum
else:
DFS(L+1, sum+a[L], tsum+a[L])
DFS(L+1, sum, tsum+a[L])
if __name__ == "__main__":
c, n = map(int, input().split())
a = [0]*n
result = -2147000000 # 이 안에 선언한 순간 전역변수가 된다 !!!!!
for i in range(n):
a[i] = int(input())
total = sum(a)
DFS(0,0,0)
print(result)
꿀팁 확인 !!!!!!!!!!!!!!!!!!!!!!!!
Author And Source
이 문제에 관하여(Part5.5_완전탐색_부분집합 구하기(DFS)__바둑이 승차__전역변수,지역변수), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@angel_eugnen/Part5.5완전탐색부분집합-구하기DFS바둑이-승차전역변수지역변수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)