시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
| 1 초 | 256 MB | 84218 | 38505 | 28563 | 43.919% |
문제
N×N개의 수가 N×N 크기의 표에 채워져 있다. (x1, y1)부터 (x2, y2)까지 합을 구하는 프로그램을 작성하시오. (x, y)는 x행 y열을 의미한다.
예를 들어, N = 4이고, 표가 아래와 같이 채워져 있는 경우를 살펴보자.
여기서 (2, 2)부터 (3, 4)까지 합을 구하면 3+4+5+4+5+6 = 27이고, (4, 4)부터 (4, 4)까지 합을 구하면 7이다.
표에 채워져 있는 수와 합을 구하는 연산이 주어졌을 때, 이를 처리하는 프로그램을 작성하시오.
입력
첫째 줄에 표의 크기 N과 합을 구해야 하는 횟수 M이 주어진다. (1 ≤ N ≤ 1024, 1 ≤ M ≤ 100,000) 둘째 줄부터 N개의 줄에는 표에 채워져 있는 수가 1행부터 차례대로 주어진다. 다음 M개의 줄에는 네 개의 정수 x1, y1, x2, y2 가 주어지며, (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다. 표에 채워져 있는 수는 1,000보다 작거나 같은 자연수이다. (x1 ≤ x2, y1 ≤ y2)
출력
총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.
문제풀이
이 문제는 N*N 크기의 표에서 (x1, y1)부터 (x2, y2)의 합을 구해 출력해야 한다
누적합 배열을 누적합 이차원 배열처럼 만들어서 풀면 될 것 같다.
그러면 누적합 이차원 배열을 만드는 방법과 구간합을 구하는 방식을 만들어보자.
누적합 일차원 배열처럼 만들면 될까?
일차원에서는 누적합 배열을 만들 때 간단했다.
기존 누적합 값과 배열값을 합쳐서 나온 값이 누적합이 되었다.
그래서 공식을 보면 반복문 하나로 간단하다.
// 1. 누적합배열 만들기
int[] acc = new int[N+1];
for(int i=1; i<=N; i++)
acc[i] = acc[i-1] + arr[i];
그러면 이차원 누적합 배열도 만들어보자.
Column과 Row를 누적합 배열로 만들어 줬다.
그러면 이차원을 만드는 방법은? (1,1)로 시작할 때 (2,2)의 값은 무엇일까?
간단하게 기존에 있는 이차원 배열을 계산해보면 8이 나온다.
어떻게 하면 누적합 배열을 구할 수 있는지 분리해보자.
우선 Row, Column 기준이다. 누적(2,1) + 누적(1,2) - (1,1)중복값 + (2,2)를 하면 8이 나오는 것
이제 누적합 이차원 배열을 구하는 방법을 알아봤으니 예제 1을 다 구해보자.
구간합 구하기
이차원 누적합 배열도 구했으니 이제 구간합만 남았다.
(2,2)~(3,4)의 값을 구하면 된다. 이것도 같은 원리로 동작한다.
예제 1에서 첫번째 Query를 대입해봤다.
누적(3,4) - 누적(3,1) - 누적(1,3) + 누적(1,1)를 해주면 된다..!!
이제 위의 값을 일반화하여 공식으로 만들어보자.
이해하기 쉽게 startRow, startColumn, endRow, endColumn으로 만들었다.
sumTable[endRow][endColumn] -
(sumTable[endRow][startColumn -1] + sumTable[startRow-1][endColumn])
+ sumTable[startRow-1][startColumn-1];
코드를 작성해보자
0. 입력받기
// 0. 입력받기
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int[][] table = new int[N+1][N+1];
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++) {
table[i][j] = sc.nextInt();
}
1. 누적합 이차원 배열 생성
// 1. 누적합 이차원 배열 생성
for( int i=1; i<=N; i++) {
for( int j=1; j<=N; j++) {
sumTable[i][j] = sumTable[i-1][j] + sumTable[i][j-1] - sumTable[i-1][j-1] + table[i][j];
}
}
2. 구간합 구하기
// 2. 구간합 구하기
int ans = 0;
for(int i=1; i<=N; i++) {
for(int j=1; j<=N; j++) {
ans = sumTable[endRow][endColumn] - (sumTable[endRow][startColumn -1] + sumTable[startRow-1][endColumn]) + sumTable[startRow-1][startColumn-1];
}
}
전체 코드
import java.util.Scanner;
class Main
{
public static void main (String[] args) {
// 0. 입력받기
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int[][] table = new int[N+1][N+1];
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++) {
table[i][j] = sc.nextInt();
}
int[][] sumTable = new int[N+1][N+1];
while(M-->0) {
int startRow = sc.nextInt();
int startColumn = sc.nextInt();
int endRow = sc.nextInt();
int endColumn = sc.nextInt();
// 1. 누적합 이차원 배열 생성
for( int i=1; i<=N; i++) {
for( int j=1; j<=N; j++) {
sumTable[i][j] = sumTable[i-1][j] + sumTable[i][j-1] - sumTable[i-1][j-1] + table[i][j];
}
}
// 2. 구간합 구하기
int ans = 0;
for(int i=1; i<=N; i++) {
for(int j=1; j<=N; j++) {
ans = sumTable[endRow][endColumn] - (sumTable[endRow][startColumn -1] + sumTable[startRow-1][endColumn]) + sumTable[startRow-1][startColumn-1];
}
}
// 3. 결과 출력하기
System.out.println(ans);
}
}
}
자 이제 답이 잘 나오는지 예제1을 대입해보자!!! 맞았으니 제출을 해보자
흠,, 시간초과네 😤
왜지?? 아.. 지금 반복문에 넣을 필요가 없는 코드를 넣어서 그렇다.. 😱
코드 정리하기
누적합 이차원 배열 생성하는 부분을 while문에서 제거해주고
구간합을 구하는 코드도 반복문을 제거해주자.
import java.util.Scanner;
class Main
{
public static void main (String[] args) {
// 0. 입력받기
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int[][] table = new int[N+1][N+1];
for(int i=1; i<=N; i++)
for(int j=1; j<=N; j++) {
table[i][j] = sc.nextInt();
}
int[][] sumTable = new int[N+1][N+1];
// 1. 누적합 이차원 배열 생성
for( int i=1; i<=N; i++) {
for( int j=1; j<=N; j++) {
sumTable[i][j] = sumTable[i-1][j] + sumTable[i][j-1] - sumTable[i-1][j-1] + table[i][j];
}
}
while(M-->0) {
int startRow = sc.nextInt();
int startColumn = sc.nextInt();
int endRow = sc.nextInt();
int endColumn = sc.nextInt();
// 2. 구간합 구하기
int ans = 0;
ans = sumTable[endRow][endColumn] - (sumTable[endRow][startColumn -1] + sumTable[startRow-1][endColumn]) + sumTable[startRow-1][startColumn-1];
// 3. 결과 출력하기
System.out.println(ans);
}
}
}
출력을 해보면? 굳 시간내에 맞았다.
시간복잡도
이 알고리즘의 시간복잡도를 계산해보면 입력받을때 이중 반복문을 사용하니 O(N^2)
그리고 구간합을 M번만큼 반복하니 O(M) 즉, O(N^2 + M)이 답이다.
[19951] 태상이의 훈련소
시간 제한 메모리 제한 제출 정답 맞힌 사람 정답 비율
| 1 초 | 512 MB | 2796 | 1638 | 1300 | 59.010% |
문제
2020년 5월 14일 논산훈련소에 입대한 태상이는 첫 총기 훈련에서 가스 조절기를 잃어버리는 중대한 실수를 범했다. 그로 인해, 태상이는 조교들에게 눈총을 받게 되었다. 조교들은 태상이에게 연병장(운동장)의 흙을 옮기는 일을 주고 제대로 수행하지 못하면 징계를 내리려고 한다.
연병장은 일렬로 이어진 N개의 칸으로 이루어져 있으며 각 칸마다 높이를 가지고 있고, 첫 번째 칸부터 순서대로 1번, 2번, 3번, ..., N번 칸으로 명칭이 붙어있다. 조교들은 총 M명이 있으며, 각 조교들은 태상이에게 a번 칸부터 b번 칸까지 높이 k만큼 흙을 덮거나 파내라고 지시한다. 흙은 주변 산에서 얼마든지 구할 수 있으므로 절대로 부족하지 않다.
태상이는 각 조교의 지시를 각각 수행하면, 다른 조교의 지시로 흙을 덮어둔 칸을 다시 파내기도 하는 비효율적인 일이 발생하는 것을 깨달았다. 그래서 태상이는 각 조교의 지시를 모아 연병장 각 칸의 최종 높이를 미리 구해 한 번에 일을 수행하려고 한다.
불쌍한 태상이를 위해 조교들의 지시를 모두 수행한 뒤 연병장 각 칸의 높이를 구하자.
입력
첫 줄에 연병장의 크기 N과 조교의 수 M이 주어진다.
둘째 줄에 연병장 각 칸의 높이 Hi가 순서대로 N개 주어진다.
셋째 줄부터 M개의 줄에 각 조교의 지시가 주어진다.
각 조교의 지시는 세 개의 정수 a, b, k로 이루어져 있다.
- k ≥ 0인 경우 a번 칸부터 b번 칸까지 높이가 각각 |k| 만큼 늘어나도록 흙을 덮어야 한다.
- k < 0인 경우 a번 칸부터 b번 칸까지 높이가 각각 |k| 만큼 줄어들도록 흙을 파내야 한다.
출력
모든 지시를 수행한 뒤 연병장 각 칸의 높이를 공백을 사이에 두고 출력한다.
문제풀이
이 문제는 N개의 배열이 주어지고 그안에 Hi가 순서대로 배치가 되는데
Hi를 조교의 명령 (a,b,k)를 받아 [a:b]까지 k를 더하면된다. k는 음수일수도 양수일수도 있다.
물론 시간초과가 나오겠지만 한 번 쉽게 풀어보자.
0. 입력 받기
N,M,H까지 입력받아 다 저장해주자.
그리고 M번만큼 명령을 받아야하니 while문을 사용해서 명령을 받아주자.
// 0. 입력받기
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int M = sc.nextInt();
int[] H = new int[N+1];
for(int i=1; i<=N; i++)
H[i] = sc.nextInt();
while(M-->0) {
int a = sc.nextInt();
int b = sc.nextInt();
int k = sc.nextInt();
}
1. 명령대로 흙을 덮고 파자
2. 마지막 H를 출력하자.
[a:b]까지 k를 더하고 빼주고 모든 명령이 끝나면 출력해보자.
// 1. 흙 덮고 파기
for (int i = a; i <= b; i++) {
H[i] = H[i] + k;
}
// 2. 출력하기
for(int i=1; i<=N; i++)
System.out.print(H[i] + " ");
이제 제출을 해보면?
답은 맞지만 시간초과가 일어난다. 역시 이렇게 간단할리가 없지 골드문제인데 이렇게 편하게 풀수없지 😤
다시 생각해서 풀어보자.
지금 문제는 명령만큼 반복을 해서 시간초과가 나는 것이다.
그러면 명령을 한번에 모두 받아서 추후에 한번만 처리하면 어떨까?
아래 배열을 보게되면 명령을 한번에 받을 수 있을 것 같다.
그러면 해당칸 부터 마지막 칸까지 적용되는 변화량을 기록하는 delta를 통해 실제 각 칸의 변화량을 구해보자.
마지막 지시까지 반영 후 결과만 출력하기 때문에 delta의 적용은 마지막 한 번에 몰아서 반영해도 된다.
누적합 배열을 하기 위해 기존 명령어를 모두 모은 배열을 만들어 보자.
dleta[]: [-3, 2, 0, 0, 0, 5, 0, -2, 0, 0]
accDelta[]: [ -3, -1, -1, -1, -1, 7, 7, 5, 5, 5]
1. 각 지시에 따른 변화량을 기록한다.
배열을 하나 생성하여 모든 지시를 기록해주자.
이때 b+1까지 해주기 위해 N+2만큼 배열을 생성해주자
int[] delta = new int[N+2];
while(M-->0) {
int a = sc.nextInt();
int b = sc.nextInt();
int k = sc.nextInt();
delta[a] += k;
delta[b + 1] -= k;
}
2. 각 칸부터의 변화량을 각 칸에 적용한다.
int[] accDeleta = new int[N+1];
for(int i=1; i<=N; i++)
accDeleta[i] = accDeleta[i-1] + delta[i];
3. 변화량이 적용된 각 칸의 높이를 출력한다.
for(int i=1; i<=N; i++)
System.out.print(H[i] + accDeleta[i] + " ");
시간복잡도
이 알고리즘의 시간복잡도는 입력할때 O(M)이고 나중에 누적합 배열을 사용할때 O(N)이다.
즉. O(M+N)이다.
'알고리즘 > Prefix Sum' 카테고리의 다른 글
| [코딩테스트] [17232] 생명 게임 & (이분탐색) [1920] 수 찾기 & [14425] 문자열 집합 (2) | 2024.12.16 |
|---|---|
| [코딩테스트] [11659] 구간 합 구하기 4 & [16713] Generic Queries (0) | 2024.12.12 |