[C++] ICPC 25W 4회차 - 누적합, 투포인터

prefix sum(누적합)

• 배열에서 각 위치까지의 합을 미리 계산하는 기법
• f(i) = 구간 [1,i]의 원소를 합친 값
• 알아볼 것
  1. 우리가 원하는 것을 구할 수 있는가
  2. 이걸 구하는 것은 효율적인가
• f(1)부터 f(n)까지 모두 구했다고 가정 -> 문제에서 요구하는 구간[i,j]에 속하는 원소들의 합을 구해야 함.
  • f(j)-f(i-1)로 구할 수 있음
  • f(1)부터 f(n)까지 구하려면 1+2+...+n번 연산해야돼서 나이브(별 다른 처리를 하지 않다)하게 구하면 O(N^2) but 최적화를 통해 O(N)으로 만들기
• f(i)=구간 [1,i]의 원소의 합 ---> f(i-1)=구간 [1,i-1]의 원소 합.
  • f(i-1)을 안다면 f(i)=f(i-1)+A[i]로 O(1)만에 구할 수 있다.
  • f(1)=A[1]이므로 이도 O(1)이다.
• prefix sum: 각 f(i)를 구하는데 O(1)밖에 들지 않고, 총 N개를 구하므로 O(N)으로 f(1)부터 f(n)을 모두 구할 수 있다.

 

2차원 prefix sum

• 이번에도 마찬가지로 f(1)부터 f(n)까지 다 구해보기
• 각 행을 구분해주기 위해 인자를 하나 더 넣기. f(i,j)와 같이!
  • f(i,j)=i행에 대해 구간 [1,j]에 속한 원소의 합 ==> 1행부터 N행까지 모두 prefix sum 구해주기 
  • ==> 그렇게 구한 구간합을 아래로 한 번 더 구간합 해보기
• (1,1)을 꼭짓점으로 가지는 사각형을 쉽게 구할 수 있음 but 다른 경우는 어려움
  • 우리가 원하는 값이 기준을 포함하지 않기 때문. prefix sum은 어떠한 기준으로부터 값을 연속적으로 계산한 것 -> 원하는 값을 얻기 위해 값을 제해줘야 함

• 간단한 포함배제를 이용하여 위 사각형에서 f(x2, y2) - f(x1-1, y2) - f(x2, y1-1) + f(x1-1, y1-1) 으로 구할 수 있다.

 

prefix sum의 한계

Q. prefix sum에서 중간에 이 바뀌면 완전 통째로 다시 수정해야되는 거 아닙니까?!

A. 일단은 마즘. 누적합이 포함하고 있는 값이 변경되면 그 누적합도 변하게 된다. 그러나 그것을 변경해주기 위해 최대 O(N)번의 수정을 해야 한다. 따라서 누적합은 구성에 O(N), 쿼리에 O(1), 업데이트에 O(N) 소요.

• 또 해당 연산의 역연산이 존재해야 한다.
  • 덧셈의 역연산: 뺄셈, 곱셈의 역연산: 나눗셈
  • 역연산이 있다면 특정 구간의 값을 prefix sum으로 구할 수 있음(구간의 합, 구간의 곱 등)
    • 쓸모없는 값을 제해야만 함, 쓸모없는 값을 제하기 위해서는 역연산 반드시 필요.

Description

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지의 최댓값을 구하는 프로그램을 작성하시오.

 

Input

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

 

Output

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지의 최댓값을 출력한다.

Limit

● 1 ≤ N ≤ 100,000

● 1 ≤ M ≤ 100,000

● 1 ≤ i ≤ j ≤ N

위와 같은 문제에서 사용하기 어려움(관심없는 구간의 값을 제거할 때 문제 생김)

즉, 업데이트가 있거나 역연산이 존재하지 않는  경우 사용하기 어려워짐

 

two pointer

Description

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

 

Input

첫째 줄에 N(1 ≤ N ≤ 100,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000 을 넘지 않는 자연수이다.

 

Output

첫째 줄에 경우의 수를 출력한다.

• 누적합으로 푸는 방법
  • N제한에 상관없이 시간복잡도는 O(N^2)
  • N이 최대 10만이므로 O(N^2)로는 못 풂
  • 투포인터를 쓰면 시간복잡도를 O(N^2)보다 빠르게 풀 수 있음   

two pointer

• 배열에서 두 개의 포인터를 사용하여 조건을 만족하는 부분을 찾는 알고리즘
  1. 두 개의 포인터 위치 설정
  2. 조건 검사
  3. 포인터 옮기기
  4. 2,3 반복

• 문제의 조건을 충족하는지 알아보기 위하여 구간의 합을 들고 다니자.
  • 'x을 들고 다니다' : x라는 값을 언제든 빠르게 사용하기 위하여 변할 때마다 계속 갱신하는 것.
• 일단 지금은 두 포인터 모두 0에 있으니 당연히 합은 0. L이 R보다 오른쪽으로 가면 안되니 R을 오른쪽으로 한 칸 옮긴다.

• L을 옮긴다면 구간이 줄어들며 S가 줄어들 것, 이는 우리가 원하는 것이 아니다.
• R을 옮기되 어차피 S<M이면 오른쪽을 계속 옮길테니까 S<M이 아닐 때까지 옮겨주자.

• 이제 S<M이 아니게 되었다. S=M이라면 답에 1이 더해지겠지만 그러지 않았다.
• 어차피 R을 옮기면 옮길수록 S가 커지기만 하므로 우리의 목표와는 반대된다.
  • 따라서 구간을 늘리는것보다는 줄이는 것이 맞다. L을 옮겨보자.

• 이제는 L,R 중 무엇을 움직이는 게 좋을까?

정답: 아무거나. 왜냐하면 배열에 적혀있는 수가 1 이상이므로 L을 옮기면 S<M, R을 옮기면 S>M인 상황이 오게 된다. 결국 뭘 먼저 옮기든 같은 상황으로 귀결.

 

코드

int n,m;
cin >> n >> m;

for(int i=1; i<=n; i++)
	cin >> A[i];
    
int s=0, ans=0;
for(int l=1; r=0; l<=n; l++){
	while(r<n && s<m){
    	r++;
        s += A[r];
      }
      if (s==m) ans++;
      s -= A[l];
  }
  cout << ans << endl;

 

시간복잡도

• 결국 L,R이 시작지점에서 종료지점까지 이동하면 종료됨
• 이동은 L이 O(N)번, R이 O(N)번 할 수 있음
• 이동을 할 때마다 조건에 대해서 검사했는데, 검사는 O(1)로 처리함.
• 따라서 시간복잡도는 O(N)

어떤 상황에 써야할까

• 문제에서 요구하는 것이 조건을 만족하는 두 쌍같은 형태이고, 조건을 맞추기 위해 현재 보고 있는 쌍 중 움직여야 하는 포인터가 명확할 때 사용.
• 위 문제에서 A[i]가 0이나 음수가 될 수 있었다면 그 문제는 투포인터로 풀 수 없음.
• 투포인터는 문제에서 요구하는 두 쌍을 포인터로 표현. 구간도 쌍의 일종([s,e]로 표현가능)
  • 새로운 정답쌍을 찾기 위해 포인터를 움직일 때, 움직이면 손해인 포인터를 찾아야 함.
  • 하지만 A[i]가 양수가 아니라면 'L을 움직이면 S가 감소한다, R을 움직이면 S가 증가한다.' 라는 대전제가 깨지기 때문에 투포인터를 사용할 수 X