69 - (파이썬) 확인문제, 메모화 추가

전체사람수 = 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))

 

 

... 시간은 안 구할래요

 

---

https://replit.com/@wh3308/LongtermDramaticPress#main.py