📙[Algo] 24.01.25 누적합 / 알고리즘

누적합 정리

쿼리 문제

• 수열, 트리, 그래프 등 무얼 하나 주고 Q번 반복하라는 문제
• 종류
  1️⃣ 점 update O(1)
  ex) 세 번째 값을 5로 바꿔라, 세 번째 값에 3을 더해라.
  2️⃣ 구간 update O(n)
  ex) [2, 5] 구간에 3씩 더해라, [1, 3] 구간을 모두 2로 바꿔라.
  3️⃣ 점 get O(1)
  ex) 세 번째 값이 뭐냐? 다섯 번째 값이 홀수냐?
  4️⃣ 구간 get O(n)
  ex) [1, 3] 구간의 합을 구해라, [2, 5]구간에 짝수가 몇 개 있냐?
• 쿼리 문제의 경우 어떤 자료구조나 알고리즘을 사용해서 최적화 진행
  • 누적합, 세그먼트 트리(G1), 펜윅 트리(G1) 등..
    • 누적합의 경우 점 update는 빠르나, 구간 update는 느리다
    • 세그먼트 트리의 경우 구간 get은 빠르나 구간 update는 느리다
• 쿼리 문제는 코딩테스트에 많이 나오지 않지만, 만약 나온다면 대부분 누적합으로 풀린다.
• 누적합은 기본적으로 쿼리문제를 빠르게 해결하는 알고리즘이다.

기본 누적합

• 업데이트가 없고, 구간 get이 계속 주어지는 경우 누적합을 사용한다.

BOJ11659. 구간 합 구하기 4

11659번: 구간 합 구하기 4

수 N개가 주어짐

5 4 3 2 1

• 누적합 prefix 배열 만들기

  0

  5

  9

  12

  14

  15

  • 배열 크기를 하나 늘려서 앞에 0 인덱스는 비워두고 사용하는 게 좋다. (i-1에 접근할 때 예외 처리하기 번거롭다)
  • prefix[i] : [1, i] 구간의 합
  • 어떻게 만들까?
    • prefix[i] = prefix[i-1] + arr[i]
      ⇒ 하나하나를 O(1)에 구하니까 총 O(n)
  • 어떻게 쓸까?
    • [s, e] 구간의 합을 구한다면
      prefix[e] - prefix[s - 1]
      ⇒ O(1)에 구할 수 있다
      ⇒ 구간 get쿼리를 점 get쿼리 둘로 바꾼다.
  • 즉, 원본 배열의 구간 get 쿼리 == prefix 배열의 점 get 쿼리
• 문제를 풀다보니, 구간 get이 너무 많다. 그래서 점 get으로 바꿔서 문제를 풀자!
• 연속 부분 수열을 자꾸 읽어야 한다. 몇 개의 점만 보면서 처리하고 싶다.

BOJ2015. 수들의 합 4

2015번: 수들의 합 4

💡원본 배열의 연속 부분 수열 == 누적합 배열 (뒤의 값) - (앞의 값)

• 원래 문제 : arr의 연속 부분 수열 중 합이 5인 것의 개수를 구하자
  0 1 2 3 4 5 0 (k = 5)
• 바뀐 문제(누적합 적용 후) : 뒤의 갚에서 앞의 값을 뺄 때 5가 되는 쌍의 개수
  0 1 3 6 10 15 15
  •  cnt[i]
    • 이제까지 i가 몇 개 나왔는지
  • answer += cnt[prefix[i] - k]
    • 예를 들어, 15입장에서(prefix[5]) 앞의 값을 뺄 때 5가 나오려면 앞의 값이 10이 나와야 한다. 즉, cnt[prefix[5] - 5] 는 cnt[10]이 되고, 지금까지 10이 나온 개수는 15에서 앞의 값을 뺐을 때 5가 되는 쌍의 개수가 된다.
  • cnt[prefix[i]] += 1
    • 그리고, 현재 숫자의 개수를 하나 늘려준다.
• cnt 배열을 못 만드는 경우가 있다면
  • java의 경우 TreeMap을 사용해야 한다. (C++는 map, Python은 dict)
    • HashMap은 해쉬 함수가 일부 테스트케이스에 해쉬 충돌이 일어나면 O(n)이 걸리기 때문에 비추!(알고리즘 한정)

