최근 알고리즘을 풀다가 몰랐던 알고리즘 유형이 있어서 정리해보려고 한다!
특정 구간이 중첩되는 횟수를 계산하는 문제였는데, 완탐으로 풀다가 시간초과가 발생했다 ㅠㅠ 이후로 찾아보다 누적합을 확장해서 풀 수 있다는 것을 알게 되었고, 정리해보려고 한다.
누적합 개념
누적합이란 ?
- 배열의 특정 구간의 합을 계산하기 위해, 배열 각 요소들을 누적 계산하고 저장한다.
- 특정 구간의 합을 O(1) 시간 복잡도 안에 구할 수 있다.
- 누적합의 구체적인 설명은 생략
// 누적합 활용해서 4~5 인덱스 합 구하기 예시
int[] arr = {1, 2, 3, 4, 5};
for(int i = 1; i < arr.length; i++) {
arr[i] = arr[i-1]+arr[i];
}
int sum = arr[4]-arr[2];
System.out.println(sum);특정 구간 중첩 영역 구하기 (feat. imos)
- 누적합을 활용하면 특정 구간에서 중첩되는 영역을 구할 수 있다.
- 다른 분들은 imos 알고리즘이라고 부르는데, 공식적인 알고리즘은 아니다.
- 특정 구간에서 중첩되는 횟수를 계산하기 위해, 특정 구간에 동일한 연산이 필요될 때 사용하기 좋다. (특히 , N이 클때 시간초과 방지할 수 있음!)
- 아래 문제를 예시로 이해해보면 좋을 것 같다.
문제 예시 - 시간이 겹칠까 ?
https://www.acmicpc.net/problem/28018
예제 입력2 를 예시로 들어보자
- A 학생은 1시부터 5시까지 좌석을 사용하고, B학생은 3시부터 6시까지 사용한다.
- 즉, 2시에는 1개의 좌석이 , 3시에는 2개의 좌석이, 7시에는 0개의 좌석이 사용되고 있다.
- 설명을 위해 핑크 사용시간을 A , 주황 사용시간을 B라고 정의한다.
- 그럼 어떻게 매시간마다 좌석 사용 유무를 체크할 수 있을까 ?
1. 완전탐색 이용
- S와 E 사이에 포함되는 모든 시간을 탐색하여, 사용하고 있는 좌석의 개수를 증가시킨다.
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
int[] usingTime = new int[1_000_000+2];
for(int i =0;i<N;i++){
st = new StringTokenizer(br.readLine());
int S = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
for(int time = S;time<=E;time++){
usingTime[time] ++;
}
}
int Q = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for(int i =0;i<Q;i++){
int time = Integer.parseInt(st.nextToken());
System.out.println(usingTime[time]);
}
}- 하지만 완전탐색을 이용하면 시간초과가 발생한다.
- N의 범위와 S,E의 범위가 크기 때문에 최대 (100,000 * 1,000,000) 번 연산이 발생하기 때문이다.
2. 누적합 이용
- 사용하고 있는 좌석의 개수를 시간대별로 누적합으로 계산한다.
- 사용을 시작하는 시간에는 +1 , 끝났을 때는 -1을 한다.
- +1 은 사용하는 좌석이 1개 늘어났음을, -1은 1개의 좌석이 사용 종료되었음을 뜻한다.
- A와 B는 5시, 6시에 끝나긴하지만, 종료된 시간에 바로 다른 사람이 사용할 수 없으므로, 실제 사용이 가능한 6시,7시에 -1을 한다.
- 누적합으로 시간대마다 몇개의 좌석이 사용되고 있는지 계산한다.
- 2시에는 1개의 좌석이 , 3시에는 2개의 좌석이 , 7시에는 0개의 좌석이 사용되고 있는 것을 확인할 수 있다.
- 누적합 확장하여 문제를 해결하면, 최대 (1,000,000)번의 연산으로 결과값을 구할 수 있다.
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
int[] usingTime = new int[1_000_000+2];
int maxEnd = 0;
for(int i =0;i<N;i++){
st = new StringTokenizer(br.readLine());
int S = Integer.parseInt(st.nextToken());
int E = Integer.parseInt(st.nextToken());
usingTime[S]++;
usingTime[E+1]--;
if(maxEnd < E+1) maxEnd = E+1;
}
int sum = 0;
for(int i =0;i<=maxEnd;i++){
sum += usingTime[i];
usingTime[i] = sum;
}
int Q = Integer.parseInt(br.readLine());
st = new StringTokenizer(br.readLine());
for(int i =0;i<Q;i++){
int time = Integer.parseInt(st.nextToken());
System.out.println(usingTime[time]);
}
}유사문제
프로그래머스
코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.
programmers.co.kr
더보기
코드
class Solution {
public int solution(int[][] board, int[][] skill) {
int answer = 0;
int rowMax = board.length;
int colMax = board[0].length;
int[][] degrees = new int[rowMax][colMax];
for(int[] sk : skill){
int type = sk[0];
int r1 = sk[1];
int c1 = sk[2];
int r2 = sk[3];
int c2 = sk[4];
int degree = sk[5];
if(type == 1){
degrees[r1][c1] -=degree;
if(c2+1<colMax){
degrees[r1][c2+1] +=degree;
}
if(r2+1<rowMax){
degrees[r2+1][c1] +=degree;
if(c2+1<colMax){
degrees[r2+1][c2+1] -=degree;
}
}
}else{
degrees[r1][c1] +=degree;
if(c2+1<colMax){
degrees[r1][c2+1] -=degree;
}
if(r2+1<rowMax){
degrees[r2+1][c1] -=degree;
if(c2+1<colMax){
degrees[r2+1][c2+1] +=degree;
}
}
}
}
int cnt = 0;
for(int i =0;i<rowMax;i++){
int sum =0;
for(int j = 0;j<colMax;j++){
sum+=degrees[i][j];
degrees[i][j] = sum;
}
}
for(int j = 0;j<colMax;j++){
int sum =0;
for(int i =0;i<rowMax;i++){
sum+=degrees[i][j];
degrees[i][j] = sum;
board[i][j] = board[i][j]+degrees[i][j];
if(board[i][j] <= 0){
cnt++;
}
}
}
answer = rowMax*colMax-cnt;
return answer;
}
}
더보기
코드
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int H = Integer.parseInt(st.nextToken());
int[] blocks = new int[H+1];
for(int i =1;i<=N;i++){
int height = Integer.parseInt(br.readLine());
if(i%2 != 0){
//석순
blocks[1] +=1;
blocks[height+1] -=1;
}else{
//종유석
blocks[H-height+1] +=1;
}
}
int sum =0;
int min = N;
blocks[0] = -1;
for(int i =1;i<=H;i++){
sum+=blocks[i];
blocks[i]=sum;
min = Math.min(min,blocks[i]);
}
int finalMin = min;
int cnt = (int)Arrays.stream(blocks).filter(x->x== finalMin).count();
System.out.println(min+" "+cnt);
}
}