{"id":27010,"date":"2024-10-27T13:42:53","date_gmt":"2024-10-27T13:42:53","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=27010"},"modified":"2024-11-26T07:24:28","modified_gmt":"2024-11-26T07:24:28","slug":"%ed%8c%8c%ec%9d%b4%ec%8d%ac-%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-%ea%b5%ac%ed%95%98%ea%b8%b0-3","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/27010\/","title":{"rendered":"\ud30c\uc774\uc36c \ucf54\ub529\ud14c\uc2a4\ud2b8 \uac15\uc88c, \uad6c\uac04 \ud569 \uad6c\ud558\uae30 3"},"content":{"rendered":"

<\/p>\n

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

\n \uc8fc\uc5b4\uc9c4 \uc815\uc218 \ubc30\uc5f4 A\uc640 \uc5ec\ub7ec \uc30d\uc758 \uc815\uc218 L, R\uc774 \uc8fc\uc5b4\uc84c\uc744 \ub54c, \uac01 \uc30d\uc5d0 \ub300\ud574 L\ubc88 \uc778\ub371\uc2a4\ubd80\ud130 R\ubc88 \uc778\ub371\uc2a4\uc758 \uad6c\uac04 \ud569\uc744 \uad6c\ud558\ub294 \ud504\ub85c\uadf8\ub7a8\uc744 \uc791\uc131\ud558\uc2dc\uc624.\n <\/p>\n

\n \uc608\ub97c \ub4e4\uc5b4, A = [1, 2, 3, 4, 5]\uc774\uace0 \uad6c\uac04 \uc30d\uc774 (1, 3), (0, 2), (2, 4)\ub77c\uace0 \ud558\uba74,
\n \uacb0\uacfc\ub294 \uac01\uac01 9, 6, 12\uac00 \ub418\uc5b4\uc57c \ud569\ub2c8\ub2e4.\n <\/p>\n

\uc785\ub825 \ud615\uc2dd<\/h2>\n
\n    - \uccab \uc904\uc5d0 \uc815\uc218 N (1 \u2264 N \u2264 100,000): \ubc30\uc5f4 A\uc758 \ud06c\uae30\n    - \ub458\uc9f8 \uc904\uc5d0\ub294 N\uac1c\uc758 \uc815\uc218 A[i] (1 \u2264 A[i] \u2264 10,000)\uac00 \uc8fc\uc5b4\uc9c4\ub2e4.\n    - \uc14b\uc9f8 \uc904\uc5d0 \uc815\uc218 M (1 \u2264 M \u2264 100,000): \uad6c\uac04 \uc30d\uc758 \uac1c\uc218\n    - \uc774\uc5b4\uc11c M\uc904\uc5d0 \uac78\uccd0 \uad6c\uac04 \uc30d L, R (0 \u2264 L <= R < N)\uac00 \uc8fc\uc5b4\uc9c4\ub2e4.\n    <\/pre>\n
\ucd9c\ub825 \ud615\uc2dd<\/h2>\n
\n    - \uac01 \uad6c\uac04\uc758 \ud569\uc744 M\uc904\uc5d0 \uac78\uccd0 \ucd9c\ub825\ud55c\ub2e4.\n    <\/pre>\n
\ubb38\uc81c \ud574\uacb0 \uc804\ub7b5<\/h2>\n
\n        \uc774 \ubb38\uc81c\ub97c \ud574\uacb0\ud558\uae30 \uc704\ud574\uc11c\ub294 \ub2e8\uc21c\ud788 \ubc18\ubcf5\ubb38\uc744 \uc0ac\uc6a9\ud558\ub294 \uac83\ub3c4 \uac00\ub2a5\ud558\uc9c0\ub9cc,
\n        \ucd5c\uc545\uc758 \uacbd\uc6b0 N\uacfc M\uc774 \ucd5c\ub300 100,000\uc774\ubbc0\ub85c O(N * M)\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub97c \uac00\uc9c4 \uc5f0\uc0b0\uc740 \ubd88\uac00\ub2a5\ud558\ub2e4.
\n        \ub530\ub77c\uc11c O(N + M)\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub97c \uac00\uc9c0\ub294 \ubc29\ubc95\uc774 \ud544\uc694\ud558\ub2e4.\n    <\/p>\n
\n        \uc774\ub97c \uc704\ud574 \uc804\ucc98\ub9ac<\/strong> \uacfc\uc815\uc73c\ub85c \ub204\uc801 \ud569 \ubc30\uc5f4<\/strong>\uc744 \ub9cc\ub4e4\uc5b4 \uc8fc\uba74 \uc720\uc6a9\ud558\ub2e4.
\n        \ub204\uc801 \ud569 \ubc30\uc5f4\uc744 \uc774\uc6a9\ud558\uba74 \uac01 \uad6c\uac04\uc758 \ud569\uc744 \ube60\ub974\uac8c \uad6c\ud560 \uc218 \uc788\ub2e4.\n    <\/p>\n
\ub204\uc801 \ud569 \ubc30\uc5f4 \uc124\uba85<\/h2>\n
\n        \uba3c\uc800 \ubc30\uc5f4 A\uc758 \ub204\uc801 \ud569\uc744 \uacc4\uc0b0\ud558\uc5ec prefix_sum \ubc30\uc5f4\uc744 \uc0dd\uc131\ud55c\ub2e4.
\n        prefix_sum[i]\ub294 A[0]\ubd80\ud130 A[i]\uae4c\uc9c0\uc758 \ud569\uc744 \uc800\uc7a5\ud55c\ub2e4.
\n        \uadf8\ub7ec\uba74 L\ubc88 \uc778\ub371\uc2a4\ubd80\ud130 R\ubc88 \uc778\ub371\uc2a4\uc758 \ud569\uc740 \ub2e4\uc74c\uacfc \uac19\uc774 \uacc4\uc0b0\ud560 \uc218 \uc788\ub2e4:
\n        
\nsum(L, R) = prefix_sum[R] – prefix_sum[L – 1]<\/strong>, L > 0
\n        
\nsum(0, R) = prefix_sum[R]<\/strong>, L = 0\n    <\/p>\n
\ucf54\ub4dc \uad6c\ud604<\/h2>\n
\n    \ndef compute_prefix_sum(A):\n    prefix_sum = [0] * len(A)\n    prefix_sum[0] = A[0]\n    for i in range(1, len(A)):\n        prefix_sum[i] = prefix_sum[i - 1] + A[i]\n    return prefix_sum\n\ndef range_sum(prefix_sum, L, R):\n    if L == 0:\n        return prefix_sum[R]\n    else:\n        return prefix_sum[R] - prefix_sum[L - 1]\n\ndef main():\n    N = int(input())\n    A = list(map(int, input().split()))\n    M = int(input())\n    \n    prefix_sum = compute_prefix_sum(A)\n\n    results = []\n    for _ in range(M):\n        L, R = map(int, input().split())\n        results.append(range_sum(prefix_sum, L, R))\n    \n    for result in results:\n        print(result)\n\nif __name__ == \"__main__\":\n    main()\n    <\/code>\n    <\/pre>\n
\ucf54\ub4dc \uc124\uba85<\/h2>\n
\n        1. compute_prefix_sum<\/strong> \ud568\uc218\ub294 \uc785\ub825\ubc1b\uc740 \ubc30\uc5f4 A\uc758 \ub204\uc801 \ud569\uc744 \uacc4\uc0b0\ud558\uc5ec
\n        prefix_sum \ubc30\uc5f4\uc744 \ubc18\ud658\ud569\ub2c8\ub2e4. \ucd08\uae30\uac12\uc744 \uc124\uc815\ud558\uace0, \uac01 \uc778\ub371\uc2a4\uc758 \uac12\uc740 \uc774\uc804 \uac12\uacfc \ud604\uc7ac \uac12\uc744 \ub354\ud558\uc5ec \uacc4\uc0b0\ud569\ub2c8\ub2e4.\n    <\/p>\n
\n        2. range_sum<\/strong> \ud568\uc218\ub294 \uc8fc\uc5b4\uc9c4 L\uacfc R\uc5d0 \ub300\ud574 \ub204\uc801 \ud569 \ubc30\uc5f4\uc744 \uc0ac\uc6a9\ud558\uc5ec
\n        \uad6c\uac04\uc758 \ud569\uc744 \ube60\ub974\uac8c \uacc4\uc0b0\ud569\ub2c8\ub2e4. L\uc774 0\uc774\uba74 prefix_sum[R]\uc744 \ubc18\ud658\ud558\uace0, \uadf8\ub807\uc9c0 \uc54a\uc73c\uba74
\n        prefix_sum[R]\uc5d0\uc11c prefix_sum[L-1]\uc744 \ube7c\uc11c \uacb0\uacfc\ub97c \uacc4\uc0b0\ud569\ub2c8\ub2e4.\n    <\/p>\n
\n        3. main<\/strong> \ud568\uc218\uc5d0\uc11c\ub294 \uc785\ub825\uc744 \ucc98\ub9ac\ud558\uace0, \uac01 \uad6c\uac04 \uc30d\uc5d0 \ub300\ud574 range_sum \ud568\uc218\ub97c \ud638\ucd9c\ud558\uc5ec
\n        \uacb0\uacfc\ub97c \ucd9c\ub825\ud569\ub2c8\ub2e4.\n    <\/p>\n
\uc2dc\uac04 \ubcf5\uc7a1\ub3c4 \ubd84\uc11d<\/h2>\n
\n        – \ub204\uc801 \ud569 \ubc30\uc5f4\uc744 \uacc4\uc0b0\ud558\ub294 \ub370 O(N)\uc758 \uc2dc\uac04\uc774 \uac78\ub9bd\ub2c8\ub2e4.\n    <\/p>\n
\n        – \uac01 M\uac1c\uc758 \ucffc\ub9ac\uc5d0 \ub300\ud574 O(1)\uc758 \uc2dc\uac04\uc774 \uc18c\uc694\ub429\ub2c8\ub2e4.
\n        \ub530\ub77c\uc11c \uc804\uccb4\uc801\uc73c\ub85c O(N + M)\uc758 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub97c \uac00\uc9d1\ub2c8\ub2e4.\n    <\/p>\n
\uacb0\ub860<\/h2>\n
\n        \uc774\ubc88 \uac15\uc88c\uc5d0\uc11c\ub294 \uad6c\uac04 \ud569 \uad6c\ud558\uae30\uc5d0 \ub300\ud55c \ud6a8\uc728\uc801\uc778 \uc811\uadfc \ubc29\ubc95\uc744 \ub2e4\ub8e8\uc5c8\uc2b5\ub2c8\ub2e4.
\n        \ub204\uc801 \ud569\uc744 \ud65c\uc6a9\ud558\uba74 \uc2dc\uac04 \ubcf5\uc7a1\ub3c4\ub97c \uc904\uc77c \uc218 \uc788\uc5b4 \ud070 \uc785\ub825\uc5d0\ub3c4 \ube60\ub974\uac8c \ucc98\ub9ac\ud560 \uc218 \uc788\uc2b5\ub2c8\ub2e4.
\n        \uc774\ub7ec\ud55c \uae30\ubc95\uc740 \ub2e4\uc591\ud55c \uc54c\uace0\ub9ac\uc998 \ubb38\uc81c\uc5d0\uc11c \uc720\uc6a9\ud558\ubbc0\ub85c \uaf2d \uc219\uc9c0\ud574\ub450\uc2dc\uae30 \ubc14\ub78d\ub2c8\ub2e4.\n    <\/p>\n
\ucd94\uac00 \uc5f0\uc2b5 \ubb38\uc81c<\/h2>\n