{"id":27985,"date":"2024-10-27T15:20:52","date_gmt":"2024-10-27T15:20:52","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=27985"},"modified":"2024-11-26T07:12:36","modified_gmt":"2024-11-26T07:12:36","slug":"%ec%9e%90%eb%b0%94%ec%8a%a4%ed%81%ac%eb%a6%bd%ed%8a%b8-%ec%bd%94%eb%94%a9%ed%85%8c%ec%8a%a4%ed%8a%b8-%ea%b0%95%ec%a2%8c-%ec%b5%9c%ec%86%8c-%eb%b9%84%ec%9a%a9-%ea%b5%ac%ed%95%98%ea%b8%b0","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/27985\/","title":{"rendered":"\uc790\ubc14\uc2a4\ud06c\ub9bd\ud2b8 \ucf54\ub529\ud14c\uc2a4\ud2b8 \uac15\uc88c, \ucd5c\uc18c \ube44\uc6a9 \uad6c\ud558\uae30"},"content":{"rendered":"

<\/p>\n

\n

\ubb38\uc81c \uc124\uba85<\/h2>\n

\uc8fc\uc5b4\uc9c4 \ube44\uc6a9 \ubc30\uc5f4\uc774 \uc788\uc2b5\ub2c8\ub2e4. \ubc30\uc5f4\uc758 \uac01 \uc778\ub371\uc2a4\ub294 \ud2b9\uc815 \uc704\uce58\uc5d0 \ub3c4\ub2ec\ud558\ub294 \ube44\uc6a9\uc774\uba70, \ud2b9\uc815 \uc9c0\uc810\uc5d0\uc11c \uc2dc\uc791\ud558\uc5ec \ub05d \uc9c0\uc810\uc5d0 \ub3c4\ub2ec\ud560 \ub54c\uc758 \ucd5c\uc18c \ube44\uc6a9\uc744 \uacc4\uc0b0\ud558\uc2ed\uc2dc\uc624.<\/p>\n

\uc608\ub97c \ub4e4\uc5b4, \ube44\uc6a9 \ubc30\uc5f4\uc774 [10, 15, 20]<\/code>\uc774\ub77c\uba74, \uccab \ubc88\uc9f8 \uc778\ub371\uc2a4(0)\uc5d0\uc11c \uc2dc\uc791\ud558\uc5ec \ub450 \ubc88\uc9f8 \uc778\ub371\uc2a4(1) \ub610\ub294 \uc138 \ubc88\uc9f8 \uc778\ub371\uc2a4(2)\uae4c\uc9c0 \uac00\ub294 \ucd5c\uc18c \ube44\uc6a9\uc744 \ucc3e\uc544\uc57c \ud569\ub2c8\ub2e4. \uc774 \uacbd\uc6b0, 1 \uc778\ub371\uc2a4\ub97c \uac70\uce58\ub294 \ube44\uc6a9 15\uac00 \uacb0\uc815\ub429\ub2c8\ub2e4.<\/p>\n

\uc785\ub825<\/h3>\n

– \ube44\uc6a9 \ubc30\uc5f4: cost<\/code> (1 <= cost.length <= 100)<\/p>\n

\ucd9c\ub825<\/h3>\n

– \ucd5c\uc18c \ube44\uc6a9\uc778 \uc22b\uc790\ub97c \ubc18\ud658\ud569\ub2c8\ub2e4.<\/p>\n

\uc81c\ud55c \uc0ac\ud56d<\/h3>\n

– \ube44\uc6a9\uc740 \uc591\uc758 \uc815\uc218\uc785\ub2c8\ub2e4.<\/p>\n<\/div>\n

\n

\ud574\uacb0 \uacfc\uc815<\/h2>\n

\uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574 \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d(Dynamic Programming) \ubc29\ubc95\uc744 \uc0ac\uc6a9\ud560 \uac83\uc785\ub2c8\ub2e4. \uc774 \ubc29\ubc95\uc740 \uc774\ubbf8 \uacc4\uc0b0\ub41c \uacb0\uacfc\ub97c \uc800\uc7a5\ud558\uc5ec \uc911\ubcf5 \uacc4\uc0b0\uc744 \ud53c\ud558\uace0 \ud6a8\uc728\uc131\uc744 \ub192\uc774\ub294 \uae30\ubc95\uc785\ub2c8\ub2e4.<\/p>\n

1\ub2e8\uacc4: \ubb38\uc81c \uc774\ud574\ud558\uae30<\/h3>\n

\ube44\uc6a9 \ubc30\uc5f4\uc774 \uc8fc\uc5b4\uc9c0\uba74, \uc6b0\ub9ac\ub294 \uccab \ubc88\uc9f8 \uc778\ub371\uc2a4\uc5d0\uc11c \uc885\ub8cc \uc9c0\uc810\uc73c\ub85c \uac00\ub294 \ucd5c\uc18c \ube44\uc6a9\uc744 \uacc4\uc0b0\ud569\ub2c8\ub2e4. \uac01 \uc778\ub371\uc2a4\uc5d0\uc11c \ub2e4\uc74c \uc778\ub371\uc2a4\ub85c \uac00\ub294 \ube44\uc6a9\uc744 \ub204\uc801\ud558\uc5ec \uc804\uccb4\uc801\uc778 \ube44\uc6a9\uc744 \uacc4\uc0b0\ud574\uc57c \ud569\ub2c8\ub2e4.<\/p>\n

2\ub2e8\uacc4: \ub3d9\uc801 \ud504\ub85c\uadf8\ub798\ubc0d \ud14c\uc774\ube14 \uc815\uc758\ud558\uae30<\/h3>\n

\uc6b0\ub9ac\ub294 dp<\/code>\ub77c\ub294 \ubc30\uc5f4\uc744 \uc815\uc758\ud560 \uac83\uc785\ub2c8\ub2e4. dp[i]<\/code>\ub294 \uc778\ub371\uc2a4 i<\/code>\uae4c\uc9c0\uc758 \ucd5c\uc18c \ube44\uc6a9\uc744 \uc800\uc7a5\ud569\ub2c8\ub2e4. \uccab \ubc88\uc9f8 \uc778\ub371\uc2a4\uc758 \ube44\uc6a9\uc740 \uadf8 \uc790\uccb4\uc774\ubbc0\ub85c dp[0]<\/code>\ub294 cost[0]<\/code>\ub85c \ucd08\uae30\ud654\ud569\ub2c8\ub2e4.<\/p>\n

3\ub2e8\uacc4: \ucd08\uae30 \uc0c1\ud0dc \uc124\uc815<\/h3>\n

\ucd08\uae30 \uc0c1\ud0dc\ub294 \uc544\ub798\uc640 \uac19\uc774 \uc124\uc815\ub429\ub2c8\ub2e4:<\/p>\n

let dp = new Array(cost.length);\ndp[0] = cost[0];<\/code><\/pre>\n
4\ub2e8\uacc4: \uc810\ud654\uc2dd \uad6c\uc131<\/h3>\n
\uc810\ud654\uc2dd\uc740 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:<\/p>\n
dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);<\/code><\/pre>\n
\uc989, \ud604\uc7ac \uc778\ub371\uc2a4 i<\/code>\uc5d0 \ub3c4\ub2ec\ud558\uae30 \uc704\ud55c \ube44\uc6a9\uc740 \ud604\uc7ac \uc778\ub371\uc2a4\uc758 \ube44\uc6a9\uacfc \uc774\uc804 \ub450 \uc778\ub371\uc2a4(\uc774\uc804 \uac12\uacfc \uadf8 \uc774\uc804 \uac12)\uc5d0\uc11c\uc758 \ucd5c\uc18c \ube44\uc6a9\uc758 \ud569\uc774 \ub429\ub2c8\ub2e4.<\/p>\n
5\ub2e8\uacc4: \uc804\uccb4 \ucf54\ub4dc \uc791\uc131<\/h3>\n
function minCost(cost) {\n    let n = cost.length;\n    if (n === 0) return 0;\n    if (n === 1) return cost[0];\n\n    let dp = new Array(n);\n    dp[0] = cost[0];\n    dp[1] = cost[1];\n\n    for (let i = 2; i < n; i++) {\n        dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);\n    }\n\n    return Math.min(dp[n - 1], dp[n - 2]);\n}\n\n\/\/ \uc0ac\uc6a9 \uc608\uc2dc:\nconsole.log(minCost([10, 15, 20])); \/\/ \ucd9c\ub825: 15<\/code><\/pre>\n
6\ub2e8\uacc4: \ucf54\ub4dc \ubd84\uc11d<\/h3>\n
\uc774 \ucf54\ub4dc\ub294 \ube44\uc6a9 \ubc30\uc5f4\uc758 \ud06c\uae30\uac00 1\uc77c \ub54c\uc640 0\uc77c \ub54c\ub97c \ucc98\ub9ac\ud558\ub294 \ucd08\uae30 \uc870\uac74\uc744 \ud3ec\ud568\ud558\uace0 \uc788\uc2b5\ub2c8\ub2e4. \uadf8 \ud6c4, \ubc18\ubcf5\ubb38\uc744 \ud1b5\ud574 \uac01 \uc778\ub371\uc2a4\uc5d0 \ub300\ud574 \ucd5c\uc18c \ube44\uc6a9\uc744 \uacc4\uc0b0\ud558\uba70, \ub9c8\uc9c0\ub9c9\uc5d0\ub294 \ucd5c\uc885\uc801\uc73c\ub85c \ucd5c\uc18c \ube44\uc6a9\uc744 \ubc18\ud658\ud569\ub2c8\ub2e4.<\/p>\n
7\ub2e8\uacc4: \uc2dc\uac04 \ubcf5\uc7a1\ub3c4<\/h3>\n
\uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(n)<\/code>\uc785\ub2c8\ub2e4. (n\uc740 \ube44\uc6a9 \ubc30\uc5f4\uc758 \uae38\uc774). \uac01 \uc778\ub371\uc2a4\ub97c \ud55c \ubc88\ub9cc \uc870\ud68c\ud558\ubbc0\ub85c \ud6a8\uc728\uc801\uc785\ub2c8\ub2e4.<\/p>\n
8\ub2e8\uacc4: \ucd94\uac00 \uc124\uba85<\/h3>\n
\uc774 \ubb38\uc81c\ub294 \uc2e4\uc0dd\ud65c\uc5d0\uc11c\ub3c4 \uc720\uc6a9\ud55c \uc54c\uace0\ub9ac\uc998\uc73c\ub85c, \uae38\uc744 \ucc3e\uac70\ub098 \ucd5c\ub2e8 \uacbd\ub85c\ub97c \uad6c\ud558\ub294 \ubb38\uc81c\uc5d0 \uc801\uc6a9\ub420 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc774\ub7ec\ud55c \uc6d0\ub9ac\ub97c \ub2e4\ub978 \ubcf5\uc7a1\ud55c \ubb38\uc81c\uc5d0 \ud655\uc7a5\ud558\uc5ec \ud65c\uc6a9\ud560 \uc218 \uc788\uc73c\uba70, \uc54c\uace0\ub9ac\uc998\uc5d0 \ub300\ud55c \uc774\ud574\ub3c4\ub97c \ub192\uc774\ub294 \ub370 \ub3c4\uc6c0\uc774 \ub429\ub2c8\ub2e4.<\/p>\n<\/div>\n