# Prefix sum
LeetCode - 1732. Find the Highest Altitude
Solution Explanation > gain배열은 지점별 고도의 변화값을 나타내는 배열이다. 필자가 원하는 것은 지점별 고도를 갖고있는 배열이다. 그래서 reduce를 이용해서 전 지점에 고도의 변화값을 적용해서 지점별 고도 리스트를 만들었다. 그리고 Math.max 메소드를 사용해서 가장 높은 고도값을 리턴한다.
LeetCode - 2574. Left and Right Sum Differences
Solution Explanation > 문제의 요구사항에 맞춰 단순하게 접근해서 for문이나 map 메소드를 이용해서 leftSum 배열과 rightSum 배열을 하나하나 구한 후 두 배열의 차를 얻는 방법으로 해결할수도있다. 하지만 뭔가 수학적인(?) 규칙이 있는 것 같아 그 규칙을 이용해서 풀어보았다. 예제를 이용해서 알아낸 규칙은 다음과 같다. > | index | LeftSum | RightSum | |:---:|:---:|:---:| | 0 | | 1 + 2 + 3 + ... + nums.length-1| | 1 | 0 | 2 + 3 + ... + nums.length-1| | 2 | 0 + 1 | 3 + ... + nums.length-1| | 3 | 0 + 1 + 2 | 4 + ... + nums.length-1| | nums.length-1 | 0 + 1 + 2 + 3 + ... + nums.length-2 | | 즉, 특정 인덱스에서 해당 요소
LeetCode - 1480. Running Sum of 1d Array
Solution Explanation > 빌트인 배열 메소드를 사용하지 않고 풀어보았다. 결과를 담을 새로운 배열(output)을 선언한다. nums의 첫 번째 요소를 output에 첫 번째 요소로 집어넣는다. output의 현재 인덱스의 값 = output의 이전 인덱스의 값 + nums의 현재 인덱스의 값 위 식대로 코드를 작성해면 된다.
[BOJ/C++] 10986(나머지 합)
1. Link https://www.acmicpc.net/problem/10986 진짜 어이없게 끝난 문제입니다. 누적 합은 알겠는데 어떻게 풀어야하지 엄청 고민했는데, 한 번 생각나고 나서는 이걸 왜 고민했지 싶었던 문제였습니다. 누적 합 뿐 아니라 결과값에 왜 다음과 같이 더해지는지(조합) 알아야 하는 문제입니다. 만약 생소하다면 이런 유형은 익혀두는 것이 좋습니다.(저에게도..) 2. 풀이 과정 > 1. 연속된 부분 구간의 합(N 누적 합 ~의 합이 m으로 나누어 떨어지는 구간의 개수 -> 조합(nCr) 누적 합은 저런 구절만으로 대략 눈치챌 수 있을 거라고 생각합니다. 사실 세그먼트 트리도 있고, DP도 있고 다양하지만, N 값을 보고 배열이 너무 커질 것이라고 생각했습니다. 따라서 누적 합으로 문제를 풀이했습니다. 예제를 들어 문제를 설명해보도록 하겠습니다. 
백준 28427
다음 쿼리를 수행하는 프로그램을 작성하시오. > >$L\ R$: $L \leq x < y \leq R$을 만족하는 정수 $x$, $y$에 대하여, $x \leq k \leq y$를 만족하는 모든 자연수 $k$의 합이 소수가 되게 하는 모든 정수 쌍 $(x, \:y)$의 개수를 출력한다. 첫째 줄에 쿼리의 개수 $Q$가 주어진다. $(1 \leq Q \leq 500\ 000)$ 다음 $Q$개의 줄에는 각각의 쿼리를 나타내는 양의 정수 $L$, $R$이 주어진다. $(2 \leq L < R \leq 500 \ 000)$ 풀이 문제를 보고 바로 떠오른 개념은 누적합, DP였다. 쿼리(test case)의 개수, L, R이 5\*10^5이기 때문에 쿼리 내부의 연산은 선형/로그시간이여야 한다. 그렇기 때문에 DP table을 만들어 누적합 개념으로 접근한다는 생각을 가지고 이 문제를 풀기 시작했다. 처음에는 모든 구간을 저장하는 테이블을 만든다는 생각
[Prefix Sum 문제] LEETCODE.238 Product of Array Except Self
문제풀이 이번 문제는 구간 합 문제 유형이다. 크게 Prefix 결과(선택된 index 이전 결과)와 PostFix(선택된 index 이후 결과의 값)을 활용한다. 보조 리스트 a(Prefix 배열)와 b(Postfix 배열)를 생성하고, a는 각 요소의 왼쪽 요소들의 곱, b는 각 요소의 오른쪽 요소들의 곱을 저장함. a 리스트를 왼쪽에서 오른쪽으로 순회하며 각 요소를 자신의 왼쪽 요소들의 곱으로 설정함. b 리스트를 오른쪽에서 왼쪽으로 순회하며 각 요소를 자신의 오른쪽 요소들의 곱으로 설정함. a와 b 리스트를 병렬로 순회하며 각 위치의 왼쪽과 오른쪽 부분의 곱을 계산하고, 그 결과를 리스트로 반환함. 이렇게 하면 최종적으로 리스트 내의 모든 요소를 제외한 나머지 요소들의 곱이 계산되어 반환함 코드 Lookback Zip 함수를 통해 한 줄 라인으로 배열 간의 연산 결과를 Return 할 수 있다는 점을 활용해보는 것도 좋을 듯하다.
[BOJ/C++] 2167(2차원 배열의 합)
Link https://www.acmicpc.net/problem/2167 풀이 과정 누적 합에 대한 계산으로, 2차원 DP를 이용하여 합을 누적하는 것으로 계산 > 1. (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하라 -> DP 누적합을 구하는 방법을 다음의 그림과 같이 표현할 수 있습니다. > DPx - DPx - DPi - 1 + DPi - 1 (0,0)부터 (x,y)까지를 포함하는 검은색 구간을 전부 합한 값이 (x,y)위치에 누적합으로 계산되어 있습니다. 이 때 빨간색과 초록색 누적합을 빼면 (i,j)부터 (x,y)까지의 누적합을 구한 것처럼 보일지 모르지만, 빨간 사각형과 초록 사각형은 보라색
BOJ 28140 | 빨강~ 빨강~ 파랑! 파랑! 달콤한 솜사탕!
5월 월간 향유회 C번 문제입니다. 이건 이분탐색이 정해입니다. ㄹㅇ. 구간 [l, r]이 주어질 때, 그 구간 내부에서 R과 B를 찾아야 합니다. R을 나타내는 인덱스 a, b와 B를 나타내는 인덱스 c, d가 있을 때, $a<b<c<d$인 a, b, c, d를 구해야 합니다. 결국 구간 내부에서 가장 처음으로 등장하는 R과 가장 마지막에 등장하는 B를 찾고, 그걸 기준으로 a, b, c, d를 구해야 합니다. $Ridx, Bidx$ 두 배열을 만들고 문자열 내부에서 R이 등장하는 인덱스와 B가 등장하는 인덱스를 기록합니다. 그 후, 쿼리가 들어오면 [l, r]에서 l을 기준으로 R을 찾고, r을 기준으로 B를 찾은 뒤 그 인덱스를 기반으로 a, b, c, d를 모두 찾고 $a<b<c<d$에 부합하면
알고리즘 - 구간합
구간 합 ( Prefix Sum ) 구간합은 주어진 배열이나 리스트에서 원소들을 특정 구간으로 묶어 더한 값을 각 구간마다 계산하는 방법이다. 예를 들어, 주어진 배열이 [1, 2, 3, 4, 5] 라면 각 위치에서 구간합은 다음과 같다. 배열에서 특정 구간의 합을 구할 때 매번 반복문을 돌며 합을 구하는 것은 시간 복잡도가 높아지기 때문에 구간합을 미리 구해 놓으면 구간 합을 구하는데 O(1)의 시간복잡도만 필요하다. 구간합을 구하는 공식은 다음과 같으며, 크게 2가지 과정을 거친다. * 1. S[i] = S[i-1] + A[i] * 합배열 S를 만드는 공식, 배열 S의 0번째 인덱스부터 S.length 까지 모든 배열을 이전값 + 현재 입력값으로 초기화 * 2. S[j] - S[i - 1] * 구간합을 구하는 공식. 구하려는 구간합의 인덱스가 더 큰 인덱스에서 더 작은 인덱스 - 1의
[2022 KAKAO BLIND RECRUITMENT] 파괴 되지 않은 건물
2022 KAKAO BLIND RECRUITMENT 파괴되지 않은 건물 문제 설명 [본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다.] N x M 크기의 행렬 모양의 게임 맵이 있습니다. 이 맵에는 내구도를 가진 건물이 각 칸마다 하나씩 있습니다. 적은 이 건물들을 공격하여 파괴하려고 합니다. 건물은 적의 공격을 받으면 내구도가 감소하고 내구도가 0이하가 되면 파괴됩니다. 반대로, 아군은 회복 스킬을 사용하여 건물들의 내구도를 높이려고 합니다. 적의 공격과 아군의 회복 스킬은 항상 직사각형 모양입니다. 예를 들어, 아래 사진은 크기가 4 x 5인 맵에 내구도가 5인 건물들이 있는 상태입니다. 
BOJ 13550 | 수열과 쿼리 7
수열과 쿼리 0과 완전히 같은 문제이다. 다만 수열과 쿼리 0은 마이너스 값까지 신경써야 했다면 이 문제는 그런 게 없는 대신 (psum[j] - psum[i-1]) % K == 0을 찾는 것이므로 모든 psum 값에 mod K 를 해 주어야 한다. 2 <= K <= 1,000,000 이므로 배열 크기만 맞춰준다면 수열과 쿼리 0을 푼 시점에서 정말 어렵지 않게 통과할 수 있다.
BOJ 13545 | 수열과 쿼리 0
수열과 쿼리 4를 풀었다면 날먹이 가능하다는 글을 읽고 도전해 보았다. 우선, [i~j]의 합은 계산해 놓은 누적합 배열이 psum이라고 할 때 psum[j] - psum[i-1]이다. 이 합이 0이려면 psum[i-1] = psum[j] 이면 되는 것이다. 따라서 같은 값의 최대 거리를 찾는 수열과 쿼리 4 문제를 이용해서 arr 대신 psum으로 계산하면 된다. 여기까지는 의식의 흐름대로 왔는데 계속 OutofBound가 나서 잠깐 당황했다. psum 배열 크기를 1,000,000까지 늘렸는데도 계속 OutofBound가 나길래 왜이러지 하고 생각하다가 이 문제에서 누적합은 최소 -100,000에서 최대 100,000까지 가능하다는 걸 깨달았다. psum을 그대로 쓰려면 cnt[psum]에서 마이
[C++] 11659: 구간 합 구하기 4
문제 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다. 출력 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다. 풀이 1차원 누적합 문제. sum 배열에 0번째 인덱스부터 i번째 인덱스까지의 합을 저장해놓는다. i부터 j까지의 합은 이다. 코드 성공 !
[c++] 백준 25682, 체스판 다시 칠하기 2
백준 25682 > 알고리즘 분류 : prefix sum (누적 합) 🌲 문제 요약 입력받은 임의의 MxN 크기의 보드를 KxK 크기의 보드로 잘라낸 뒤 색칠을 통해 하나의 체스판으로 만들려 한다. 이때 다시 칠해야 하는 정사각형의 최소 개수는 몇 개일까? 🌲 문제 풀이 2차원에서의 누적 합을 이용하여 문제를 해결하였다. chess 함수를 통해, 입력받은 배열 board와 두 개의 체스판(첫 번째 칸이 검은색인 체스판, 첫 번째 칸이 흰색인 체스판)을 각각 비교한 뒤, 더 작은 값을 정답으로 출력했다. chess 함수에서는 board와 체스판을 비교하여, 만약 색칠이 필요하다면 변수 value에 1, 색칠이 필요 없다면 value에 0을 저장하고 이를 토대로 누적 합 배열 pSum을 완성시켰다. 다음으로 pSum 안에서 반복문을 통해 KxK
[C++] 25682: 체스판 다시 칠하기 2
문제 지민이는 자신의 저택에서 MN개의 단위 정사각형으로 나누어져 있는 M×N 크기의 보드를 찾았다. 어떤 정사각형은 검은색으로 칠해져 있고, 나머지는 흰색으로 칠해져 있다. 지민이는 이 보드를 잘라서 K×K 크기의 체스판으로 만들려고 한다. 체스판은 검은색과 흰색이 번갈아서 칠해져 있어야 한다. 구체적으로, 각 칸이 검은색과 흰색 중 하나로 색칠되어 있고, 변을 공유하는 두 개의 사각형은 다른 색으로 칠해져 있어야 한다. 따라서 이 정의를 따르면 체스판을 색칠하는 경우는 두 가지뿐이다. 하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우이다. 보드가 체스판처럼 칠해져 있다는 보장이 없어서, 지민이는 K×K 크기의 체스판으로 잘라낸 후에 몇 개의 정사각형을 다시 칠해야겠다고 생각했다. 당연히 K×K 크기는 아무데서나 골라도 된다. 지민이가 다시 칠해야 하는 정사각형의 최소 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정수 N, M, K가 주어진다
[C++] 2167: 2차원 배열의 합
문제 2차원 배열이 주어졌을 때 (i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하는 프로그램을 작성하시오. 배열의 (i, j) 위치는 i행 j열을 나타낸다. 입력 첫째 줄에 배열의 크기 N, M(1 ≤ N, M ≤ 300)이 주어진다. 다음 N개의 줄에는 M개의 정수로 배열이 주어진다. 배열에 포함되어 있는 수는 절댓값이 10,000보다 작거나 같은 정수이다. 그 다음 줄에는 합을 구할 부분의 개수 K(1 ≤ K ≤ 10,000)가 주어진다. 다음 K개의 줄에는 네 개의 정수로 i, j, x, y가 주어진다(1 ≤ i ≤ x ≤ N, 1 ≤ j ≤ y ≤ M). 출력 K개의 줄에 순서대로 배열의 합을 출력한다. 배열의 합은 231-1보다 작거나 같다. 풀이 2차원 배열의 누적합 문제. 
[Python] 백준 2118 - 두 개의 탑 문제 풀이
Overview BOJ 2118번 두 개의 탑 문제 Python 풀이 분류: 투포인터(Two Pointer), 누적합 (Prefix Sum) 문제 페이지 풀이 코드 투포인터와 누적합을 응용한 풀이이다. 거리가 저장된 dists 리스트를 복사하여 뒤에 붙여 길이가 2N인 리스트를 만든다. 그리고 해당 리스트의 누적합을 구한 뒤, 투포인터를 이용해 두 점 사이의 거리를 탐색한다.
[Python] 백준 15724 - 주지수 문제 풀이
Overview BOJ 15724번 주지수 문제 Python 풀이 분류: 다이나믹 프로그래밍 (Dynamic Programming), 누적합 (Prefix Sum) 문제 페이지 풀이 코드 다이나믹 프로그래밍과 누적합으로 풀 수 있다. arr 리스트 각 원소에 (0, 0)부터 해당 좌표까지의 합을 계산하여 저장한다. 그리고 구하려는 영역의 합을 구한다.
Leetcode - 437. Path Sum III 풀이
문제 주어진 트리에서 root부터 leaf까지 path중에 합이 targetSum 과 같은 경우는 총 몇개인가 (root부터 시작될 필요 없음) https://leetcode.com/problems/path-sum-iii/ 해결 아이디어 기본적으로 560. Subarray Sum Equals K 와 동일하다. 560번 문제를 먼저 잘 이해하면, 이 문제도 쉽게 해결할 수 있다. 이 두문제를 항상 쌍으로 같이 풀어볼것. 다른점은 리스트를 선형적으로 순회하는
[C++] 10986: 나머지 합
문제 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) 쌍의 개수를 구해야 한다. 입력 첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 106, 2 ≤ M ≤ 103) 둘째 줄에 N개의 수 A1, A2, ..., AN이 주어진다. (0 ≤ Ai ≤ 109) 출력 첫째 줄에 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 출력한다. 풀이 코드 구현은 짧은데 로직이 어렵다 ㅜ-ㅜ 부분 구간의 시작 인덱스를 i, 끝 인덱스를 j라 하자. 연속된 부분 구간의 합이 M으로 나누어떨어지기 위해서는 이어야 하므로 일 경우, i ~ j 구간의 합이 M으로 나누어떨어진다. 따라서 i와 j의 조합 수를 구하여 모두 더하면, 답을 구할 수 있다. 아래 그림