누적합 확장해서 생각해보기 (feat. Imos)

2024. 7. 2. 09:59·알고리즘

최근 알고리즘을 풀다가 몰랐던 알고리즘 유형이 있어서 정리해보려고 한다!

특정 구간이 중첩되는 횟수를 계산하는 문제였는데, 완탐으로 풀다가 시간초과가 발생했다 ㅠㅠ 이후로 찾아보다 누적합을 확장해서 풀 수 있다는 것을 알게 되었고, 정리해보려고 한다.

 

 

누적합 개념

누적합이란 ?

  • 배열의 특정 구간의 합을 계산하기 위해, 배열 각 요소들을 누적 계산하고 저장한다.
  • 특정 구간의 합을 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);

	}
}

 

'알고리즘' 카테고리의 다른 글

최단경로  (0) 2023.01.27
다이나믹 프로그래밍  (0) 2023.01.26
이진탐색  (1) 2023.01.25
정렬  (1) 2023.01.19
DFS / BFS  (0) 2023.01.12
'알고리즘' 카테고리의 다른 글
  • 최단경로
  • 다이나믹 프로그래밍
  • 이진탐색
  • 정렬
gani+
gani+
꾸준히 기록할 수 있는 사람이 되자 !
  • gani+
    Gani_Dev :)
    gani+
  • 전체
    오늘
    어제
    • 분류 전체보기 (43)
      • 당장 프로젝트 (2)
        • 트러블슈팅 (0)
      • 댕댕어디가 프로젝트 (11)
        • 트러블슈팅 (3)
        • MSA (8)
      • 개발일지 (2)
      • BOOK (12)
        • SQL 레벨업 (10)
      • 프로젝트 (0)
      • ELK (5)
      • 알고리즘 (9)
      • CS (2)
        • 디자인패턴 (2)
  • 블로그 메뉴

    • 홈
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    9095
    후기
    완전탐색
    순차탐색
    DP
    SW마에스트로
    이것이코딩테스트다
    백준4963
    알고리즘
    섬의개수
    다이나믹프로그래밍
    SWMaestro14
    다익스트라
    백준
    dfs
    4963
    플로이드워셔
    정렬
    4673
    이것이 코딩 테스트다
    최단경로
    해쉬
    이진탐색
    14기
    소마
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
gani+
누적합 확장해서 생각해보기 (feat. Imos)
상단으로

티스토리툴바