{"id":451,"date":"2018-03-17T21:42:57","date_gmt":"2018-03-17T12:42:57","guid":{"rendered":"http:\/\/dong1lkim.oboki.net\/?p=451"},"modified":"2019-09-01T22:21:42","modified_gmt":"2019-09-01T13:21:42","slug":"python-memoization%ec%9d%84-%ec%9d%b4%ec%9a%a9%ed%95%9c-fibonacci","status":"publish","type":"post","link":"https:\/\/oboki.net\/workspace\/python\/python-memoization%ec%9d%84-%ec%9d%b4%ec%9a%a9%ed%95%9c-fibonacci\/","title":{"rendered":"[Python] Memoization\uc744 \uc774\uc6a9\ud55c Fibonacci"},"content":{"rendered":"

Fibonacci using Memoization<\/h1>\n

Legacy Fibonacci<\/h2>\n
def fibo(n):\n    return n if n < 2 else fibo(n-2) + fibo(n-1)\n\ndef Main():\n    number = int(input(\"Enter integer: \"))\n    print(fibo(number))\n\nif __name__=='__main__':\n    Main()\n<\/code><\/pre>\n
Fibonacci using Memoization<\/h2>\n
__fibo_cache = {}\ndef fibo(n):\n    if n in __fibo_cache:\n        return __fibo_cache[n]\n    else:\n        __fibo_cache[n] = n if n < 2 else fibo(n-2) + fibo(n-1)\n        return __fibo_cache[n]\n\ndef Main():\n    number = int(input(\"Enter integer: \"))\n    print(fibo(number))\n\nif __name__=='__main__':\n    Main()\n<\/code><\/pre>\n
\uc704 \uc18c\uc2a4\ub97c \uae30\uc900\uc73c\ub85c fibo(5) \uc744 \uad6c\ud55c\ub2e4\uace0 \uac00\uc815\ud558\uba74 \uc544\ub798\uc640 \uac19\uc740 \uc21c\uc11c\ub85c memoization \uc744 \uc218\ud589\ud55c\ub2e4.<\/p>\n
    \n
  1. call fibo(5) -> 5 is not in __fibo_cache -> fibo(3) + fibo(4)<\/li>\n
  2. call fibo(3) -> 3 is not in __fibo_cache -> fibo(1) + fibo(2)<\/li>\n
  3. call fibo(1) -> 1 is not in __fibo_cache -> __fibo_cache[1] = 1 memo<\/strong><\/li>\n
  4. call fibo(2) -> 2 is not in __fibo_cache -> __fibo_cache[2] = 2 memo<\/strong><\/li>\n
  5. __fibo_cache[3] = 1 + 2 = 3 memo<\/strong><\/li>\n
  6. call fibo(4) -> 4 is not in __fibo_cache -> fibo(2) + fibo(3)<\/li>\n
  7. 2,3 is in __fibo_cache -> __fibo_cache[4] = 2 + 3 = 5 memo<\/strong><\/li>\n
  8. __fibo_cache[5] = 3 + 5 = 8 memo<\/li>\n<\/ol>\n
    \uc911\ubcf5\ud574\uc11c \uacc4\uc0b0\uc774 \ud544\uc694\ud55c \ubd80\ubd84\uc740 memo\ub97c \ud574\ub450\uace0 \uadf8\uac83\uc744 \ucc3e\uc544\ubcfe\uc73c\ub85c\uc368 \ubd88\ud544\uc694\ud55c \uc5f0\uc0b0\uc744 \uc904\uc5ec\uc904 \uc218 \uc788\ub2e4.<\/p>\n
    Fibonacci using memoization and decorator<\/h3>\n
    Python\uc758 Decorator\ub97c \uc774\uc6a9\ud558\uba74 \uc544\ub798\uc640 \uac19\uc774 \uc880 \ub354 \uadf8\ub7f4\uc2f8\ud558\uac8c \uad6c\ud604\ud560 \uc218 \uc788\ub2e4.<\/p>\n
    def memoize(f):\n    cache = {}\n    def decorated_function(*args):\n        if args in cache:\n            return cache[args]\n        else:\n            cache[args] = f(*args)\n            return cache[args]\n    return decorated_function\n\n@memoize\ndef fibo(n):\n    return n if n < 2 else fibo(n-2) + fibo(n-1)\n\ndef Main():\n    number = int(input(\"Enter integer: \"))\n    print(fibo(number))\n\nif __name__=='__main__':\n    Main()\n<\/code><\/pre>\n
    \uc18c\uc2a4\ucf54\ub4dc \ucd9c\ucc98: http:\/\/ujihisa.blogspot.com\/2010\/11\/memoized-recursive-fibonacci-in-python.html<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
    Fibonacci using Memoization Legacy Fibonacci def fibo(n): return n if n < 2 else fibo(n-2) + fibo(n-1) def Main(): number = int(input(“Enter integer: “)) print(fibo(number)) if __name__==’__main__’: Main() Fibonacci using Memoization __fibo_cache = {} def fibo(n): if n in __fibo_cache: return __fibo_cache[n] else: __fibo_cache[n] = n if n < 2 else fibo(n-2) + fibo(n-1) return […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[10],"tags":[34],"class_list":["post-451","post","type-post","status-publish","format-standard","hentry","category-python","tag-python"],"_links":{"self":[{"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts\/451","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/comments?post=451"}],"version-history":[{"count":5,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts\/451\/revisions"}],"predecessor-version":[{"id":1285,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/posts\/451\/revisions\/1285"}],"wp:attachment":[{"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/media?parent=451"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/categories?post=451"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/oboki.net\/workspace\/wp-json\/wp\/v2\/tags?post=451"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}