{"id":408,"date":"2019-09-08T17:15:42","date_gmt":"2019-09-08T08:15:42","guid":{"rendered":"https:\/\/blog.enyou.net\/?p=408"},"modified":"2019-09-08T17:15:42","modified_gmt":"2019-09-08T08:15:42","slug":"python3-trie-%ec%9e%90%eb%a3%8c%ea%b5%ac%ec%a1%b0-%ea%b5%ac%ed%98%84","status":"publish","type":"post","link":"https:\/\/blog.enyou.net\/ko\/archives\/408","title":{"rendered":"Python3 Trie \uc790\ub8cc\uad6c\uc870 \uad6c\ud604"},"content":{"rendered":"\n<pre class=\"wp-block-code\"><code>class Node:\n    def __init__(self):\n        self.count = 0\n        self.pointer = [None for i in range(26)]\n\nclass Trie:\n    def __init__(self):\n        self.root = Node()\n        self.str_to_int = {}\n\n        for i in range(97, 123):\n            self.str_to_int[chr(i)] = i - 97\n        \n    def insert(self, string):\n        self.root = self._insert(self.root, string)\n\n    def _insert(self, node, string):\n        if not node: #\ub178\ub4dc\uac00 \uc5c6\ub2e4.\n            node = Node()\n            \n        if not string: #\uc885\ub9d0 \ub178\ub4dc\uc774\ub2e4.\n            node.count += 1\n        else: #\uc885\ub9d0 \ub178\ub4dc\uac00 \uc544\ub2c8\ub2e4.\n            node.pointer[self.str_to_int[string[0]]] = self._insert(node.pointer[self.str_to_int[string[0]]], string[1:])\n\n        return node\n\n    def find(self, string):\n        node = self.root\n\n        while node and string:\n            node = node.pointer[self.str_to_int[string[0]]]\n            string = string[1:]\n\n        if not node:\n            return 0\n        if node.count == 0:\n            return 0\n        else:\n            return node.count\n\n\ntrie = Trie()\ntrie.insert('aaaabb')\nprint(trie.find('aaaabb'))\nprint(trie.find('aaaab'))\nprint(trie.find('aab'))\nprint(trie.find('aaaabbbbb'))\ntrie.insert('xyz')\nprint(trie.find('xy'))\nprint(trie.find('yx'))\nprint(trie.find('xyz'))\ntrie.insert('xyz')\nprint(trie.find('xyz'))<\/code><\/pre>\n\n\n\n<p>\ubb38\uc790\uc5f4 \uac80\uc0c9\uc5d0 \uc790\uc8fc \uc0ac\uc6a9\ub418\ub294 \uc790\ub8cc\uad6c\uc870\uc778 Trie\uc774\ub2e4. \ub300\ud559 \uc218\uc5c5\uc5d0\uc11c\ub294 \ub530\ub85c \uac00\ub974\uccd0 \uc8fc\uc9c0 \uc54a\uc740 \uae30\uc5b5\uc778\ub370, \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c\ub294 \uaf64\ub098 \uc790\uc8fc \uc774\uc6a9\ub418\ub294 \uc790\ub8cc \uad6c\uc870\uc778 \uac83 \uac19\ub2e4. (2017, 2019 \uce74\uce74\uc624 \ube14\ub77c\uc778\ub4dc \ud14c\uc2a4\ud2b8\uc758 \ubb38\uc81c \ud558\ub098 \uc529\uc758 \uc815\ud574\uc5d0\uc11c \uc0ac\uc6a9\ub418\uc5c8\ub2e4.)<\/p>\n\n\n\n<p>\uc774\uac83\ubcf4\ub2e4 \uac04\ub2e8\ud558\uac8c \uad6c\ud604\ud558\ub824\uba74, \uc0ac\uc804 \uc790\ub8cc\uad6c\uc870\ub97c \uacc4\uc18d \uc911\ucca9\ud558\uba74\uc11c \uad6c\ud604\ud558\ub294 \ubc29\ubc95\ub3c4 \uc788\ub2e4.<\/p>\n\n\n\n<p>\ubcc4\ub3c4\uc758 \ub178\ub4dc\uc640 \ud2b8\ub77c\uc774 \uac1d\uccb4\ub97c \ubd84\ub9ac\ud574\uc11c \uc791\uc131\ud560 \ud544\uc694 \uc5c6\uc774 \ub178\ub4dc \uac1d\uccb4\ub9cc\uc744 \uc0ac\uc804\uacfc \uce74\uc6b4\ud2b8\ub85c \uc791\uc131\ud574\uc8fc\uba74 \ub354 \uac04\ub2e8\ud558\uac8c \uad6c\ud604\uc774 \uac00\ub2a5\ud558\ub2e4.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\ubb38\uc790\uc5f4 \uac80\uc0c9\uc5d0 \uc790\uc8fc \uc0ac\uc6a9\ub418\ub294 \uc790\ub8cc\uad6c\uc870\uc778 Trie\uc774\ub2e4. \ub300\ud559 \uc218\uc5c5\uc5d0\uc11c\ub294 \ub530\ub85c \uac00\ub974\uccd0 \uc8fc\uc9c0 \uc54a\uc740 \uae30\uc5b5\uc778\ub370, \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c\ub294 \uaf64\ub098 \uc790\uc8fc \uc774\uc6a9\ub418\ub294 \uc790\ub8cc \uad6c\uc870\uc778 \uac83 \uac19\ub2e4. (2017, 2019 \uce74\uce74\uc624 \ube14\ub77c\uc778\ub4dc \ud14c\uc2a4\ud2b8\uc758 \ubb38\uc81c \ud558\ub098 \uc529\uc758 \uc815\ud574\uc5d0\uc11c \uc0ac\uc6a9\ub418\uc5c8\ub2e4.) \uc774\uac83\ubcf4\ub2e4 \uac04\ub2e8\ud558\uac8c \uad6c\ud604\ud558\ub824\uba74, \uc0ac\uc804 \uc790\ub8cc\uad6c\uc870\ub97c \uacc4\uc18d \uc911\ucca9\ud558\uba74\uc11c \uad6c\ud604\ud558\ub294 \ubc29\ubc95\ub3c4 \uc788\ub2e4. \ubcc4\ub3c4\uc758 \ub178\ub4dc\uc640 \ud2b8\ub77c\uc774 \uac1d\uccb4\ub97c \ubd84\ub9ac\ud574\uc11c \uc791\uc131\ud560 \ud544\uc694 \uc5c6\uc774 [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[1],"tags":[],"class_list":["post-408","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_featured_media_url":"","jetpack-related-posts":[],"jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/blog.enyou.net\/ko\/wp-json\/wp\/v2\/posts\/408"}],"collection":[{"href":"https:\/\/blog.enyou.net\/ko\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.enyou.net\/ko\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.enyou.net\/ko\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.enyou.net\/ko\/wp-json\/wp\/v2\/comments?post=408"}],"version-history":[{"count":1,"href":"https:\/\/blog.enyou.net\/ko\/wp-json\/wp\/v2\/posts\/408\/revisions"}],"predecessor-version":[{"id":409,"href":"https:\/\/blog.enyou.net\/ko\/wp-json\/wp\/v2\/posts\/408\/revisions\/409"}],"wp:attachment":[{"href":"https:\/\/blog.enyou.net\/ko\/wp-json\/wp\/v2\/media?parent=408"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.enyou.net\/ko\/wp-json\/wp\/v2\/categories?post=408"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.enyou.net\/ko\/wp-json\/wp\/v2\/tags?post=408"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}