{"id":782,"date":"2022-12-18T20:59:46","date_gmt":"2022-12-18T11:59:46","guid":{"rendered":"http:\/\/mukgee.com\/?p=782"},"modified":"2022-12-18T20:59:46","modified_gmt":"2022-12-18T11:59:46","slug":"leetcode139-word-break","status":"publish","type":"post","link":"http:\/\/mukgee.com\/?p=782","title":{"rendered":"[leetcode]139. Word Break"},"content":{"rendered":"<p>https:\/\/leetcode.com\/problems\/word-break\/<\/p>\n<p>\ub9ac\ud2b8\ucf54\ub4dc 139\ubc88 \ubb38\uc81c\ub294 \uc0ac\uc2e4 Dynamic Programming(DP) \ub85c \uc774 \ubb38\uc81c\ub97c \ud480\uc5b4\uc57c\ud55c\ub2e4\ub294\uac78 \uc54c\uba74 \uc26c\uc6b4 \ubb38\uc81c\uc785\ub2c8\ub2e4.<\/p>\n<p>\uc27d\uac8c \uac00\uace0 \uc2f6\uc5b4\uc11c Related Topics \ub97c \uc7a0\uae50 \ud655\uc778\ud588\uace0 DP \ub85c \ud480\uc218 \uc788\ub294 \ubb38\uc81c\ub77c\ub294\uac78 \uc54c\uac8c\ub41c \ud6c4\uc5d0\ub294 DP \uc801\uc778 \uc811\uadfc\ubc95\uc73c\ub85c \uc27d\uac8c \uc54c\uace0\ub9ac\uc998\uc744 \uad6c\ud604 \ud560 \uc218 \uc788\uc5c8\uc2b5\ub2c8\ub2e4.<\/p>\n<p>&nbsp;<\/p>\n<p>DP \ub294 \uc791\uc740 \ubb38\uc81c\uc758 \ub2f5\uc744 \uc774\uc6a9\ud574 \ud070 \ubb38\uc81c\ub97c \ud574\uacb0\ud55c\ub2e4\ub294 \uc81c\uadc0\ubc95\uc801 \ud574\uacb0\ubc95\uacfc \uba54\ubaa8\uc774\uc81c\uc774\uc158\uc744 \uc870\ud569\ud55c \uc54c\uace0\ub9ac\uc998 \uc811\uadfc\ubc95\uc774\ub2e4.<\/p>\n<p>DP \uc124\uba85\uc744 \uc704\ud574 \uc774\uc804\uc5d0 \uacf5\uc720\ud55c \uc0ac\ub2e4\ub9ac \ud0c0\uae30 \ubb38\uc81c\ub97c \uacf5\uc720\ud569\ub2c8\ub2e4.<\/p>\n<p><img loading=\"lazy\" class=\"alignnone wp-image-779\" style=\"font-family: -apple-system, BlinkMacSystemFont, 'Segoe UI', Roboto, Oxygen-Sans, Ubuntu, Cantarell, 'Helvetica Neue', sans-serif;\" src=\"http:\/\/mukgee.com\/wp-content\/uploads\/2022\/12\/\u1109\u1173\u110f\u1173\u1105\u1175\u11ab\u1109\u1163\u11ba-2022-12-18-\u110b\u1169\u1112\u116e-8.49.44.png\" alt=\"\" width=\"1142\" height=\"559\" srcset=\"http:\/\/mukgee.com\/wp-content\/uploads\/2022\/12\/\u1109\u1173\u110f\u1173\u1105\u1175\u11ab\u1109\u1163\u11ba-2022-12-18-\u110b\u1169\u1112\u116e-8.49.44.png 1818w, http:\/\/mukgee.com\/wp-content\/uploads\/2022\/12\/\u1109\u1173\u110f\u1173\u1105\u1175\u11ab\u1109\u1163\u11ba-2022-12-18-\u110b\u1169\u1112\u116e-8.49.44-300x147.png 300w, http:\/\/mukgee.com\/wp-content\/uploads\/2022\/12\/\u1109\u1173\u110f\u1173\u1105\u1175\u11ab\u1109\u1163\u11ba-2022-12-18-\u110b\u1169\u1112\u116e-8.49.44-1024x501.png 1024w, http:\/\/mukgee.com\/wp-content\/uploads\/2022\/12\/\u1109\u1173\u110f\u1173\u1105\u1175\u11ab\u1109\u1163\u11ba-2022-12-18-\u110b\u1169\u1112\u116e-8.49.44-768x376.png 768w, http:\/\/mukgee.com\/wp-content\/uploads\/2022\/12\/\u1109\u1173\u110f\u1173\u1105\u1175\u11ab\u1109\u1163\u11ba-2022-12-18-\u110b\u1169\u1112\u116e-8.49.44-1536x752.png 1536w\" sizes=\"(max-width: 1142px) 100vw, 1142px\" \/><\/p>\n<blockquote class=\"wp-embedded-content\" data-secret=\"w429LOgWjQ\"><p><a href=\"http:\/\/mukgee.com\/?p=544\">[\ub3d9\uc801\uacc4\ud68d\ubc95]\uc0ac\ub2e4\ub9ac \uc62c\ub77c\uac00\uae30<\/a><\/p><\/blockquote>\n<p><iframe class=\"wp-embedded-content\" sandbox=\"allow-scripts\" security=\"restricted\" style=\"position: absolute; clip: rect(1px, 1px, 1px, 1px);\" title=\"&#8220;[\ub3d9\uc801\uacc4\ud68d\ubc95]\uc0ac\ub2e4\ub9ac \uc62c\ub77c\uac00\uae30&#8221; &#8212; sungjin&#039; blog\" src=\"http:\/\/mukgee.com\/?p=544&#038;embed=true#?secret=w429LOgWjQ\" data-secret=\"w429LOgWjQ\" width=\"600\" height=\"338\" frameborder=\"0\" marginwidth=\"0\" marginheight=\"0\" scrolling=\"no\"><\/iframe><\/p>\n<p>139\ubc88 \ubb38\uc81c\uc758 DP \uc801 \uc811\uadfc\uc740 \uc544\ub798\uc640 \uac19\uc2b5\ub2c8\ub2e4.<\/p>\n<p>dp[i-len(word)] == True \uc774\uace0 s[i:len(word)] == word \uc774\ub77c\uba74 dp[i] = True \uc785\ub2c8\ub2e4.<\/p>\n<p>\uc0ac\ub2e4\ub9ac \ud0c0\uae30\uc640 \uc57d\uac04 \ub2e4\ub978\ub370, \ud604\uc7ac \ub2e8\uc5b4 \uc774\uc804\uae4c\uc9c0\uac00 \uc870\uac74\uc744 \ub9cc\uc871\ud55c\ub2e4\uba74 \ud604\uc7ac \ub2e8\uc5b4\ub9cc\ud07c\ub9cc \ud655\uc778\ud574\uc11c True \uc5ec\ubd80\ub97c \ud310\ub2e8\ud558\uba74 \ub429\ub2c8\ub2e4.<\/p>\n<p>&nbsp;<\/p>\n<pre class=\"lang:python decode:true \">class Solution(object):\r\n    def wordBreak(self, s, wordDict):\r\n        L = len(s)+1\r\n        dp =[False]*L\r\n        dp[0] = True\r\n        for index in range(L):\r\n            for word in wordDict:\r\n                if index - len(word) &gt;= 0 :\r\n                    if dp[index-len(word)] == True and s[index-len(word) : index] == word :\r\n                        dp[index] = True\r\n                        break\r\n        return dp[-1]<\/pre>\n<p>&nbsp;<\/p>\n<p>DP \ubb38\uc81c\ub294 \ud480\uc218 \uc788\ub294 \uc791\uc740 \ubb38\uc81c\ub85c \ub098\ub204\uace0 \uadf8 \uc791\uc740 \ubb38\uc81c\ub97c \ud65c\uc6a9\ud574\uc11c \ub2e4\uc74c \ubb38\uc81c\ub97c \ud478\ub294 \ubc29\ubc95\uc73c\ub85c \uace0\ubbfc\ud558\uba74 \ubc29\ubc95\uc744 \ucc3e\uc544 \ub098\uac08 \uc218 \uc788\ub294\uac83 \uac19\uc2b5\ub2c8\ub2e4.<\/p>\n<p>\ub2e4\ub9cc, \uc774\ubc88 \ubb38\uc81c\ub97c DP \ub85c \uc811\uadfc\ud574\uc57c\ud55c\ub2e4\ub294 \uac78 \uc54c\uc544\ucc28\ub9ac\ub294\uac8c \uc27d\uc9c0 \uc54a\uc558\uc2b5\ub2c8\ub2e4( \ucc98\uc74c\uc5d0\ub294 backtracking \uc73c\ub85c \uc0dd\uac01 \ud588\uc2b5\ub2c8\ub2e4.)<\/p>\n<p>&nbsp;<\/p>\n<p><a href=\"https:\/\/github.com\/sok891111\/leetcode\/blob\/main\/WEEK26\/139.%20Word%20Break.py\" target=\"_blank\" rel=\"noopener\">https:\/\/github.com\/sok891111\/leetcode\/blob\/main\/WEEK26\/139.%20Word%20Break.py<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/leetcode.com\/problems\/word-break\/ \ub9ac\ud2b8\ucf54\ub4dc 139\ubc88 \ubb38\uc81c\ub294 \uc0ac\uc2e4 Dynamic Programming(DP) \ub85c \uc774 \ubb38\uc81c\ub97c \ud480\uc5b4\uc57c\ud55c\ub2e4\ub294\uac78 \uc54c\uba74 \uc26c\uc6b4 \ubb38\uc81c\uc785\ub2c8\ub2e4. \uc27d\uac8c \uac00\uace0 \uc2f6\uc5b4\uc11c Related Topics \ub97c \uc7a0\uae50 \ud655\uc778\ud588\uace0 DP \ub85c \ud480\uc218&hellip;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"spay_email":""},"categories":[3],"tags":[81,53],"aioseo_notices":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"http:\/\/mukgee.com\/index.php?rest_route=\/wp\/v2\/posts\/782"}],"collection":[{"href":"http:\/\/mukgee.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/mukgee.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/mukgee.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/mukgee.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=782"}],"version-history":[{"count":1,"href":"http:\/\/mukgee.com\/index.php?rest_route=\/wp\/v2\/posts\/782\/revisions"}],"predecessor-version":[{"id":783,"href":"http:\/\/mukgee.com\/index.php?rest_route=\/wp\/v2\/posts\/782\/revisions\/783"}],"wp:attachment":[{"href":"http:\/\/mukgee.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=782"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/mukgee.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=782"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/mukgee.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=782"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}