응용

BOJ2559. 수열

2559번: 수열

문제 요약 : 연속된 K개의 부분 수열 중 최대 합계 출력

• 구간 쿼리가 계속 주어지므로 누적합으로 최적화를 하겠다.
• 투포인터의 슬라이딩 윈도우를 사용할 수도 있다.
  • 슬라이딩 윈도우 : 투포인터의 구간을 찾을 때 간격을 유지하며 이동하는 경우 사용하는 알고리즘
  • 자벌레 알고리즘(inchworm) : 투포인터의 구간을 찾는 다른 이름

예시

1️⃣ [ s, e ] 구간에 b가 몇 개 있냐?
0 a b c d e b a b a b c
0 0 1 1 1 1 1 1 2 2 3 3
⇒ 인덱스 e에 접근하면 b 개수를 구할 수 있음(구간 → 점)

2️⃣ 내 앞/뒤 구간의 최댓값?

• 내 앞에는 누가 제일 클까? ( → )
  0 1 3 5 2 6 2 3 8 3
  0 1 3 5 5 6 6 6 8 8
• 내 뒤에는 누가 제일 클까? ( ← )
  0 1 3 5 2 6 2 3 8 3
  8 8 8 8 8 8 8 8 8 3

⇒ 배열을 미리 만들고 갖다 쓰기

 

누적합의 약점

• 원본 배열의 점 update를 하게 되면 구간 update가 되어 버린다.
  • 즉, get은 다 O(1)인 장점이 있지만, update가 다 O(n)이 된다는 단점이 있다.

2차원 누적합

BOJ11660. 구간합 구하기5

2차원 배열에서 구간합 구하기 ex) (2,2) ~ (4,3) 합계 구하기

예를 들어, 2차원 배열에서 (3,2)까지의 구간을 묻는다면 아래처럼 생각할 수 있다.

구간합 적용하기

만약 (3,3)까지의 구간합을 구하고 싶다면, (3,2)까지의 구간합(15) + (2,3)까지의 구간합(15) - 겹쳐지는 부분인 (2,2)까지의 구간합(8) + (3,3)의 원소값(5)를 통해 구할 수 있다.

prefix[i][j] = prefix[i][j - 1] + prefix[i - 1][j] - prefix[i - 1][j - 1] + arr[i][j]

 

같은 로직으로 특정 구간의 합을 구하는 것도 가능하다. ⇒ 2차원은 직접 그림으로 그려보고 이해하며 풀기!

imos

• 구간 업데이트가 계속 주어진 뒤, 모든 끝난 다음 get을 하는 경우 imos를 사용할 수 있다.
• 즉, 업데이트를 모두 한 시점에 누적합 배열을 구한다.
• 원본 배열에서 하나가 바뀌면 누적합 배열에선 뒤가 다 바뀌기 때문에 업데이트할 위치의 양끝점만 업데이트
  • [s, e] 구간을 업데이트 한다면(+v)
    arr[s] 에 +v
    arr[e + 1]에 -v
• 예시
  원본 배열
  0 1 2 3 4 5 6 7 8
  0 0 0 0 0 0 0 0 0
  
  [3, 5] 구간에 2씩 더할 경우, 원본 배열에 아래와 같이 업데이트 진행
  0 1 2 3 4 5 6 7 8
  0 0 0 2 0 0 -2 0 0
  
  [2, 6] 구간에 3씩 더할 경우, 원본 배열에 아래와 같이 업데이트 진행
  0 1 2 3 4 5  6  7  8
  0 0 3 2 0 0 -2 -3 0
  
  [1, 5] 구간에 5씩 더할 경우, 원본 배열에 아래와 같이 업데이트 진행
  0 1 2 3 4 5  6  7 8
  0 5 3 2 0 0 -7 -3 0
  
  업데이트 후 누적합을 적용하면
  0 1 2    3  4  5  6 7 8
  0 5 8 10 10 10 3 0 0

BOJ3020. 개똥벌레

3020번: 개똥벌레

문제 요약 : 최대한 장애물 적게 만나는 층 개수와 그 때의 장애물 개수 구하기

