๋์ ํฉ(Prefix sum)
๊ณ์ฐ ์์ ์ค์ฌ์ ์๊ฐ์ ์ผ๋ก ๋ง์ ์ด๋์ ๋ณผ ์ ์๋ ์๊ณ ๋ฆฌ์ฆ์ด๋ค.
1. ๊ธฐ๋ณธ ์๋ฆฌ
1) 1์ฐจ์ ๋ฐฐ์ด
1์ฐจ์ ๋ฐฐ์ด์์ i๋ฒ์งธ๋ถํฐ j๋ฒ์งธ ์ธ๋ฑ์ค๊น์ง k๋ฅผ ๋ํ ๊ฒ์ ๊ธฐ๋กํ๋ ค๋ฉด, ์๋ก์ด ๋ฐฐ์ด์ i๋ฒ์งธ ์ธ๋ฑ์ค์ k๋ฅผ ๋ํ๊ณ j+1๋ฒ์งธ ์ธ๋ฑ์ค์ k๋ฅผ ๋นผ๋ฉด ๋๋ค.
- ์๋ก์ด ๋ฐฐ์ด์ ํฌ๊ธฐ๋ ๊ธฐ์กด ๋ฐฐ์ด ํฌ๊ธฐ๋ณด๋ค ํ๋ ์ด์ ํฌ๊ฒ ๋ง๋ ๋ค.
์๋ฅผ ๋ค์ด ํฌ๊ธฐ๊ฐ 5์ธ ๋ฐฐ์ด์์ 0๋ฒ์งธ๋ถํฐ 2๋ฒ์งธ ์ธ๋ฑ์ค๊น์ง N์ ๋นผ๊ณ ์ถ๋ค๋ฉด ๋ค์๊ณผ ๊ฐ์ด ๋์ ํฉ ๋ฐฐ์ด์ ๋ง๋ ๋ค.
{ -N, 0, 0, N, 0, 0 }
์ ์๋ก์ด ๋ฐฐ์ด์ 0๋ฒ์งธ๋ถํฐ ๋ง์ง๋ง ์ธ๋ฑ์ค๊น์ง ๋์ ํฉ์ ๊ณ์ฐํ๊ฒ ๋๋ฉด ๋ค์๊ณผ ๊ฐ๋ค.

์ถ๊ฐ๋ก 1๋ฒ์งธ๋ถํฐ 2๋ฒ์งธ ์ธ๋ฑ์ค๊น์ง M์ ๋ํ๊ณ ์ถ๋ค๋ฉด ๋์ ํฉ ๋ฐฐ์ด์ ๊ฐ์ ์ถ๊ฐํ๋ค.
{ -N, -M, 0, N, M, 0 }
๋ค์ 0๋ฒ์งธ๋ถํฐ ๋ง์ง๋ง ์ธ๋ฑ์ค๊น์ง ๋์ ํฉ์ ๊ณ์ฐํ๊ฒ ๋๋ฉด ๋ค์๊ณผ ๊ฐ๋ค.

๋์ ํฉ ๋ฐฐ์ด์ ๊ณ์ ๊ฐ์ ์ ์ฅํ ํ ๋ง์ง๋ง์ ํ ๋ฒ๋ง ๋์ ํฉ์ ๊ณ์ฐํ๋ฉด, ์ต์ข ์ ์ธ ๋ณํ๋์ ๊ธฐ๋กํ๋ ๋ฐฐ์ด์ ๊ฐ์ง ์ ์๋ค.
2) 2์ฐจ์ ๋ฐฐ์ด

2. ๋ฌธ์
https://programmers.co.kr/learn/courses/30/lessons/92344
์ฝ๋ฉํ ์คํธ ์ฐ์ต - ํ๊ดด๋์ง ์์ ๊ฑด๋ฌผ
[[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5],[5,5,5,5,5]] [[1,0,0,3,4,4],[1,2,0,2,3,2],[2,1,0,3,1,2],[1,0,1,3,3,1]] 10 [[1,2,3],[4,5,6],[7,8,9]] [[1,1,1,2,2,4],[1,0,0,1,1,2],[2,2,0,2,0,100]] 6
programmers.co.kr
#include <vector>
using namespace std;
int PrefixSum[1001][1001];
int solution(vector<vector<int>> board, vector<vector<int>> skill)
{
// 2์ฐจ์ ๋ฐฐ์ด ๋์ ํฉ
for (vector<int> sk : skill) {
int degree = sk[5] * (sk[0] == 1 ? -1 : 1);
PrefixSum[sk[1]][sk[2]] += degree;
PrefixSum[sk[1]][sk[4] + 1] -= degree;
PrefixSum[sk[3] + 1][sk[2]] -= degree;
PrefixSum[sk[3] + 1][sk[4] + 1] += degree;
}
// ์์์ ์๋๋ก ๋์ ํฉ
for (int i = 0; i < board.size(); i++)
for (int j = 1; j < board[0].size(); j++)
PrefixSum[i][j] += PrefixSum[i][j - 1];
// ์ผ์ชฝ์์ ์ค๋ฅธ์ชฝ์ผ๋ก ๋์ ํฉ
for (int i = 1; i < board.size(); i++)
for (int j = 0; j < board[0].size(); j++)
PrefixSum[i][j] += PrefixSum[i - 1][j];
int answer = 0;
for (int i = 0; i < board.size(); ++i)
for (int j = 0; j < board[0].size(); ++j)
if (board[i][j] + PrefixSum[i][j] > 0)
answer++;
return answer;
}
https://leetcode.com/problems/product-of-array-except-self/description/
#include <vector>
using namespace std;
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> answer(n, 1);
int left = 1;
for (int i = 0; i < n; ++i) {
answer[i] = left;
left *= nums[i];
}
int right = 1;
for (int i = n - 1; i >= 0; --i) {
answer[i] *= right;
right *= nums[i];
}
return answer;
}
};