{"id":28518,"date":"2024-10-27T16:11:54","date_gmt":"2024-10-27T16:11:54","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=28518"},"modified":"2024-11-26T07:01:35","modified_gmt":"2024-11-26T07:01:35","slug":"%ec%bd%94%ed%8b%80%eb%a6%b0-%ec%bd%94%eb%94%a9%ed%85%8c%ec%8a%a4%ed%8a%b8-%ea%b0%95%ec%a2%8c-%ec%97%b0%ec%86%8d-%ed%95%a9-%ea%b5%ac%ed%95%98%ea%b8%b0","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/28518\/","title":{"rendered":"\ucf54\ud2c0\ub9b0 \ucf54\ub529\ud14c\uc2a4\ud2b8 \uac15\uc88c, \uc5f0\uc18d \ud569 \uad6c\ud558\uae30"},"content":{"rendered":"

<\/p>\n

\n

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

\n \uc8fc\uc5b4\uc9c4 \uc815\uc218 \ubc30\uc5f4 arr<\/code>\uac00 \uc788\uc744 \ub54c, \uc5f0\uc18d\ub41c \ubd80\ubd84 \ubc30\uc5f4\uc758 \ud569 \uc911 \ucd5c\ub300 \uac12\uc744 \uad6c\ud558\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4.
\n \uc989, arr<\/code>\uc758 \uc5f0\uc18d\ub41c \uba87 \uac1c\uc758 \uc22b\uc790\ub97c \ub354\ud588\uc744 \ub54c \uac00\uc7a5 \ud070 \uac12\uc774 \ubb34\uc5c7\uc778\uc9c0 \ucc3e\uc544\uc57c \ud569\ub2c8\ub2e4.
\n \uc774 \ubb38\uc81c\ub294 \uc790\uc8fc \ucd9c\uc81c\ub418\ub294 \ucf54\ub529 \ud14c\uc2a4\ud2b8 \ubb38\uc81c \uc911 \ud558\ub098\uc774\uba70, Kadane\uc758 \uc54c\uace0\ub9ac\uc998\uc744 \uc0ac\uc6a9\ud558\uc5ec \ud574\uacb0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n

\ubb38\uc81c \uc608\uc2dc<\/h2>\n

\uc785\ub825<\/h3>\n
[2, -1, 3, 4, -2, 1, -5, 4]<\/code><\/pre>\n
\ucd9c\ub825<\/h3>\n
10<\/code><\/pre>\n
\uc124\uba85: \uc5f0\uc18d\ub41c \ubd80\ubd84 \ubc30\uc5f4 [3, 4, -2, 1]\uc758 \ud569\uc774 \ucd5c\ub300\uc778 10\uc785\ub2c8\ub2e4.<\/p>\n
\ubb38\uc81c \uc811\uadfc \ubc29\ubc95<\/h2>\n
\n            \uc774 \ubb38\uc81c\ub294 \uc5f0\uc18d\ub41c \ubd80\ubd84 \ubc30\uc5f4\uc758 \ud569\uc744 \uad6c\ud558\ub294 \uac83\uc774\uae30 \ub54c\ubb38\uc5d0 \ubc94\uc704\ub97c \uc5b4\ub5bb\uac8c \uc124\uc815\ud560\uc9c0\uac00 \uad00\uac74\uc785\ub2c8\ub2e4.
\n            \uc989, \uc2dc\uc791 \uc9c0\uc810\uacfc \ub05d \uc9c0\uc810\uc744 \uc815\ud558\uace0 \uadf8 \uc0ac\uc774\uc758 \ubaa8\ub4e0 \uc6d0\uc18c\ub97c \ub354\ud558\ub294 \ubc29\uc2dd\uc73c\ub85c \uc811\uadfc\ud560 \uc218 \uc788\uc9c0\ub9cc,
\n            \uc774 \ubc29\ubc95\uc740 \ube44\ud6a8\uc728\uc801\uc785\ub2c8\ub2e4. \ub300\uc2e0, Kadane\uc758 \uc54c\uace0\ub9ac\uc998\uc744 \ud65c\uc6a9\ud558\uc5ec O(n) \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub85c \ud574\uacb0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n        <\/p>\n
Kadane\uc758 \uc54c\uace0\ub9ac\uc998<\/h3>\n
\n            Kadane\uc758 \uc54c\uace0\ub9ac\uc998\uc740 \ud604\uc7ac\uae4c\uc9c0\uc758 \ucd5c\ub300 \uc5f0\uc18d \ud569\uacfc \ud604\uc7ac \uc704\uce58\uc758 \uac12\uc744 \ube44\uad50\ud558\uc5ec \ucd5c\ub300\uac12\uc744 \uac31\uc2e0\ud558\ub294 \ubc29\uc2dd\uc73c\ub85c \uc791\ub3d9\ud569\ub2c8\ub2e4.
\n            \uad6c\uccb4\uc801\uc778 \uacfc\uc815\uc740 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:\n        <\/p>\n
    \n
  1. \ubcc0\uc218 maxSoFar<\/code>\uc640 maxEndingHere<\/code>\ub97c \ucd08\uae30\ud654\ud569\ub2c8\ub2e4. \ub458 \ub2e4 0 \ub610\ub294 \ubc30\uc5f4\uc758 \uccab \ubc88\uc9f8 \uc694\uc18c\ub85c \ucd08\uae30\ud654\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/li>\n
  2. \ubc30\uc5f4\uc744 \uc21c\ud68c\ud558\uba70 \ud604\uc7ac \uac12 arr[i]<\/code>\ub97c maxEndingHere<\/code>\uc5d0 \ub354\ud569\ub2c8\ub2e4.<\/li>\n
  3. maxEndingHere<\/code>\uac00 maxSoFar<\/code>\ubcf4\ub2e4 \ud06c\uba74 maxSoFar<\/code>\ub97c \uac31\uc2e0\ud569\ub2c8\ub2e4.<\/li>\n
  4. \ub9cc\uc57d maxEndingHere<\/code>\uac00 0\ubcf4\ub2e4 \uc791\uc544\uc9c0\uba74 0\uc73c\ub85c \ucd08\uae30\ud654\ud558\uc5ec \uc0c8\ub85c\uc6b4 \uc5f0\uc18d \ud569\uc744 \uc2dc\uc791\ud569\ub2c8\ub2e4.<\/li>\n<\/ol>\n
    \n            \uc774 \ubc29\ubc95\uc740 \ubc30\uc5f4 \ud06c\uae30\uc640 \uad00\uacc4\uc5c6\uc774 O(n) \uc2dc\uac04 \ub0b4\uc5d0 \ucd5c\ub300 \ud569\uc744 \uad6c\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n        <\/p>\n
    \ucf54\ud2c0\ub9b0 \ucf54\ub4dc \uad6c\ud604<\/h2>\n
    \n            \ub2e4\uc74c\uc740 \uc704\uc758 \uc54c\uace0\ub9ac\uc998\uc744 \ucf54\ud2c0\ub9b0\uc73c\ub85c \uad6c\ud604\ud55c \ucf54\ub4dc\uc785\ub2c8\ub2e4:\n        <\/p>\n
    \nfun maxSubArraySum(arr: IntArray): Int {\n    var maxSoFar = arr[0]\n    var maxEndingHere = arr[0]\n\n    for (i in 1 until arr.size) {\n        maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i])\n        maxSoFar = Math.max(maxSoFar, maxEndingHere)\n    }\n\n    return maxSoFar\n}\n\nfun main() {\n    val arr = intArrayOf(2, -1, 3, 4, -2, 1, -5, 4)\n    val result = maxSubArraySum(arr)\n    println(\"\ucd5c\ub300 \uc5f0\uc18d \ud569: $result\")\n}\n        <\/code><\/pre>\n
    \uc704 \ucf54\ub4dc\ub294 \uc8fc\uc5b4\uc9c4 \uc815\uc218 \ubc30\uc5f4\uc5d0\uc11c \ucd5c\ub300 \uc5f0\uc18d \ud569\uc744 \uad6c\ud558\ub294 \ud568\uc218 maxSubArraySum<\/code>\uc744 \uc815\uc758\ud569\ub2c8\ub2e4.<\/p>\n
    \uc2dc\uac04 \ubcf5\uc7a1\ub3c4 \ubd84\uc11d<\/h2>\n
    \n            Kadane\uc758 \uc54c\uace0\ub9ac\uc998\uc740 \ud55c \ubc88\uc758 \ubc30\uc5f4 \uc21c\ud68c\ub97c \ud1b5\ud574 \uacb0\uacfc\ub97c \ub3c4\ucd9c\ud558\uae30 \ub54c\ubb38\uc5d0 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(n)\uc785\ub2c8\ub2e4.
    \n            \ub530\ub77c\uc11c \ubc30\uc5f4\uc758 \ud06c\uae30\uac00 \ucee4\uc838\ub3c4 \uc131\ub2a5\uc5d0 \ud070 \uc601\ud5a5\uc744 \ubbf8\uce58\uc9c0 \uc54a\uc2b5\ub2c8\ub2e4. \uacf5\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(1)\uc774\uba70 \ucd94\uac00 \ub370\uc774\ud130 \uad6c\uc870\ub97c \uc0ac\uc6a9\ud558\uc9c0 \uc54a\uae30 \ub54c\ubb38\uc5d0 \ub9e4\uc6b0 \ud6a8\uc728\uc801\uc785\ub2c8\ub2e4.\n        <\/p>\n
    \uacb0\ub860<\/h2>\n
    \n            \uc5f0\uc18d \ud569 \uad6c\ud558\uae30 \ubb38\uc81c\ub294 \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c \ud480\uc774\uc5d0\uc11c \ube48\ubc88\ud788 \ub4f1\uc7a5\ud558\ub294 \ubb38\uc81c\ub85c,
    \n            Kadane\uc758 \uc54c\uace0\ub9ac\uc998\uc744 \ud1b5\ud574 \ud6a8\uc728\uc801\uc73c\ub85c \ud574\uacb0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc774\ub97c \ud1b5\ud574 \ucf54\ud2c0\ub9b0\uc758 \uae30\ubcf8 \ubb38\ubc95\uacfc \uc54c\uace0\ub9ac\uc998 \uc124\uacc4\ub97c \ub3d9\uc2dc\uc5d0 \ud559\uc2b5\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.
    \n            \ucf54\ub529 \ud14c\uc2a4\ud2b8\uc5d0\uc11c \uc885\uc885 \ucd9c\uc81c\ub418\ub294 \ubb38\uc81c\uc774\ubbc0\ub85c \uc5f0\uc2b5\ud558\uc5ec \uc790\uc5f0\uc2a4\ub7fd\uac8c \uad6c\ud604\ud560 \uc218 \uc788\ub3c4\ub85d \ud558\uc2ed\uc2dc\uc624.\n        <\/p>\n
    \ucd94\uac00 \uc5f0\uc2b5 \ubb38\uc81c<\/h2>\n
    \ub2e4\uc74c\uc758 \ubcc0\ud615 \ubb38\uc81c\ub4e4\uc744 \ud1b5\ud574 \ucd94\uac00\uc801\uc778 \uc5f0\uc2b5\uc744 \ud574\ubcf4\uc138\uc694:<\/p>\n