1. 완전 탐색으로 접근하기
   • 기둥을 중심을 접근할 수 있다. 기둥 높이가 다음과 같이 주어진다면,
     1 5 3 3 5 1
     

     1	2	3	4	5	6	7
     1
     		1	1	1	1	1
     2	1	2
     				2	2	2
     3	2	3	2	3
     						3

2. 최적화 하기
   • 1 5 3 3 5 1 은 아래처럼 해석할 수 있음.
     [1,1], [3,5], [1,3], [5,7], [1,5], [7,7] 구간을 업데이트 ⇒ 즉, 구간 업데이트를 n번 진행

 

누적합 적용하는 문제 생각해보기,,,

• 문제에서 연속 부분 수열이 주어질 경우, 구간의 합을 구해야 할 때 → 누적합이 더 빠르다고 생각하면 적용
• 구간 쿼리를 빠르게 진행하고 싶을 때
• 구간 업데이트가 계속 주어지고, 결과를 한 번에 볼 때

---

알고리즘 문제) BOJ 11659. 구간 합 구하기 4

11659번: 구간 합 구하기 4

문제 요약

• 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합 구하기

시간 제한

• 1초

입력

• N M
  • N : 수 개수 (1≤N≤10만)
  • M : 구해야 하는 횟수 (1≤M≤10만)
• N개의 수가 공백으로 주어짐
  • 수는 1000이하 자연
• M개의 줄에 합을 구할 구간 i j가 주어짐 (1≤i≤j≤N)

출력

• 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합 출력

접근법

1. 완전 탐색으로 접근하기
   • 주어진 쿼리의 구간마다 합계를 구하고 출력
   • 10만 * 10만 ⇒ 최대 100억개 연산 필요
2. 최적화 진행
   • 모든 구간을 일일이 합계를 구하면 안 됨
   • 구간 → 점으로 치환할 수 있는 구간합 배열을 사용

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            arr[i] = arr[i-1] + Integer.parseInt(st.nextToken());
        }

        int s, e;
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            s = Integer.parseInt(st.nextToken());
            e = Integer.parseInt(st.nextToken());

            sb.append(arr[e] - arr[s - 1] + "\n");
        }

        bw.write(String.valueOf(sb));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 2559. 수열

2559번: 수열

문제 요약

• 매일 측정한 온도가 정수 수열로 주어질 때, 연속적인 K일 동안의 온도의 합이 가장 큰 값 계산

시간 제한

• 1초

입력

• N K
  • N: 온도 측정한 날짜 수 2≤N≤10만
  • K: 합을 구하기 위한 연속적인 날짜 수 1≤K≤N
• 매일 측정한 온도를 나타내는 N개의 정수가 빈칸으로 주어짐
  • -100이상 100이하

출력

• 온도 수열에서 연속적인 K일의 온도 합이 최대가 되는 값 출력

접근법

1. 완전 탐색으로 접근하기
   • 2중 for문 사용해서 케이스별로 앞에서부터 하나하나 합계를 구한다.
   • 최악의 경우 10만 * 10만 ⇒ 시간초과
2. 최적화 하기
   • 1일차부터 하나하나 돌긴 해야함
   • 합계를 구하는 부분을 최적화 할 것
     • 구간 → 점
     • 부분 연속 수열 합계 → 구간합 적용
     • 구간합 배열 사용하기
     • 또는 투포인터를 사용해도 될 것 같음
       • 한 칸씩 이동할 때마다 추가되는 부분, 삭제되는 부분만 더하고 빼면 되니까!

코드

구간합 사용

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N + 1];
        for (int i = 1; i <= N; i++) {
            arr[i] = arr[i-1] + Integer.parseInt(st.nextToken());
        }

        int answer = Integer.MIN_VALUE;
        for (int i = 1; i <= N - K + 1; i++) {
            answer = Math.max(answer, arr[i + K - 1] - arr[i - 1]);
        }

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

투포인터 사용

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int[] arr = new int[N + 2];
        for (int i = 1; i <= N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int answer = Integer.MIN_VALUE;
        int s = 1, e = K, sum = 0;
        for (int i = s; i <= e ; i++) {
            sum += arr[i];
        }
        while (e <= N) {
            answer = Math.max(answer, sum);

            e++;
            sum += arr[e];

            sum -= arr[s];
            s++;
        }

        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}

 

