{"id":26726,"date":"2024-10-27T11:52:12","date_gmt":"2024-10-27T11:52:12","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=26726"},"modified":"2024-11-26T07:31:51","modified_gmt":"2024-11-26T07:31:51","slug":"%ec%9e%90%eb%b0%94-%ec%bd%94%eb%94%a9%ed%85%8c%ec%8a%a4%ed%8a%b8-%ea%b0%95%ec%a2%8c-%ea%b5%ac%ea%b0%84-%ed%95%a9","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/26726\/","title":{"rendered":"\uc790\ubc14 \ucf54\ub529\ud14c\uc2a4\ud2b8 \uac15\uc88c, \uad6c\uac04 \ud569"},"content":{"rendered":"

<\/p>\n

\uc548\ub155\ud558\uc138\uc694! \uc774\ubc88 \ud3ec\uc2a4\ud305\uc5d0\uc11c\ub294 \uc790\ubc14\ub97c \ud65c\uc6a9\ud55c \ucf54\ub529\ud14c\uc2a4\ud2b8 \uc900\ube44\ub97c \uc704\ud55c \uad6c\uac04 \ud569 \ubb38\uc81c\ub97c \ub2e4\ub8e8\uc5b4 \ubcf4\uaca0\uc2b5\ub2c8\ub2e4. \uad6c\uac04 \ud569 \ubb38\uc81c\ub294 \uc8fc\uc5b4\uc9c4 \ubc30\uc5f4\uc758 \ud2b9\uc815 \uad6c\uac04\uc5d0 \uc788\ub294 \uc6d0\uc18c\ub4e4\uc758 \ud569\uc744 \ud6a8\uc728\uc801\uc73c\ub85c \uad6c\ud558\ub294 \ubb38\uc81c\ub85c, \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\uc5d0\uc11c \uc790\uc8fc \ucd9c\uc81c\ub418\ub294 \uc720\ud615\uc785\ub2c8\ub2e4.<\/p>\n

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

\ubc30\uc5f4 A<\/code>\uac00 \uc8fc\uc5b4\uc84c\uc744 \ub54c, Q<\/code>\uac1c\uc758 \ucffc\ub9ac\uac00 \uc788\uc2b5\ub2c8\ub2e4. \uac01 \ucffc\ub9ac\ub294 \ub450 \uc815\uc218 L<\/code>\uacfc R<\/code>\ub85c \uc774\ub8e8\uc5b4\uc838 \uc788\uc73c\uba70, \uc774\ub4e4\uc740 \ubc30\uc5f4 A<\/code>\uc758 \uc778\ub371\uc2a4\ub97c \ub098\ud0c0\ub0c5\ub2c8\ub2e4. \uac01 \ucffc\ub9ac\uc5d0 \ub300\ud574 L<\/code>\ubc88\uc9f8\ubd80\ud130 R<\/code>\ubc88\uc9f8\uae4c\uc9c0\uc758 \uad6c\uac04 \ud569\uc744 \uad6c\ud558\uc2dc\uc624.<\/p>\n

\uc785\ub825<\/h3>\n
\n    \uccab \ubc88\uc9f8 \uc904\uc5d0\ub294 \ubc30\uc5f4\uc758 \ud06c\uae30 N<\/code>\uacfc \ucffc\ub9ac\uc758 \uc218 Q<\/code>\uac00 \uc8fc\uc5b4\uc9c4\ub2e4.\n    \ub450 \ubc88\uc9f8 \uc904\uc5d0\ub294 N<\/code>\uac1c\uc758 \uc815\uc218 A[1], A[2], ..., A[N]<\/code>\uc774 \uc8fc\uc5b4\uc9c4\ub2e4.\n    \uc774\ud6c4 Q<\/code>\uac1c\uc758 \uc904\uc5d0 L<\/code>\uacfc R<\/code>\uac00 \uacf5\ubc31\uc73c\ub85c \uad6c\ubd84\ub418\uc5b4 \uc8fc\uc5b4\uc9c4\ub2e4.\n    <\/pre>\n
\ucd9c\ub825<\/h3>\n
\n    \uac01 \ucffc\ub9ac\uc5d0 \ub300\ud55c \uad6c\uac04 \ud569\uc744 \ud55c \uc904\uc5d0 \ud558\ub098\uc529 \ucd9c\ub825\ud55c\ub2e4.\n    <\/pre>\n
\uc608\uc81c \uc785\ub825<\/h2>\n
\n    5 3\n    1 2 3 4 5\n    1 3\n    2 4\n    1 5\n    <\/pre>\n
\uc608\uc81c \ucd9c\ub825<\/h2>\n
\n    6\n    9\n    15\n    <\/pre>\n
\ubb38\uc81c \ud574\uacb0 \uc804\ub7b5<\/h2>\n
\uad6c\uac04 \ud569 \ubb38\uc81c\ub97c \ucc98\ub9ac\ud558\uae30 \uc704\ud55c \ucf54\ub529 \ubc29\ubc95\uc740 \uc5ec\ub7ec \uac00\uc9c0\uac00 \uc788\uc9c0\ub9cc, \ube44\ud6a8\uc728\uc801\uc778 \ubc29\ubc95\uc73c\ub85c\ub294 \uac01 \ucffc\ub9ac\uc5d0 \ub300\ud574 \uc9c1\uc811 \ub8e8\ud504\ub97c \ub3cc\uba70 \uad6c\uac04 \ud569\uc744 \uacc4\uc0b0\ud558\ub294 \uac83\uc785\ub2c8\ub2e4. \uc774 \uacbd\uc6b0, \ucd5c\uc545\uc758 \uacbd\uc6b0 O(N * Q)<\/code>\uc758 \uc2dc\uac04\uc774 \uc18c\uc694\ub420 \uc218 \uc788\uc2b5\ub2c8\ub2e4. \ub530\ub77c\uc11c \uc6b0\ub9ac\ub294 \uad6c\uac04 \ud569\uc744 \ube60\ub974\uac8c \uacc4\uc0b0\ud558\uae30 \uc704\ud55c \ubc29\ubc95\uc744 \ucc3e\uc544\uc57c \ud569\ub2c8\ub2e4.<\/p>\n
\uc804\ucc98\ub9ac \ud1b5\ud55c \uc811\uadfc<\/h3>\n
\ud6a8\uc728\uc801\uc778 \ubc29\ubc95 \uc911 \ud558\ub098\ub294 \uc804\ucc98\ub9ac \uacfc\uc815\uc744 \ud1b5\ud574 \uad6c\uac04 \ud569\uc744 \ub204\uc801 \ubc30\uc5f4 \ud615\ud0dc\ub85c \uc800\uc7a5\ud558\ub294 \uac83\uc785\ub2c8\ub2e4. \uc774\ub807\uac8c \ud558\uba74 \uac01 \ucffc\ub9ac\uc758 \uad6c\uac04 \ud569\uc744 O(1)<\/code>\uc5d0 \uad6c\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.<\/p>\n
    \n
  1. \uba3c\uc800, \ub204\uc801\ud569 \ubc30\uc5f4 sum<\/code>\uc744 \uc0dd\uc131\ud569\ub2c8\ub2e4. \uc774\ub54c sum[0] = 0<\/code>\uc73c\ub85c \ucd08\uae30\ud654\ud558\uace0, sum[i] = sum[i - 1] + A[i - 1]<\/code>\ub85c \uc124\uc815\ud569\ub2c8\ub2e4.<\/li>\n
  2. \uac01 \ucffc\ub9ac\ub294 \uad6c\uac04 [L, R]<\/code>\uc5d0\uc11c\uc758 \ud569\uc744 \uad6c\ud558\uae30 \uc704\ud574 sum[R] - sum[L - 1]<\/code> \uacf5\uc2dd\uc744 \uc0ac\uc6a9\ud569\ub2c8\ub2e4.<\/li>\n<\/ol>\n
    \uc790\ubc14 \ucf54\ub4dc \uad6c\ud604<\/h2>\n
    \n    import java.util.Scanner;\n\n    public class RangeSum {\n        public static void main(String[] args) {\n            Scanner sc = new Scanner(System.in);\n            \n            \/\/ \ubc30\uc5f4\uc758 \ud06c\uae30\uc640 \ucffc\ub9ac \uc218 \uc785\ub825\n            int N = sc.nextInt();\n            int Q = sc.nextInt();\n            \n            \/\/ \ubc30\uc5f4 \uc785\ub825\n            int[] A = new int[N];\n            for (int i = 0; i < N; i++) {\n                A[i] = sc.nextInt();\n            }\n            \n            \/\/ \ub204\uc801\ud569 \ubc30\uc5f4 \uc0dd\uc131\n            long[] sum = new long[N + 1];\n            for (int i = 1; i <= N; i++) {\n                sum[i] = sum[i - 1] + A[i - 1];\n            }\n            \n            \/\/ \uac01 \ucffc\ub9ac\ub97c \ucc98\ub9ac\n            for (int i = 0; i < Q; i++) {\n                int L = sc.nextInt();\n                int R = sc.nextInt();\n                long rangeSum = sum[R] - sum[L - 1];\n                System.out.println(rangeSum);\n            }\n            \n            sc.close();\n        }\n    }\n    <\/pre>\n
    \ucf54\ub4dc \uc124\uba85<\/h2>\n
    \uc704\uc758 \ucf54\ub4dc\ub294 \ub2e4\uc74c\uacfc \uac19\uc740 \ud750\ub984\uc73c\ub85c \ub3d9\uc791\ud569\ub2c8\ub2e4:<\/p>\n
      \n
    1. \uba3c\uc800, \uc0ac\uc6a9\uc790\ub85c\ubd80\ud130 \ubc30\uc5f4\uc758 \ud06c\uae30 N<\/code>\uacfc \ucffc\ub9ac \uc218 Q<\/code>\ub97c \uc785\ub825\ubc1b\uc2b5\ub2c8\ub2e4.<\/li>\n
    2. \uadf8 \ub2e4\uc74c, \ubc30\uc5f4 A<\/code>\uc758 \uc6d0\uc18c\ub97c \uc785\ub825\ubc1b\uc544 \ucd08\uae30\ud654\ud569\ub2c8\ub2e4.<\/li>\n
    3. \uac01 \uc6d0\uc18c\uc758 \ub204\uc801\ud569\uc744 \uc800\uc7a5\ud558\ub294 sum<\/code> \ubc30\uc5f4\uc744 \uc0dd\uc131\ud569\ub2c8\ub2e4. \uc774\ub54c, \uc778\ub371\uc2a4 0\uc740 0\uc73c\ub85c \ucd08\uae30\ud654 \ud1b5\ud569\ud558\uc5ec, sum[i]<\/code>\uc5d0 \ub300\ud55c \uc811\uadfc\uc774 \uc6a9\uc774\ud569\ub2c8\ub2e4.<\/li>\n
    4. \ucffc\ub9ac\ub9c8\ub2e4 \uc8fc\uc5b4\uc9c4 L<\/code>\uacfc R<\/code>\uc744 \uc774\uc6a9\ud574 \uad6c\uac04 \ud569\uc744 \uacc4\uc0b0 \ud6c4 \ucd9c\ub825\ud569\ub2c8\ub2e4.<\/li>\n<\/ol>\n
      \ud14c\uc2a4\ud2b8 \ubc0f \uac80\uc99d<\/h2>\n
      \ucf54\ub4dc\ub97c \uc791\uc131\ud55c \ud6c4, \ub2e4\uc591\ud55c \uc785\ub825\uc744 \ud1b5\ud574 \uac01 \ucffc\ub9ac\uac00 \uc62c\ubc14\ub978 \uacb0\uacfc\ub97c \ucd9c\ub825\ud558\ub294\uc9c0 \ud655\uc778\ud574\uc57c \ud569\ub2c8\ub2e4. \uc608\uc81c \uc785\ub825\uacfc \ud568\uaed8 \ucd94\uac00\uc801\uc778 \uacbd\uc6b0\ub4e4\ub3c4 \uc2e4\ud5d8\ud574\ubcf4\uba70 \uacb0\uacfc\ub97c \uac80\ud1a0\ud569\ub2c8\ub2e4. \uc544\ub798\ub294 \uba87 \uac00\uc9c0 \uc608\uc2dc\uc785\ub2c8\ub2e4.<\/p>\n