\ubb38\uc81c \uc124\uba85<\/h2>\n
\n \uc8fc\uc5b4\uc9c0\ub294 \uc815\uc218 \ubc30\uc5f4 \n – \uccab \ubc88\uc9f8 \ucffc\ub9ac (0, 2): arr[0] + arr[1] + arr[2] = 1 + 2 + 3 = 6 \n \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574 \uba3c\uc800 \ubc30\uc5f4\uc758 \ubd80\ubd84 \ud569\uc744 \ud6a8\uc728\uc801\uc73c\ub85c \uad6c\ud560 \uc218 \uc788\ub294 \ubc29\ubc95\uc744 \uace0\ubbfc\ud574\uc57c \ud569\ub2c8\ub2e4. \n \ubd80\ubd84 \ud569 \ubc30\uc5f4 \n \uc704\uc758 \ucf54\ub4dc\uc5d0\uc11c, \n \ubd80\ubd84 \ud569 \ubc30\uc5f4\uc744 \uc0dd\uc131\ud55c \ud6c4, \uac01 \ucffc\ub9ac\uc5d0 \ub300\ud574 \ubd80\ubd84 \ud569\uc744 \uacc4\uc0b0\ud558\ub294 \ud568\uc218\ub3c4 \uc791\uc131\ud569\ub2c8\ub2e4. \n \n \uc704\uc758 \ubaa8\ub4e0 \ub0b4\uc6a9\uc744 \uc885\ud569\ud558\uc5ec \uc804\uccb4 \ucf54\ub4dc\ub97c \uc791\uc131\ud574 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4.\n <\/p>\n \n \uc704\uc758 \ucf54\ub4dc\uc5d0\uc11c\ub294 \ubc30\uc5f4\uacfc \ucffc\ub9ac\ub97c \ud3ec\ud568\ud558\ub294 \uc785\ub825\uc744 \ubc1b\uc544\uc11c \ubd80\ubd84 \ud569 \ucffc\ub9ac\ub97c \uc2e4\ud589\ud558\uace0 \n \ud604\uc7ac \uc54c\uace0\ub9ac\uc998\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub294 O(N + M)\uc73c\ub85c \ub9e4\uc6b0 \ud6a8\uc728\uc801\uc785\ub2c8\ub2e4. \n \uc774\ub7ec\ud55c \uc790\ub8cc\uad6c\uc870\ub294 \ub3d9\uc801 \uc5c5\ub370\uc774\ud2b8\uc640 \ucffc\ub9ac \uc5f0\uc0b0\uc744 \ub3d9\uc2dc\uc5d0 \uc9c0\uc6d0\ud560 \uc218 \uc788\uc5b4 \uc2e4\uc2dc\uac04\uc73c\ub85c \n \uc774\ubc88 \uac15\uc88c\ub97c \ud1b5\ud574 \uae30\ubcf8\uc801\uc778 \uad6c\uac04 \ud569 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\ub294 \ubc29\ubc95\uc5d0 \ub300\ud574 \uc54c\uc544\ubcf4\uc558\uc2b5\ub2c8\ub2e4. \n \ub3c5\uc790 \uc5ec\ub7ec\ubd84\ub4e4\uc774 \uc790\uc2e0\ub9cc\uc758 \ubb38\uc81c \ud574\uacb0 \ubc29\ubc95\uacfc \ud6a8\uc728\uc801\uc778 \uc54c\uace0\ub9ac\uc998\uc744 \uac1c\ubc1c\ud558\ub294 \ub370 <\/body><\/p>\n","protected":false},"excerpt":{"rendered":"arr<\/code>\uc640 \ucffc\ub9ac \ubc30\uc5f4 queries<\/code>\uac00 \uc788\ub2e4. arr<\/code>\uc758 \uac01 \ucffc\ub9ac\ub294
\n \ub450 \uac1c\uc758 \uc778\ub371\uc2a4\ub85c \uc774\ub8e8\uc5b4\uc838 \uc788\uc73c\uba70, \uc774 \uc778\ub371\uc2a4\ub97c \ud1b5\ud574 arr<\/code>\uc758 \ubd80\ubd84 \ubc30\uc5f4\uc758 \ud569\uc744 \uad6c\ud574\uc57c \ud55c\ub2e4.
\n \uac01 \ucffc\ub9ac\ub294 (\uc2dc\uc791 \uc778\ub371\uc2a4, \ub05d \uc778\ub371\uc2a4) \ud615\ud0dc\ub85c \uc81c\uacf5\ub418\uba70, \ubd80\ubd84 \ubc30\uc5f4\uc758 \ud569\uc744 \ube60\ub974\uac8c \uacc4\uc0b0\ud560 \uc218 \uc788\ub294 \ubc29\ubc95\uc744
\n \uad6c\ud604\ud574\uc57c \ud55c\ub2e4.\n <\/p>\n\uc785\ub825<\/h3>\n
\n
arr<\/code>: \uae38\uc774\ub294 N (1 \u2264 N \u2264 100,000)<\/li>\nqueries<\/code>: \uae38\uc774\ub294 M (1 \u2264 M \u2264 100,000), \uac01 \uc6d0\uc18c\ub294 (x, y) \ud615\ud0dc\ub85c \uc8fc\uc5b4\uc9d0<\/li>\n<\/ul>\n\ucd9c\ub825<\/h3>\n
\n
queries<\/code>\uc758 \uac01 \ucffc\ub9ac\uc5d0 \ub300\ud55c \ubd80\ubd84 \ubc30\uc5f4\uc758 \ud569\uc744 \ubc30\uc5f4\ub85c \ubc18\ud658<\/li>\n<\/ul>\n<\/section>\n\uc608\uc81c<\/h2>\n
\uc785\ub825<\/h3>\n
\narr = [1, 2, 3, 4, 5]\nqueries = [(0, 2), (1, 3), (2, 4)]\n <\/code><\/pre>\n\ucd9c\ub825<\/h3>\n
\n[6, 9, 12]\n <\/code><\/pre>\n\uc124\uba85<\/h3>\n
\n – \ub450 \ubc88\uc9f8 \ucffc\ub9ac (1, 3): arr[1] + arr[2] + arr[3] = 2 + 3 + 4 = 9
\n – \uc138 \ubc88\uc9f8 \ucffc\ub9ac (2, 4): arr[2] + arr[3] + arr[4] = 3 + 4 + 5 = 12\n <\/p>\n<\/section>\n\ubb38\uc81c \ud574\uacb0 \uacfc\uc815<\/h2>\n
\n \uac01 \ucffc\ub9ac\uac00 O(N) \uc2dc\uac04\uc5d0 \ucc98\ub9ac\ub41c\ub2e4\uba74 \uc804\uccb4 \ucffc\ub9ac\ub97c \ucc98\ub9ac\ud558\ub294 \ub370 O(N * M) \uc2dc\uac04\uc774 \uc18c\uc694\ub418\uc5b4 \ub9e4\uc6b0 \ube44\ud6a8\uc728\uc801\uc785\ub2c8\ub2e4.
\n \ub530\ub77c\uc11c \ubd80\ubd84 \ud569\uc744 \ubbf8\ub9ac \uacc4\uc0b0\ud574 \ub450\uace0 \uc0ac\uc6a9\ud558\ub294 \ubc29\ubc95\uc744 \uace0\ub824\ud574\uc57c \ud569\ub2c8\ub2e4.\n <\/p>\n1. \ubd80\ubd84 \ud569 \ubc30\uc5f4 \ub9cc\ub4e4\uae30<\/h3>\n
prefixSum<\/code>\uc744 \ub9cc\ub4e4\uc5b4\ubcf4\uaca0\uc2b5\ub2c8\ub2e4. prefixSum[i]<\/code>\ub294 arr[0] + arr[1] + ... + arr[i]<\/code>\ub97c \uc758\ubbf8\ud569\ub2c8\ub2e4.
\n \uc774\ub97c \ud1b5\ud574, \uc8fc\uc5b4\uc9c4 \ucffc\ub9ac\uc758 \uc2dc\uc791 \uc778\ub371\uc2a4\uc640 \ub05d \uc778\ub371\uc2a4\ub97c \uc774\uc6a9\ud558\uc5ec \uac04\ub2e8\ud788 \ubd80\ubd84 \ud569\uc744 \uacc4\uc0b0\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n\nfunc createPrefixSum(arr: [Int]) -> [Int] {\n var prefixSum = [Int](repeating: 0, count: arr.count)\n prefixSum[0] = arr[0]\n\n for i in 1..createPrefixSum<\/code> \ud568\uc218\ub294 \uc785\ub825 \ubc30\uc5f4 arr<\/code>\ub97c \ubc1b\uc544 \ubd80\ubd84 \ud569 \ubc30\uc5f4\uc744 \uc0dd\uc131\ud558\uc5ec \ubc18\ud658\ud569\ub2c8\ub2e4.\n <\/p>\n2. \ucffc\ub9ac\uc5d0 \ub300\ud55c \ubd80\ubd84 \ud569 \uacc4\uc0b0<\/h3>\n
\n \uc8fc\uc5b4\uc9c4 \ucffc\ub9ac (x, y)\uc5d0\uc11c \ubd80\ubd84 \ud569\uc740 prefixSum[y]<\/code>\uc5d0\uc11c prefixSum[x - 1]<\/code>\ub97c \ube7c\uba74 \uad6c\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n\nfunc rangeSum(prefixSum: [Int], queries: [(Int, Int)]) -> [Int] {\n var result = [Int]()\n\n for query in queries {\n let x = query.0\n let y = query.1\n let sum = prefixSum[y] - (x > 0 ? prefixSum[x - 1] : 0)\n result.append(sum)\n }\n \n return result\n}\n <\/code><\/pre>\nrangeSum<\/code> \ud568\uc218\ub294 \ubd80\ubd84 \ud569 \ubc30\uc5f4\uacfc \ucffc\ub9ac \ubc30\uc5f4\uc744 \ubc1b\uc544 \uac01 \ucffc\ub9ac\uc758 \ubd80\ubd84 \ud569\uc744 \uacc4\uc0b0\ud558\uc5ec \ubc18\ud658\ud569\ub2c8\ub2e4.
\n result<\/code> \ubc30\uc5f4\uc5d0 \uac01 \ucffc\ub9ac\uc758 \uacb0\uacfc\ub97c \uc800\uc7a5\ud55c \ud6c4, \ub9c8\uc9c0\ub9c9\uc5d0 \ubc18\ud658\ud569\ub2c8\ub2e4.\n <\/p>\n3. \uc804\uccb4 \uad6c\ud604<\/h3>\n
\nfunc rangeSumQueries(arr: [Int], queries: [(Int, Int)]) -> [Int] {\n let prefixSum = createPrefixSum(arr: arr)\n return rangeSum(prefixSum: prefixSum, queries: queries)\n}\n\n\/\/ \uc608\uc81c \uc0ac\uc6a9\nlet arr = [1, 2, 3, 4, 5]\nlet queries = [(0, 2), (1, 3), (2, 4)]\nlet results = rangeSumQueries(arr: arr, queries: queries)\nprint(results) \/\/ [6, 9, 12]\n <\/code><\/pre>\n
\n \uacb0\uacfc\ub97c \ucd9c\ub825\ud569\ub2c8\ub2e4. print(results)<\/code>\ub97c \ud1b5\ud574 \uacb0\uacfc\ub97c \ud655\uc778\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n<\/section>\n\ucd5c\uc801\ud654 \ubc0f \ubcc0\ud615<\/h2>\n
\n \uadf8\ub7ec\ub098 \uc774 \uc678\uc5d0\ub3c4 \ub354 \ub9ce\uc740 \ubcc0\ud615 \ubc0f \ucd5c\uc801\ud654\ub97c \uace0\ub824\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \uc608\ub97c \ub4e4\uc5b4, \uad6c\uac04 \ud569\uc758
\n \uc5f0\uc0b0\ubfd0\ub9cc \uc544\ub2c8\ub77c \uc5c5\ub370\uc774\ud2b8\ub3c4 \uac00\ub2a5\ud558\ub3c4\ub85d \uad6c\ud604\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.
\n \uc774\ub294 Fenwick Tree(\ub610\ub294 Binary Indexed Tree)\ub098 Segment Tree\uc640 \uac19\uc740 \uace0\uae09 \uc790\ub8cc\uad6c\uc870\ub97c
\n \uc0ac\uc6a9\ud558\uc5ec \uc218\ud589\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.\n <\/p>\n
\n \ub370\uc774\ud130\uc758 \ubcc0\ud654\ub97c \ubc18\uc601\ud560 \uc218 \uc788\uac8c \ud574\uc90d\ub2c8\ub2e4.
\n \uc774\ub97c \ud1b5\ud574 \uc880 \ub354 \ubcf5\uc7a1\ud55c \ubb38\uc81c\ub97c \ud574\uacb0\ud560 \uc218 \uc788\ub294 \uae30\ubc18\uc744 \uc81c\uacf5\ud569\ub2c8\ub2e4.\n <\/p>\n<\/section>\n\uacb0\ub860<\/h2>\n
\n \ubd80\ubd84 \ud569 \ubc30\uc5f4\uc744 \ud65c\uc6a9\ud558\uc5ec \ud6a8\uc728\uc801\uc73c\ub85c \ubb38\uc81c\ub97c \ud574\uacb0\ud560 \uc218 \uc788\uc5c8\uc73c\uba70,
\n \uc774\ub97c \ud1b5\ud574 \ucd5c\uc801\ud654\ub41c \ucf54\ub4dc\ub97c \uc791\uc131\ud558\ub294 \ub370 \ud544\uc694\ud55c \uae30\ucd08\ub97c \ub2e4\uc84c\uc2b5\ub2c8\ub2e4.
\n \ub2e4\uc74c \uac15\uc88c\uc5d0\uc11c\ub294 \ub354 \ubcf5\uc7a1\ud55c \ubb38\uc81c\ub098 \uace0\uae09 \uc790\ub8cc\uad6c\uc870\ub97c \ud65c\uc6a9\ud55c \ubb38\uc81c \ud574\uacb0 \ubc29\ubc95\uc5d0 \ub300\ud574
\n \ub2e4\ub8f0 \uc608\uc815\uc785\ub2c8\ub2e4.\n <\/p>\n
\n \ub9ce\uc740 \ub3c4\uc6c0\uc774 \ub418\uc5c8\uae30\ub97c \ubc14\ub78d\ub2c8\ub2e4. \uac10\uc0ac\ud569\ub2c8\ub2e4.\n <\/p>\n<\/section>\n<\/article>\n