[C++] ๋ˆ„์  ํ•ฉ(Prefix sum)

2022. 3. 17. 17:45ยท๐Ÿ“ Computer Science/โœ Algorithm

๋ˆ„์  ํ•ฉ(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

 

์ถ”๊ฐ€๋กœ 1๋ฒˆ์งธ๋ถ€ํ„ฐ 2๋ฒˆ์งธ ์ธ๋ฑ์Šค๊นŒ์ง€ M์„ ๋”ํ•˜๊ณ  ์‹ถ๋‹ค๋ฉด ๋ˆ„์  ํ•ฉ ๋ฐฐ์—ด์— ๊ฐ’์„ ์ถ”๊ฐ€ํ•œ๋‹ค.

{ -N, -M, 0, N, M, 0 }

 

๋‹ค์‹œ 0๋ฒˆ์งธ๋ถ€ํ„ฐ ๋งˆ์ง€๋ง‰ ์ธ๋ฑ์Šค๊นŒ์ง€ ๋ˆ„์  ํ•ฉ์„ ๊ณ„์‚ฐํ•˜๊ฒŒ ๋˜๋ฉด ๋‹ค์Œ๊ณผ ๊ฐ™๋‹ค.

 

๋ˆ„์  ํ•ฉ ์˜ˆ2

 

๋ˆ„์  ํ•ฉ ๋ฐฐ์—ด์— ๊ณ„์† ๊ฐ’์„ ์ €์žฅํ•œ ํ›„ ๋งˆ์ง€๋ง‰์— ํ•œ ๋ฒˆ๋งŒ ๋ˆ„์  ํ•ฉ์„ ๊ณ„์‚ฐํ•˜๋ฉด, ์ตœ์ข…์ ์ธ ๋ณ€ํ™”๋Ÿ‰์„ ๊ธฐ๋กํ•˜๋Š” ๋ฐฐ์—ด์„ ๊ฐ€์งˆ ์ˆ˜ ์žˆ๋‹ค.

 

2) 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;
    }
};
์ €์ž‘์žํ‘œ์‹œ (์ƒˆ์ฐฝ์—ด๋ฆผ)
'๐Ÿ“ Computer Science/โœ Algorithm' ์นดํ…Œ๊ณ ๋ฆฌ์˜ ๋‹ค๋ฅธ ๊ธ€
  • [C++] ์—ฐ๊ฒฐ ๋ฆฌ์ŠคํŠธ(Linked List)
  • [C++] ํ‰ํ–‰ ๋ถ„ํ• , ๋ชจ์Šค ์•Œ๊ณ ๋ฆฌ์ฆ˜
  • [C++] ์ค‘๊ฐ„์—์„œ ๋งŒ๋‚˜๊ธฐ(Meet In The Middle)
  • [C++] ๋ฌธ์ž์—ด
Blxxming
Blxxming
CS ์ง€์‹๊ณผ ๊ณต๋ถ€ํ•˜๋‹ค ๋ฐฐ์šด ๊ฒƒ, ๊ฒฝํ—˜ํ•œ ๊ฒƒ ๋“ฑ์„ ๊ธฐ๋กํ•˜๋Š” ๋ธ”๋กœ๊ทธ์ž…๋‹ˆ๋‹ค.
  • Blxxming
    ๐Ÿ’ก๋ฒˆ๋œฉ๐Ÿ’ก
    Blxxming
  • ์ „์ฒด
    ์˜ค๋Š˜
    ์–ด์ œ
  • ๊ณต์ง€์‚ฌํ•ญ

    • Tech Interview
    • ๐Ÿ“š Tech (246)
      • ๐Ÿ“ Computer Science (96)
        • โœ OS (12)
        • โœ Network & Web (10)
        • โœ Database (11)
        • โœ Data Structure (6)
        • โœ Algorithm (40)
        • โœ Design Pattern (9)
        • โœ Cloud Computing (3)
        • โœ (5)
      • ๐Ÿ“ Language (73)
        • โœ Language (6)
        • โœ C & C++ (11)
        • โœ C# (19)
        • โœ JAVA (37)
      • ๐Ÿ“ Game (43)
        • โœ Computer Graphics (2)
        • โœ Unity (14)
        • โœ Unreal (26)
        • โœ (1)
      • ๐Ÿ“ Book (34)
        • โœ Effective (3)
        • โœ Game Server (16)
        • โœ Clean Code (14)
        • โœ (1)
  • hELLOยท Designed By์ •์ƒ์šฐ.v4.10.0
Blxxming
[C++] ๋ˆ„์  ํ•ฉ(Prefix sum)
์ƒ๋‹จ์œผ๋กœ

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”