-
69 - (파이썬) 확인문제, 메모화 추가study with Q - 파이썬 2024. 8. 1. 14:54
전체사람수 = 6 counter = 0 #이전에 몇 명을 앉혔는지 이전 화살표에 적힌 숫자를 만들어주고 def graph(nod,preArrowNumber): if nod == 0: global counter counter += 1 #2와 이전 화살표에 적힌 숫자 중 큰 것을 선택하는 조건을 만들어준다 for i in range(max(2,preArrowNumber), min(nod, 10)+1): #매개변수는 i를 전달해서 말해준다 graph(nod-i, i) #이전 화살표의 항등원은 0 graph(전체사람수,0) print(counter) >>> 4
여기에 메모화를 추가해보자.
위 함수는 값을 가지지 않기 때문에 (return 값을 가지지 않으므로) 메모화가 불가능하다. 따라서 어떠한 return 값을 줘보자고.
step 1) counter라는 부분은 날리고 +1은 남긴다
def graph(nod,preArrowNumber): # counter라는 부분은 날리고 +1은 남긴다 if nod == 0: += 1 for i in range(max(2,preArrowNumber), min(nod, 10)+1): graph(nod-i, i)
step 2) 메모화를 위해 딕셔너리를 추가한다
전체사람수 = 6 #메모화를 위해 딕셔너리를 추가한다. memo = { }
step 3) 딕셔너리에 키:값을 넣는다
: 일반적으로 메모화를 할 때는 함수의 매개변수를 키로 활용하고 리턴값을 값으로 사용하므로 함수의 매개변수를 (튜플 형태) 키로 사용한다.
step 4) 리턴값을 주고 항등원으로 초기화를 하고, 함수 마지막에 return을 받는다.
step 5) 노드가 0일 때마다 리턴값을 +1 해준다
step 6) 리턴값에 그래프를 더해준다
전체사람수 = 6 #메모화를 위해 딕셔너리를 추가한다. memo = { #키:값 #함수의 매개변수: 리턴값 } def graph(nod,preArrowNumber): #값 두개가 쉼표로 연결되어 있으므로 요건 튜플이고, 튜플은 이뮤터블 자료형이므로 딕셔너리의 키로 쓸 수 있다. (nod,preArrowNumber) #리턴값을 항등원으로 초기화 한다 returnValue = 0 # counter라는 부분은 날리고 +1은 남긴다 if nod == 0: returnValue += 1 for i in range(max(2,preArrowNumber), min(nod, 10)+1): returnValue += graph(nod-i, i) return returnValue print(graph(전체사람수,0)) >>> 4
요렇게 해서 제대로 return이 되는 것을 확인했으니 이제 메모화를 마저 하면
#이렇게 완성
전체사람수 = 6 memo = { } def graph(nod,preArrowNumber): #메모화는 요기요기 if (nod,preArrowNumber) in memo: return memo[(nod,preArrowNumber)] #일반적인 상황 returnValue = 0 if nod == 0: returnValue += 1 for i in range(max(2,preArrowNumber), min(nod, 10)+1): returnValue += graph(nod-i, i) memo[(nod,preArrowNumber)] = returnValue return returnValue print(graph(전체사람수,0)) >>> 4
100명일 때도
전체사람수 = 100 memo = { } def graph(nod,preArrowNumber): #메모화는 요기요기 if (nod,preArrowNumber) in memo: return memo[(nod,preArrowNumber)] #일반적인 상황 returnValue = 0 if nod == 0: returnValue += 1 for i in range(max(2,preArrowNumber), min(nod, 10)+1): returnValue += graph(nod-i, i) memo[(nod,preArrowNumber)] = returnValue return returnValue print(graph(전체사람수,0))
... 시간은 안 구할래요
'study with Q - 파이썬' 카테고리의 다른 글
72 - (파이썬) 구문오류와 예외 (0) 2024.08.08 70 - (파이썬) 하노이탑 (0) 2024.08.01 68 - (파이썬) 확인문제: 기본 형태 (0) 2024.07.29 67 - (파이썬) 가독성과 유지보수성 (0) 2024.07.15 66 - (파이썬) 이터러블, 이터레이터, 제너레이터 함수, 제너레이터 표현식 (0) 2024.07.09