imos 법

누적합 문제에 적용

 

 What ?

imos 법

 

 -  정해진 구간 내에 시작과 끝 이 포함된 부분 집합에 대한 명령이 여러개 들어올 때,  연산 시간을 줄이는 방법입니다.

 

 

How ?

  

 -  구간의 시작점과 끝점 에 해당하는 위치를 기록합니다.

  ( 구간의 시작 지점에는 특정 값을 더하고, 구간의 끝 지점 다음에는 해 당 값을 빼서, 구간을 표시 합니다. )

 

 -  표시한 배열을 사용하여 각 지점에서의 누적 값을 계산합니다.

    ( 이를 통해 각 지점에서의 구간의 개수나 발생 횟수를 구할 수 있습니다. )

 

 -  필요에 따라 누적 값을 이용하여 원하는 처리를 수행합니다.

 

1차원 배열에서 구현 

let imos = [ ... ]
let now = 0;
for (let i = 0; i < imos.length; i++) {
    now += imos[i];
    imos[i] = now;
}

 

 - 1차원 배열을 생성하고 값을 0으로 초기화한 후, 시작점에 1을 더하고 끝점에 1을 빼줍니다.

2차원 배열에서 구현 

let imos = [ ... ]

for (let i = 0; i < imos.length; i++) {
    let now = 0;
    for (let j = 0; j < imos[0].length; j++) {
        now += imos[i][j];
        imos[i][j] = now;
    }
}

for (let i = 0; i < imos[0].length; i++) {
    let now = 0;
    for (let j = 0; j < imos.length; j++) {
        now += imos[j][i];
        imos[j][i] = now;
    }
}

 - 2차원 배열의 경우 사각형의 꼭지점을 시작점과 끝점으로 생각합니다.
 
 - 행과 열을 구별해 2번 반복해줍니다.