알고리즘 문제) BOJ 14453. Hoof, Paper, Scissors (Silver)

14453번: Hoof, Paper, Scissors (Silver)

문제 요약

• 발굽 > 가위
• 가위 > 종이
• 종이 > 발굽
• N번의 게임 진행(1≤N≤10만)
• 농부 존과 소 베시가 대결
  • 소는 같은 제스처를 여러번 사용하는 경향
    • 예를 들어, 처음 x게임동안 “발굽”, 나머지 N-X 게임 동안 “종이”
• 존이 할 제스처 순서가 주어졌을 때, 베시가 이길 수 있는 최대 게임 수?

시간 제한

• 2

입력

• N(1≤N≤10만)
• N개의 줄에 존의 제스처가 포함
  • 발굽 H, 가위 S, 종이 P
    • H > S
    • S > P
    • P > H

출력

• 베시가 딱 한 번만 바꿀 수 있다면, 이길 수 있는 최대 게임 수?

접근법

P P H P S
이기기 위해서는 다음과 같이 내야 함
      S S P S H
S : 1 2 2 3 3
P : 0 0 1 1 1
H : 0 0 0 0 1

S : 3 2 1 1 0
P : 1 1 1 0 0
H : 1 1 1 1 1

1. 완전 탐색으로 접근한다면?
   H~P까지 각각 인덱스 1부터 N-1까지만 내고, 그 다음 다른 2개중 하나를 냈을 때 이기는 횟수를 모두 구해 본다. ⇒ 3(가위 바위 보 중 하나 고르기)*10만(그 중 하나의 끝 포인트 지정한 곳 까지 이긴 횟수 카운팅)*3(나머지 가위 바위 보 중 하나 고르기)*10만(나머지 하나로 채웠을 때 이긴 횟수 카운팅)
   ⇒ 시간초과
   ⇒ 2중 for문을 하면 무조건 시간초과가 뜸
2. 최적화 생각하기
   • prefix랑 suffix를 만든다.
   • 3*10만 안에 돌 수 있게 할 것
     • 인덱스 1부터 N까지 다음과 같은 순서대로 진행
       • 가위, 바위, 보 별로(3번)
       • prefix[i] + suffix[i+1] 더했을 때 최대값으로 갱신한다.
         ⇒ 결국 310만3이 걸린다!!!!

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());

        // H : rock, S : scissor, P : paper
        String[] play = new String[N + 1];
        // prefix 만들기(각 동작별 등장 횟수)
        int[][] prefix = new int[3][N + 2]; // 0 : rock, 1 : scissor, 2 : paper
        for (int i = 1; i <= N; i++) {
            play[i] = br.readLine();

            prefix[0][i] += prefix[0][i-1];
            prefix[1][i] += prefix[1][i-1];
            prefix[2][i] += prefix[2][i-1];

            if (play[i].equals("H")) prefix[0][i]++;
            else if (play[i].equals("S")) prefix[1][i]++;
            else prefix[2][i]++;
        }

        // suffix 만들기
        int[][] suffix = new int[3][N + 2]; // 0 : rock, 1 : scissor, 2 : paper
        for (int i = N; i >= 1 ; i--) {
            suffix[0][i] += suffix[0][i+1];
            suffix[1][i] += suffix[1][i+1];
            suffix[2][i] += suffix[2][i+1];

            if (play[i].equals("H")) suffix[0][i]++;
            else if (play[i].equals("S")) suffix[1][i]++;
            else suffix[2][i]++;
        }

        int answer = 0;
        for (int i = 0; i < 3; i++) {
            // 1 : rock, 2 : scissor, 3 : paper
            // 제스처 1 결정(prefix)
            for (int j = 1; j <= N; j++) {
                for (int k = 0; k < 3 ; k++) {
                    // 제스처 2 결정(suffix)
                    answer = Math.max(answer, prefix[i][j] + suffix[k][j+1]);
                }
            }
        }



        bw.write(String.valueOf(answer));
        bw.flush();
        bw.close();
        br.close();
    }
}