![[알고리즘]Prefix sum 알고리즘이란?](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2F4yL9M%2FbtrBFHqvUDT%2FNh7PSgdzXDf5YENg2q4311%2Fimg.png)
누적합(Prefix sum)란?
나열된 수의 누적된 합을 말한다.
배열의 일부 구간에서 대한 합을 매우 빠르게 구할 수 있게 해준다. N개의 원소로 이루어진 배열이 주어졌을 때 반복문을 통해 부분 배열의 합을 구하려면 O(N)이 걸리는데, 누적합을 이용하면 부분합을 0(N+M)으로 구할 수 있다.
설명
1차원 배열
arr을 순차 탐색하면서 sum 배열을 만들어주면 된다.
활용법
arr의 i항부터 j항 까지 합을 S(i,j)라고 하자.
이때 S(ij) = sum[j] - sum[i-1]이다.
S(2,4) = S[4]=S[1]이다. 쉽게 생각하면
참고문제)
https://www.acmicpc.net/problem/11659
11659번: 구간 합 구하기 4
첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j
www.acmicpc.net
해설)
[백준] 11659번 구간 합 구하기
문제설명 더보기 문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N
san-tiger.tistory.com
2차원 배열
2차원 배열도 같은 방식이다. arr을 순차 탐색하면서, sum배열을 만들어주면 된다.
Sum[i][j]에는 arr[0][0]부터 arr[i-1][j-1]까지의 합이다.
sum 배열 만드는 공식
sumArray[i][j]=arr[i-1][j-1]+sumArray[i-1][j]+sumArray[i][j-1]-sumArray[i-1][j-1]
활용법
arr(x1,y1) 부터 arr(x2,y2)의 합을 S라고 할 때,
S = sum[x2][y2]-sum[x1-1][y2]=sum[x2][y1-1] + sum[x1-1][y1-1]
참고문제)
https://www.acmicpc.net/problem/11659
11659번: 구간 합 구하기 4
첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j
www.acmicpc.net
해설)
[백준] 11660번 구간 합 구하기-2
문제설명 더보기 문제 N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다. 예를 들어, N = 4이고, 표가 아래와 같
san-tiger.tistory.com
'Etc. > Algorithm' 카테고리의 다른 글
| 에라토스테네스(Eratosthenes)의 체 (0) | 2022.06.26 |
|---|---|
| [알고리즘] 슬라이딩 윈도우(sliding window) 알고리즘 이란? (0) | 2022.05.12 |
| [알고리즘] Two Pointers 알고리즘이란? (0) | 2022.05.10 |
| [알고리즘] Time Complexity(시간 복잡도) 알아보기 (0) | 2022.05.08 |
| [알고리즘] JAVA (String, StringBuilder,List,Collections)메소드 정리 (0) | 2022.04.28 |