{"id":818,"date":"2023-03-12T23:50:21","date_gmt":"2023-03-12T14:50:21","guid":{"rendered":"http:\/\/mukgee.com\/?p=818"},"modified":"2023-03-14T23:04:46","modified_gmt":"2023-03-14T14:04:46","slug":"leetcode123-best-time-to-buy-and-sell-stock-iii","status":"publish","type":"post","link":"http:\/\/mukgee.com\/?p=818","title":{"rendered":"[leetcode]123. Best Time to Buy and Sell Stock III"},"content":{"rendered":"<p>\uc911\uc694\ud55c\uac74 \uaebe\uc774\uc9c0 \uc54a\ub294 \ub9c8\uc74c \uc774\ub77c\uace0 \ud558\uc9c0\ub9cc Hard \ubb38\uc81c \uc55e\uc5d0\uc11c\ub294 \uac70\uc758 \ud56d\uc0c1 \uc88c\uc808\ud558\ub294\uac83 \uac19\uc2b5\ub2c8\ub2e4.<\/p>\n<p>\uc544\uc9c1 \uac08 \uae38\uc774 \uba40\ub2e4\ub294 \ub73b\uc774\uaca0\uc9c0\uc694.<\/p>\n<p>&nbsp;<\/p>\n<p>\uc774\ubc88 \ubb38\uc81c\ub294 \ucc98\uc74c dp \ubb38\uc81c\ub97c \uc798\ubabb \uc815\uc758\ud574\uc11c \uace0\uc0dd\ub9cc \ud558\ub2e4 \uacb0\uad6d \ud480\uc9c0 \ubabb\ud558\uace0 chatGPT \uc758 \ub3c4\uc6c0\uc744 \ubc1b\uc558\uc2b5\ub2c8\ub2e4.<\/p>\n<p>\ucc98\uc74c \uc815\uc758\ud588\ub358 dp \ubb38\uc81c\ub294 \uc544\ub798\uc640 \uac19\uc558\uc2b5\ub2c8\ub2e4.<\/p>\n<blockquote><p><strong>dp[i][j] =&gt; i\ubc88\uc9f8 day \uc5d0\uc11c \uc2dc\uc791\ud574\uc11c j day \uae4c\uc9c0 \uc5bb\uc744 \uc218 \uc788\ub294 max profit<\/strong><\/p><\/blockquote>\n<p>\uc774\ub807\uac8c \ud574\uc11c \ub450 \ud30c\ud2b8\ub85c \ub098\ub220\uc11c \ub450\ubc88 \uad6c\ub9e4\ud558\ub294 \uacbd\uc6b0\uc640 \ud55c\ubc88 \uad6c\ub9e4\ud588\uc744 \uacbd\uc6b0\uc758 max \ub97c \uad6c\ud574\uc11c \uac12\uc744 \uad6c\ud558\ub824\uace0 \ud588\uc73c\ub098,<\/p>\n<p>\uc81c\uac00 \ubb38\uc81c \uc815\uc758\uc5d0\uc11c \ucd5c\ub300 2\ubc88 \uad6c\ub9e4\uac00\ub2a5\ud55c \uc870\uac74\uc744 \ubc18\uc601\ud558\uc9c0 \uc54a\uc544\uc11c \uc2e4\uc81c \ucf54\ub4dc\ub85c\ub3c4 \uac00\ub2a5\ud55c \ucd5c\ub300\ud55c \uad6c\ub9e4\ud560 \ub54c \uc5bb\uc744 \uc218 \uc788\ub294 max profit \uac12\uc774 \ub098\uc640\ubc84\ub838\uc2b5\ub2c8\ub2e4.<\/p>\n<p>(DP \ubb38\uc81c\uc5d0\uc11c\ub294 \ubb38\uc81c \uc815\uc758\uac00 \uc774\ub807\uac8c \uc911\uc694\ud569\ub2c8\ub2e4)<\/p>\n<p>&nbsp;<\/p>\n<p>\uc798\ubabb \uc815\uc758\ub41c \ubb38\uc81c\ub85c \uc5b5\uc9c0\ub85c 2\ubc88\ub9cc \uad6c\ub9e4\ud558\ub3c4\ub85d \uad6c\ud604\ud588\uc73c\ub098 O(N^2) \uc758 \uc2dc\uac04\ubcf5\uc7a1\ub3c4\ub97c \uac00\uc9c4 \uc54c\uace0\ub9ac\uc998\uc73c\ub85c time out \uc774 \ubc1c\uc0dd\ud569\ub2c8\ub2e4. ( 10^5^2 , \ubcf4\ud1b5 1\uc5b5\ubcf4\ub2e4 \ud074 \uacbd\uc6b0 TLE)<\/p>\n<ul>\n<li><code>1 &lt;= prices.length &lt;= 10<sup>5<\/sup><\/code><\/li>\n<\/ul>\n<p>&nbsp;<\/p>\n<p>O(N^2) \ubcf4\ub2e4 \uc88b\uc740 \uc54c\uace0\ub9ac\uc998\uc744 \ucc3e\uc544\uc57c\ud558\ub294\ub370 \uc544\ubb34\ub9ac \uace0\ubbfc\ud574\ubd10\ub3c4 \uc0c8\ub85c\uc6b4 \uc811\uadfc\ubc95\uc774 \ub5a0\uc624\ub974\uc9c0 \uc54a\uc544 \ub9ac\ud2b8\ucf54\ub4dc\uc758 solution \uacfc ChatGPT \uc758 \ub3c4\uc6c0\uc744 \ubc1b\uc558\uc2b5\ub2c8\ub2e4.<\/p>\n<p>\ubb38\uc81c \uc790\uccb4\ub97c \uad6c\ub9e4\ub294 (-) \ud310\ub9e4\ub294 (+) \ub85c \uc774\ud574\ud558\uace0 \uc2dc\uc791\ud569\ub2c8\ub2e4.<\/p>\n<p>\ud06c\uac8c 2\uac00\uc9c0 \uc811\uadfc\ubc95\uc73c\ub85c \uc815\ub9ac \ub420 \uac83 \uac19\uc2b5\ub2c8\ub2e4.<\/p>\n<ol>\n<li>state machine \uc744 \uc774\uc6a9\ud55c \ubc29\ubc95<\/li>\n<li>k th transaction \uc744 \ub530\ub85c \uad00\ub9ac\ud574\uc11c dp \ud478\ub294 \ubc29\ubc95<\/li>\n<\/ol>\n<p>1\ubc88\uc758 \uacbd\uc6b0 \uc815\ub9d0 \uc544\ub984\ub2f5\uace0 \ub108\ubb34 \uae54\ub054\ud55c \ucf54\ub4dc\uc9c0\ub9cc \uc81c\uac00 \ub2e4\uc2dc \uc774 \ubb38\uc81c\ub97c \ud47c\ub2e4\uace0 \ud574\ub3c4 \ub2e4\uc2dc \uc0dd\uac01\ud560 \uc218 \uc5c6\uc744 \uc54c\uace0\ub9ac\uc998\uc778\uac83 \uac19\uc544 \ucc38\uace0\ub9cc \ud558\uc600\uc2b5\ub2c8\ub2e4.<\/p>\n<p>\uac1c\uc778\uc801\uc73c\ub85c\ub294 \uc544\ub798 discussion \uc774 \uac00\uc7a5 \uc798 \uc815\ub9ac\ub41c\uac83 \uac19\uc2b5\ub2c8\ub2e4.<\/p>\n<p>(<a href=\"https:\/\/leetcode.com\/problems\/best-time-to-buy-and-sell-stock-iii\/solutions\/149383\/easy-dp-solution-using-state-machine-o-n-time-complexity-o-1-space-complexity\/\" target=\"_blank\" rel=\"noopener\">https:\/\/leetcode.com\/problems\/best-time-to-buy-and-sell-stock-iii\/solutions\/149383\/easy-dp-solution-using-state-machine-o-n-time-complexity-o-1-space-complexity\/<\/a> )<\/p>\n<p><img loading=\"lazy\" class=\"alignnone wp-image-819\" src=\"http:\/\/mukgee.com\/wp-content\/uploads\/2023\/03\/\u1109\u1173\u110f\u1173\u1105\u1175\u11ab\u1109\u1163\u11ba-2023-03-12-\u110b\u1169\u1112\u116e-11.34.46.png\" alt=\"\" width=\"1129\" height=\"261\" srcset=\"http:\/\/mukgee.com\/wp-content\/uploads\/2023\/03\/\u1109\u1173\u110f\u1173\u1105\u1175\u11ab\u1109\u1163\u11ba-2023-03-12-\u110b\u1169\u1112\u116e-11.34.46.png 1332w, http:\/\/mukgee.com\/wp-content\/uploads\/2023\/03\/\u1109\u1173\u110f\u1173\u1105\u1175\u11ab\u1109\u1163\u11ba-2023-03-12-\u110b\u1169\u1112\u116e-11.34.46-300x69.png 300w, http:\/\/mukgee.com\/wp-content\/uploads\/2023\/03\/\u1109\u1173\u110f\u1173\u1105\u1175\u11ab\u1109\u1163\u11ba-2023-03-12-\u110b\u1169\u1112\u116e-11.34.46-1024x237.png 1024w, http:\/\/mukgee.com\/wp-content\/uploads\/2023\/03\/\u1109\u1173\u110f\u1173\u1105\u1175\u11ab\u1109\u1163\u11ba-2023-03-12-\u110b\u1169\u1112\u116e-11.34.46-768x178.png 768w\" sizes=\"(max-width: 1129px) 100vw, 1129px\" \/><\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>2\ubc88\uc9f8 \uc811\uadfc\ubc95(k th transaction) \uc740 \ub9ac\ud2b8\ucf54\ub4dc discussion \uc5d0 \ub9c8\uc74c\uc5d0 \ub4dc\ub294 \uc811\uadfc\ubc95\uc774 \uc5c6\uc5b4 chatGPT \uc5d0\uac8c \ubb3c\uc5b4\ubd24\uc2b5\ub2c8\ub2e4.<\/p>\n<p>\uc544\ub798\uc640 \uac19\uc740 \uc544\ub984\ub2e4\uc6b4 \ucf54\ub4dc\ub97c \ub9cc\ub4e4\uc5b4\uc8fc\ub294\ub370 \ubc14\ub85c \uc774\ud574\ud558\uae30\uac00 \ud798\ub4e4\uc5b4 \uc870\uae08 \ub098\ub220 \uc0dd\uac01\ud574\ubcf4\uc558\uc2b5\ub2c8\ub2e4.<\/p>\n<p><img loading=\"lazy\" class=\"alignnone wp-image-821\" src=\"http:\/\/mukgee.com\/wp-content\/uploads\/2023\/03\/\u1109\u1173\u110f\u1173\u1105\u1175\u11ab\u1109\u1163\u11ba-2023-03-12-\u110b\u1169\u1112\u116e-11.46.33.png\" alt=\"\" width=\"851\" height=\"459\" srcset=\"http:\/\/mukgee.com\/wp-content\/uploads\/2023\/03\/\u1109\u1173\u110f\u1173\u1105\u1175\u11ab\u1109\u1163\u11ba-2023-03-12-\u110b\u1169\u1112\u116e-11.46.33.png 1072w, http:\/\/mukgee.com\/wp-content\/uploads\/2023\/03\/\u1109\u1173\u110f\u1173\u1105\u1175\u11ab\u1109\u1163\u11ba-2023-03-12-\u110b\u1169\u1112\u116e-11.46.33-300x162.png 300w, http:\/\/mukgee.com\/wp-content\/uploads\/2023\/03\/\u1109\u1173\u110f\u1173\u1105\u1175\u11ab\u1109\u1163\u11ba-2023-03-12-\u110b\u1169\u1112\u116e-11.46.33-1024x552.png 1024w, http:\/\/mukgee.com\/wp-content\/uploads\/2023\/03\/\u1109\u1173\u110f\u1173\u1105\u1175\u11ab\u1109\u1163\u11ba-2023-03-12-\u110b\u1169\u1112\u116e-11.46.33-768x414.png 768w\" sizes=\"(max-width: 851px) 100vw, 851px\" \/><\/p>\n<p>\uc704\uc758 \uc811\uadfc\ubc95\uc5d0\uc11c dp \ubb38\uc81c\ub294 \uc544\ub798\uc640 \uac19\uc774 \uc815\uc758\ub429\ub2c8\ub2e4.<\/p>\n<p>&nbsp;<\/p>\n<blockquote><p><strong>dp[i][k] =&gt; \ucd5c\ub300 k \ubc88\uc758 transaction \uc744 \uc2e4\ud589\ud588\uc744\ub54c i \ubc88\uc9f8 day \uc5d0\uc11c\uc758 max profit\u00a0 \u00a0<\/strong><\/p><\/blockquote>\n<p>&nbsp;<\/p>\n<p>\uadf8\ub9ac\uace0 \uc774 \ubb38\uc81c\ub97c dp\ubb38\uc81c(\uc791\uc740 \ubb38\uc81c\ub4e4\uc744 \uc0ac\uc6a9\ud574\uc11c \ud070 \ubb38\uc81c\ub97c \ud478\ub294 \uc811\uadfc\ubc95)\ub85c \ub9cc\ub4e4\uc5b4\uc8fc\ub294 \ubcc0\uc218\uac00 max_diff \uc785\ub2c8\ub2e4.<\/p>\n<p>max_diff =&gt; k-1 \ubc88\uc9f8\uc758 transaction \uc744 \uc2e4\ud589\ud588\uc744\ub54c i \ubc88\uc9f8 day \uae4c\uc9c0 \uc5bb\uc744 \uc218 \uc788\ub294 max profit \uc5d0 \ud604\uc7ac\uc758 stock \uc744 \uad6c\ub9e4\ud55c \uac12<\/p>\n<p>\uc774\uc775\uc744 \ucd5c\ub300\ud654 \ud558\uba74\uc11c\ub3c4 \uac00\uc7a5 \uc800\ub834\ud55c stock \uc744 \uad6c\ub9e4\ud55c \uac12\uc774 max_diff \uc785\ub2c8\ub2e4.<\/p>\n<p>&nbsp;<\/p>\n<p>\uadf8\ub7fc dp[i][k] \ub294 \uc544\ubb34\uac83\ub3c4 \uc0ac\uc9c0 \uc54a\uac70\ub098( dp[i-1][k] )\u00a0 1\ud68c transaction \uc774 \uc218\ud589\ub418\uace0 stock\uc744 \uad6c\ub9e4\ud55c \uc0c1\ud0dc\uc758 \uac12\uc744 \ud604\uc7ac \uac00\uaca9\uc5d0 \ud30c\ub294 ( prices[i] + max_diff ) \uac83 \uc911 max \uac00 \ucd5c\ub300 profit \uc785\ub2c8\ub2e4.<\/p>\n<p>&nbsp;<\/p>\n<blockquote><p><strong>dp[i][k] = max( dp[i-1][k] , prices[i] + max_diff )<\/strong><\/p><\/blockquote>\n<p>&nbsp;<\/p>\n<p>ChatGPT \uc758 \ucf54\ub4dc\ub97c \uadf8\ub300\ub85c \uc0ac\uc6a9\ud588\uc9c0\ub9cc \uadf8\ub798\ub3c4 \uc81c\uac00 \uc774\ud574\ud55c \uc21c\uc11c\ub300\ub85c \ucf54\ub4dc\ub294 \uc870\uae08 \ub098\ub220\ubcf4\uc558\uc2b5\ub2c8\ub2e4.<\/p>\n<p><a href=\"https:\/\/github.com\/sok891111\/leetcode\/blob\/main\/123.%20Best%20Time%20to%20Buy%20and%20Sell%20Stock%20III.py\" target=\"_blank\" rel=\"noopener\">https:\/\/github.com\/sok891111\/leetcode\/blob\/main\/123.%20Best%20Time%20to%20Buy%20and%20Sell%20Stock%20III.py<\/a><\/p>\n<p>&nbsp;<\/p>\n<p>\ubb38\uc81c\ub97c \uad6c\ub9e4\ub294 (-) \ud310\ub9e4\ub294 (+) \ub85c \uc0dd\uac01\ud558\ub294\uac83\uacfc transaction \ub2e8\uc704\ub85c dp \uc801\uc73c\ub85c \uc0dd\uac01\ud558\ub294 \ubd80\ubd84\uc774 \ubd80\uc871\ud588\ub358\uac83 \uac19\uc2b5\ub2c8\ub2e4.<\/p>\n<p>\ud2b9\ud788 dp \ubb38\uc81c\ub294 \uc0dd\uac01\uc758 \ud55c\uacc4\ub97c \ub118\ub294 \ub178\ub825\uc774 \ub9ce\uc774 \ud544\uc694\ud560\uac83 \uac19\uc2b5\ub2c8\ub2e4.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\uc911\uc694\ud55c\uac74 \uaebe\uc774\uc9c0 \uc54a\ub294 \ub9c8\uc74c \uc774\ub77c\uace0 \ud558\uc9c0\ub9cc Hard \ubb38\uc81c \uc55e\uc5d0\uc11c\ub294 \uac70\uc758 \ud56d\uc0c1 \uc88c\uc808\ud558\ub294\uac83 \uac19\uc2b5\ub2c8\ub2e4. \uc544\uc9c1 \uac08 \uae38\uc774 \uba40\ub2e4\ub294 \ub73b\uc774\uaca0\uc9c0\uc694. &nbsp; \uc774\ubc88 \ubb38\uc81c\ub294 \ucc98\uc74c dp \ubb38\uc81c\ub97c \uc798\ubabb&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":[86,81],"aioseo_notices":[],"jetpack_featured_media_url":"","_links":{"self":[{"href":"http:\/\/mukgee.com\/index.php?rest_route=\/wp\/v2\/posts\/818"}],"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=818"}],"version-history":[{"count":3,"href":"http:\/\/mukgee.com\/index.php?rest_route=\/wp\/v2\/posts\/818\/revisions"}],"predecessor-version":[{"id":825,"href":"http:\/\/mukgee.com\/index.php?rest_route=\/wp\/v2\/posts\/818\/revisions\/825"}],"wp:attachment":[{"href":"http:\/\/mukgee.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=818"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/mukgee.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=818"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/mukgee.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=818"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}