René's URL Explorer Experiment

{"@context":"https://schema.org","@type":"DiscussionForumPosting","headline":"누적합 알고리즘","articleBody":"# 누적합 알고리즘 (Prefix Sum Algorithm)\r\n\r\n- 누적합 알고리즘은 구간합을 빠르게 계산하기 위해 사용되는 기법이다.\r\n- 주어진 배열의 구간합을 O(1) 시간 복잡도로 구할 수 있다. 이를 위해 먼저 누적합 배열을 생성\r\n\r\n## 기본 개념\r\n- **정의**: 누적합 배열은 원래 배열의 각 원소까지의 합을 저장한 배열\r\n- **목적**: 구간합을 빠르게 구하기 위해 사용됌.\r\n- **사용법**: 특정 구간 [A, B]의 합을 구할 때, B까지의 누적합에서 A-1까지의 누적합을 뺍니다.\r\n\r\n## 예시\r\n- 주어진 배열: [1, 2, 3, 4, 5]\r\n- 누적합 배열: [1, 3, 6, 10, 15]\r\n\r\n\r\n1. **방법 1**:\r\n   - 각 단계별로 누적합을 구합니다.\r\n   - 예시:\r\n     ```\r\n     1\r\n     1 + 2\r\n     1 + 2 + 3\r\n     1 + 2 + 3 + 4\r\n     1 + 2 + 3 + 4 + 5\r\n     ```\r\n\r\n2. **방법 2 (더 효율적인 방법)**:\r\n   - 이전 단계의 누적합에 현재 원소를 더합니다.\r\n   - 예시:\r\n     ```\r\n     1\r\n     1 + 2\r\n     3 + 3\r\n     6 + 4\r\n     10 + 5\r\n     ```\r\n\r\n## 구간합 계산 방법\r\n- **구간합 [A, B] 계산**:\r\n  1. 누적합 배열을 구합니다.\r\n  2. 구간합은 B까지의 누적합에서 A-1까지의 누적합을 뺀다.\r\n  - 수식: `sum(A, B) = prefix_sum[B] - prefix_sum[A-1]`","author":{"url":"https://github.com/hnjgg","@type":"Person","name":"hnjgg"},"datePublished":"2024-07-30T06:00:09.000Z","interactionStatistic":{"@type":"InteractionCounter","interactionType":"https://schema.org/CommentAction","userInteractionCount":0},"url":"https://github.com/6/SquirtlesAlgorithmStudyS8/issues/6"}