![]()
#1. 문제 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net #2. 풀이 1. 누적 합, Prefix Sum [BOJ알고리즘, C++]#11659_구간 합 구하기, Prefix Sum(누적 합) 알고리즘 [BOJ 알고리즘, C++] #11659_구간 합 구하기 4, Prefix Sum(누적 합) 알고리즘 BOJ 알고리즘 문제 풀이, 11659_구간 합 구하기 4 누적 합 알고리즘을 통해 수열의 구간 합을 구하는 문제 문제 풀이 과정 위 문 webddevys.tistory.com Prefix Su..
![]()
[BOJ 알고리즘, C++] #11660_구간 합 구하기 5 BOJ 알고리즘 문제 풀이, 11660_구간 합 구하기 5 누적 합 알고리즘을 통해 수열의 구간 합을 구하는 문제 문제 풀이 1. 먼저, 2차원 배열의 누적합을 "열" 순으로 누적 합을 계산하는 것이 아니라, "행" 순으로 계산해야 합니다. 2. 누적 합을 계산하는 방법은 아래와 같이 "[i-1][j] + [i][j-1] - [i-1][j-1]"입니다. prefixSum[i][j] = prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1] "행"을 기준으로 누적 합을 계산하다 보면 "중복"으로 누적된 값이 존재합니다! 위 그림을 살펴보면, prefixSum[4]를 위해 prefixSum[2]와..
![]()
[BOJ 알고리즘, C++] #11659_구간 합 구하기 4, Prefix Sum(누적 합) 알고리즘 BOJ 알고리즘 문제 풀이, 11659_구간 합 구하기 4 누적 합 알고리즘을 통해 수열의 구간 합을 구하는 문제 문제 풀이 과정 위 문제를 해결하기 위해 우리는 누적 합 알고리즘 두 가지를 선행할 필요가 있습니다. 1. 구간 합 (Prefix Sum) 2. 투 포인터(Two Pointers) Prefix Sum, 구간 합 /* 1. Prefix Sum을 계산하여 배열에 저장합니다. 2. i(left bound) ~ j(right bound) 구간의 합은 array[r] - array[l-1] 입니다. */ #include using namespace std; constexpr size_t n = 5; ..
