이 문제에서는 0으로 초기화된 N개의 원소를 가진 배열 arr[]가 주어집니다. 우리가 작성해야 할 프로그램은 m번의 범위 증가(range increment) 연산을 모두 수행한 뒤, 배열에서 최댓값을 찾아 출력하는 것입니다.
문제 설명
배열에는 다음과 같은 형태의 범위 증가 연산이 m번 적용됩니다.
update[L, R, K] = 인덱스 L부터 R까지의 모든 원소에 값 K를 더합니다.
m번의 연산이 모두 끝난 후, 배열에서 가장 큰 값을 가지는 원소를 찾아야 합니다.
예시를 통해 문제를 살펴보겠습니다.
입력
N = 6, m = 4
Update[][] = {{1, 4, 12}, {0, 3, 5}, {1, 5, 7}, {3, 5, 10}}
출력
34
설명
arr[] = {0, 0, 0, 0, 0, 0}
Update 1 {1, 4, 12} : arr[] = {0, 12, 12, 12, 12, 0}
Update 2 {0, 3, 5} : arr[] = {5, 17, 17, 17, 12, 0}
Update 3 {1, 5, 7} : arr[] = {5, 24, 24, 24, 19, 7}
Update 4 {3, 5, 10} : arr[] = {5, 24, 24, 34, 29, 17}
모든 연산이 끝난 배열에서 가장 큰 값은 34이므로 정답은 34가 됩니다.
접근 방법 1: 단순 갱신 방식
가장 직관적인 해결 방법은 각 연산이 주어질 때마다 해당 범위의 원소 값을 실제로 갱신하고, 모든 연산이 완료된 후 배열을 한 번 순회하며 최댓값을 찾는 것입니다.
예제 코드
#include<iostream>
using namespace std;
int findmax(int arr[], int N){
int maxVal = 0;
for(int i = 0; i < N; i++){
if(maxVal < arr[i]){
maxVal = arr[i];
}
}
return maxVal;
}
void updateVal(int arr[], int L, int R, int K){
for(int i = L; i <= R; i++){
arr[i] += K;
}
}
int main(){
int N = 6;
int arr[N] = {0};
int M = 4;
int rangeIncOperation[M][3] = {{1, 4, 12}, {0, 3, 5}, {1, 5, 7}, {3, 5, 10}};
for(int i = 0; i < M; i++){
updateVal(arr, rangeIncOperation[i][0], rangeIncOperation[i][1], rangeIncOperation[i][2]);
}
cout<<"4번의 범위 증가 연산 후 배열의 최댓값은 "<<findmax(arr, N)<<"입니다";
return 0;
}
출력
4번의 범위 증가 연산 후 배열의 최댓값은 34입니다
이 방법은 구현이 간단하고 이해하기 쉽다는 장점이 있지만, 쿼리 하나하나마다 범위 전체를 순회해야 하므로 전체 시간 복잡도가 O(m × N)이 됩니다. 배열의 크기와 연산 횟수가 커지면 성능이 급격히 저하될 수 있습니다.
접근 방법 2: 차이 배열(Difference Array) 활용
더 효율적인 방법은 각 범위 증가 연산에 대해 인덱스 L에는 K를 더하고, 인덱스 R+1에서는 K를 빼는 것입니다. 이렇게 하면 각 연산을 상수 시간 O(1)에 처리할 수 있습니다.
모든 연산이 끝난 뒤 배열을 처음부터 순회하면서 누적합(prefix sum)을 계산하면, 각 위치의 실제 값이 만들어집니다. 누적합 과정에서 등장하는 값 중 가장 큰 것이 곧 우리가 찾는 최댓값입니다.
이 방식은 각 연산 처리에 O(1), 마지막 순회에 O(N)이 걸리므로 전체 시간 복잡도가 O(N + m)으로 크게 개선됩니다.
예제 코드
#include<iostream>
using namespace std;
int findmax(int arr[], int N){
int maxVal = 0;
int sum = 0;
for(int i = 0; i < N; i++){
sum += arr[i];
if(sum > maxVal){
maxVal = sum;
}
}
return maxVal;
}
void updateVal(int arr[], int L, int R, int K){
arr[L] += K;
arr[R + 1] -= K;
}
int main(){
int N = 6;
int arr[N + 1] = {0};
int M = 4;
int rangeIncOperation[M][3] = {{1, 4, 12}, {0, 3, 5}, {1, 5, 7}, {3, 5, 10}};
for(int i = 0; i < M; i++){
updateVal(arr, rangeIncOperation[i][0], rangeIncOperation[i][1], rangeIncOperation[i][2]);
}
cout<<"4번의 범위 증가 연산 후 배열의 최댓값은 "<<findmax(arr, N)<<"입니다";
return 0;
}
출력
4번의 범위 증가 연산 후 배열의 최댓값은 34입니다
주의할 점은 R+1 위치에 값을 빼기 때문에 배열을 선언할 때 크기를 N+1 이상으로 확보해야 인덱스 초과 오류를 피할 수 있다는 것입니다.
두 방법 비교
단순 갱신 방식: 로직이 단순하지만 매 연산마다 범위를 순회하므로 시간 복잡도는 O(m × N)입니다.
차이 배열 방식: 각 연산을 상수 시간에 처리하고 마지막에 한 번만 순회하므로 시간 복잡도는 O(N + m)으로, 입력 크기가 클수록 월등히 빠른 성능을 보여줍니다.
따라서 범위 갱신 연산이 여러 번 반복되는 상황이라면 차이 배열과 누적합을 활용하는 두 번째 접근 방법이 훨씬 효율적인 선택입니다.