\n \uc8fc\uc5b4\uc9c4 \uc22b\uc790 \ubc30\uc5f4\uc758 \uad6c\uac04\uc5d0 \ud574\ub2f9\ud558\ub294 \uacf1\uc744 \uad6c\ud558\ub294 \ubb38\uc81c\uc785\ub2c8\ub2e4. \n \ubb38\uc81c\ub294 \ub2e4\uc74c\uacfc \uac19\uc2b5\ub2c8\ub2e4:\n <\/p>\n \n\uc785\ub825<\/strong>: <\/p>\n \ucd9c\ub825<\/strong>: \uac01 \uc6d0\uc18c\uc758 \uad6c\uac04\uc5d0 \ub300\ud55c \uacf1\uc744 \uad6c\ud558\uc5ec \ucd9c\ub825\ud558\ub77c.\n <\/p><\/blockquote>\n \n \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574 \uc6b0\uc120 \uc22b\uc790 \ubc30\uc5f4\uc758 \uad6c\uac04 \uacf1\uc744 \ud6a8\uc728\uc801\uc73c\ub85c \uad6c\ud558\ub294 \ubc29\ubc95\uc744 \uace0\ub824\ud574\uc57c \ud569\ub2c8\ub2e4. \n \uad6c\uac04 \uacf1\uc744 \ud6a8\uc728\uc801\uc73c\ub85c \uad6c\ud558\uae30 \uc704\ud574, \ub204\uc801\uacf1(Cumulative Product) \ubc30\uc5f4\uc744 \uc0ac\uc6a9\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \n \uc774 \uacbd\uc6b0, \uad6c\uac04 \uacf1\uc740 \ub2e4\uc74c\uacfc \uac19\uc774 \uad6c\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4:\n <\/p>\n \n \uc5ec\uae30\uc11c \n \ub2e4\ub9cc, \ubd80\ud638\uac00 \uc74c\uc218\uc77c \uacbd\uc6b0 \uc74c\uc218\uc640 \uc591\uc218\uc758 \uacf1\uc5d0 \ub530\ub77c \uacb0\uacfc\uac00 \ub2ec\ub77c\uc9c8 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \n \uad6c\uac04 \ub0b4\uc5d0 \ud3ec\ud568\ub41c \uc74c\uc218\uc758 \uac1c\uc218\uac00 \ud640\uc218\uc774\uba74 \uacb0\uacfc\uac00 \uc74c\uc218\ub85c, \uc9dd\uc218\uc774\uba74 \uc591\uc218\ub85c \ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \n \uc704\uc758 \uc811\uadfc \ubc29\ubc95\uc744 \uace0\ub824\ud558\uc5ec \ucf54\ud2c0\ub9b0\uc73c\ub85c \ucf54\ub4dc\ub97c \uad6c\ud604\ud574\ubcf4\ub3c4\ub85d \ud558\uaca0\uc2b5\ub2c8\ub2e4.\n <\/p>\n \n \uc774\uc5b4\uc11c \uad6c\uac04 \uacf1\uc744 \ubc18\ud658\ud558\ub294 \ud568\uc218\ub97c \uc791\uc131\ud558\uaca0\uc2b5\ub2c8\ub2e4.\n <\/p>\n \n \ub9c8\uc9c0\ub9c9\uc73c\ub85c, \uc804\uccb4 \uc54c\uace0\ub9ac\uc998\uc744 \uacb0\ud569\ud574\ubcf4\uaca0\uc2b5\ub2c8\ub2e4.\n <\/p>\n \n – \uc2dc\uac04 \ubcf5\uc7a1\ub3c4: \n \uc774\ub7ec\ud55c \ubc29\ubc95\uc744 \ud1b5\ud574 \ubb38\uc81c\ub97c \ud6a8\uc728\uc801\uc73c\ub85c \ud574\uacb0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \n \uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 \uad6c\uac04 \uacf1 \uad6c\ud558\uae30 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574 \ub204\uc801\uacf1 \ubc30\uc5f4\uc744 \uc0ac\uc6a9\ud558\uc5ec \ud6a8\uc728\uc801\uc778 \uc54c\uace0\ub9ac\uc998\uc744 \uad6c\ud604\ud558\uc600\uc2b5\ub2c8\ub2e4. \n \ucd94\uac00\uc801\uc778 \uc9c8\ubb38\uc774\ub098 \uad81\uae08\ud55c \uc810\uc774 \uc788\uc73c\uc2dc\uba74 \ub313\uae00\uc744 \ud1b5\ud574 \ubb38\uc758\ud574\uc8fc\uc2dc\uae30 \ubc14\ub78d\ub2c8\ub2e4. \uac10\uc0ac\ud569\ub2c8\ub2e4!\n <\/p>\n <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"
\n \uc608\ub97c \ub4e4\uc5b4, \uc22b\uc790 \ubc30\uc5f4 [2, 3, 4, 5]<\/code>\uac00 \uc8fc\uc5b4\uc84c\uc744 \ub54c,
\n \uad6c\uac04 [1, 3]<\/code>\uc5d0 \ud574\ub2f9\ud558\ub294 \uacf1\uc740 3 * 4 * 5<\/code>\uc774\uba70, \uacb0\uacfc\ub294 60<\/code>\uc785\ub2c8\ub2e4.\n <\/p>\n\n
n<\/code> : \uc815\uc218 \ubc30\uc5f4\uc758 \ud06c\uae30 (1 \u2264 n<\/code> \u2264 105<\/sup>)<\/li>\narr<\/code> : \ud06c\uae30 n<\/code>\uc758 \ubc30\uc5f4 (1 \u2264 arr[i]<\/code> \u2264 1000)<\/li>\nm<\/code> : \uad6c\uac04 \uc694\uccad\uc758 \uac1c\uc218 (1 \u2264 m<\/code> \u2264 105<\/sup>)<\/li>\n[l, r]<\/code> (1 \u2264 l<\/code> \u2264 r<\/code> \u2264 n<\/code>)<\/li>\n<\/ul>\n\ubb38\uc81c \uc811\uadfc \ubc29\ubc95<\/h2>\n
\n \ub2e8\uc21c\ud788 \uad6c\uac04 [l, r]<\/code>\uc5d0 \ub300\ud574 \uacf1\uc744 \uad6c\ud558\ub824\uace0 \ud558\uba74, \ucd5c\uc545\uc758 \uacbd\uc6b0 \uc2dc\uac04\ubcf5\uc7a1\ub3c4\uac00 O(n * m)\uc774 \ub418\uc5b4 \uc131\ub2a5\uc774 \ub5a8\uc5b4\uc9c8 \uc218 \uc788\uc2b5\ub2c8\ub2e4.
\n \ub530\ub77c\uc11c, \uc120\ud615 \uc2dc\uac04 \uc774\ub0b4\uc5d0 \uacb0\uacfc\ub97c \ub3c4\ucd9c\ud560 \uc218 \uc788\ub294 \ubc29\ubc95\uc744 \ucc3e\uc544\uc57c \ud569\ub2c8\ub2e4.\n <\/p>\n1. \ub204\uc801\uacf1 \ubc30\uc5f4<\/h3>\n
\n array\uc758 i\ubc88\uc9f8 \uc6d0\uc18c\uae4c\uc9c0\uc758 \uacf1\uc744 \uc800\uc7a5\ud558\uc5ec, \uad6c\uac04 \uacf1\uc740 \ub2e4\uc74c\uacfc \uac19\uc774 \uacc4\uc0b0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\ncumulativeProduct[i] = arr[0] * arr[1] * ... * arr[i]<\/code><\/pre>\nproduct(l, r) = cumulativeProduct[r] \/ cumulativeProduct[l-1]<\/code><\/pre>\ncumulativeProduct[0]<\/code>\uc740 1\ub85c \ucd08\uae30\ud654\ub429\ub2c8\ub2e4. \uc774\ub97c \ud1b5\ud574 \uc6b0\ub9ac\ub294 \uc120\ud615 \uc2dc\uac04 O(n)\uc73c\ub85c \ub204\uc801\uacf1 \ubc30\uc5f4\uc744 \uc0dd\uc131\ud55c \ud6c4,
\n \uac01 \ucffc\ub9ac\uc5d0 \ub300\ud574 O(1)\ub85c \uad6c\uac04 \uacf1\uc744 \uacc4\uc0b0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n2. \uc74c\uc218 \ucc98\ub9ac<\/h3>\n
\n \uc774\ub7ec\ud55c \uacbd\uc6b0\uc5d0\ub294 \uc74c\uc218\uc758 \uac1c\uc218\ub97c \ud30c\uc545\ud558\uc5ec \uacb0\uacfc\ub97c \uc870\uc815\ud574\uc57c \ud569\ub2c8\ub2e4.\n <\/p>\n
\n \uc774 \uacbd\uc6b0, \ucd94\uac00\uc801\uc73c\ub85c \uc74c\uc218\ub97c \uc120\ud0dd\ud558\uc5ec \ucd5c\ub300 \uacf1\uc744 \uad6c\ud558\ub294 \ub85c\uc9c1\uc774 \ud544\uc694\ud574\uc9c8 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n\uad6c\ud604 \ucf54\ub4dc<\/h2>\n
fun getCumulativeProducts(arr: IntArray): IntArray {\n val n = arr.size\n val cumulativeProduct = IntArray(n)\n cumulativeProduct[0] = arr[0]\n \n for (i in 1 until n) {\n cumulativeProduct[i] = cumulativeProduct[i - 1] * arr[i]\n }\n \n return cumulativeProduct\n}<\/code><\/pre>\nfun rangeProduct(cumulativeProduct: IntArray, l: Int, r: Int): Int {\n if (l == 0) return cumulativeProduct[r]\n return cumulativeProduct[r] \/ cumulativeProduct[l - 1]\n}<\/code><\/pre>\nfun main() {\n val arr = intArrayOf(2, 3, 4, 5)\n val cumulativeProduct = getCumulativeProducts(arr)\n val queries = listOf(Pair(1, 3), Pair(0, 2))\n\n for (query in queries) {\n val (l, r) = query\n val result = rangeProduct(cumulativeProduct, l, r)\n println(\"\uad6c\uac04 ($l, $r)\uc758 \uacf1: $result\")\n }\n}<\/code><\/pre>\n\ubcf5\uc7a1\ub3c4 \ubd84\uc11d<\/h2>\n
O(n + m)<\/code> (\uc5ec\uae30\uc11c n<\/code>\uc740 \ubc30\uc5f4\uc758 \ud06c\uae30, m<\/code>\uc740 \uc694\uccad\uc758 \uc218)
\n
\n – \uacf5\uac04 \ubcf5\uc7a1\ub3c4: O(n)<\/code> (\ub204\uc801\uacf1 \ubc30\uc5f4\uc744 \uc800\uc7a5\ud558\uae30 \uc704\ud55c \uacf5\uac04)\n <\/p>\n
\n \ub204\uc801\uacf1 \ubc30\uc5f4\uc744 \uc774\uc6a9\ud558\uba74 \uacf1\uc744 \ud55c \ubc88\uc5d0 \uacc4\uc0b0\ud560 \uc218 \uc788\uc5b4 \uac01 \ucffc\ub9ac\uc5d0 \ub300\ud574 \ube60\ub974\uac8c \uacb0\uacfc\ub97c \ub3c4\ucd9c\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n\uacb0\ub860<\/h2>\n
\n \uc774\ub7ec\ud55c \uc811\uadfc\ubc95\uc740 \ub2e4\uc591\ud55c \ubc30\uc5f4 \ubb38\uc81c\ub97c \ub2e4\ub8e8\ub294 \ub370 \uc720\uc6a9\ud558\uac8c \uc0ac\uc6a9\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n