[알고리즘] 누적합 문제를 효율적으로 풀 수 있는 imos 법

정의

imos 법
누적합 문제에서 쓸 수 있는 개념
정해진 구간 내에 시작과 끝이 포함된 부분 집합에 대한 명령이 여러개 들어올 때, 반복적으로 연산하게 되면 연산 시간이 매우 커질 수 있다.

상황에 대해 예시를 들어보자.

0시부터 12시까지 한 장소에 n명의 사람이 입장과 퇴장을 반복할 때 각 시간에 대해 장소에 존재했던 사람이 몇명인지 구해야하는 상황 등에서 사용할 수 있는 개념이다.

구현

imos법은 각 명령에 대해 시작점과 끝점만 설정해 준 뒤, 마지막에 한 번의 반복을 통해 값을 계산하는 방식으로 구현할 수 있다.

1차원 배열에서의 구현

위의 예시와 같은 상황에서는 1차원 배열을 이용해서 구현할 수 있다.
먼저 각 시간에 대한 1차원 배열을 생성하고 값을 0으로 초기화 해준다. 그 후 각 명령에 대해 입장한 시간에 +1, 퇴장한 시간에 -1을 해준다.

만약 A(1시 ~ 4시), B(2시 ~ 8시), C(3시 ~ 12시), D(4시 ~ 8시) 동안 장소에 있었다면 배열의 값은 [0,1,1,1,0,0,0,0,-2,0,0,-1] 이 된다.

이렇게 배열의 값을 모두 만들어 준 뒤 배열에 대해 for문을 돌리면서 값을 계산해주면 된다.
계산해주는 방식은 변수를 하나 생성해서 각 index마다 저장된 값을 변수에 업데이트해주고 그 자리에 그 업데이트한 변수의 값을 넣어준다.

imos = [0,1,1,1,0,0,0,0,-2,0,0,-1]
now = 0
for i in range(12):
   now += imos[i]
   imos[i] = now

이런 식으로 하면 효율성을 지키면서 누적합 문제를 풀 수 있다!
예시 문제 -> 백준 3020 '개똥벌레'

2차원 배열에서의 구현

2차원 배열의 경우는 명령이 2차원 배열로 들어오기 때문에 사각형 모양에서의 각 꼭지점을 시작과 끝으로 생각해서 구현할 수 있다.

먼저 시작, 끝을 표시하는 배열을 생성하는 방식은

명령이 위의 그림처럼 사각형 구간 안의 값을 변경해야한다고 했을 때, X 표시한 각 모서리의 값을 변경해준다.
1. 사각형이 시작하는 부분 (왼쪽 위 점) : +1
2. 시작 부분에서 가로, 세로로 나아갔을 때 범위가 끝나는 부분 (빨간색 표시 지점) : -1
3. 사각형이 끝난 부분 (구간 밖 오른쪽 아래 점) -1 해준 걸 상쇄하기 위해 다시 : +1

이런 방식으로 배열을 생성해주고 다시 값을 계산해줄 때에는 가로와 세로를 나눠서 두 번 반복문을 돌려준다.

for i in range(len(imos)):
        now = 0
        for j in range(len(imos[0])):
            now += imos[i][j]
            imos[i][j] = now

    for i in range(len(imos[0])):
        now = 0
        for j in range(len(imos)):
            now += imos[j][i]
            imos[j][i] = now

특히 2차원 배열에서의 누적합을 구할 때 효율성 문제가 많이 생기기 때문에 imos법을 적용해서 반복을 최소화해주는 것이 좋다.
예시 문제 -> 카카오 2022 블라인드 채용 '파괴되지 않은 건물'