누적 합(sum)과 구간 합(Prefix sum)
누적 합
누적 합은 처음부터 정해진 구간까지 더한 값을 의미하며 누적 합을 이용하여 합 배열을 생성할 수 있다.
합 배열은 주어진 배열에서 0부터 특정 인덱스까지의 데이터가 더해진 값(누적 합)이 배열에 저장된 형태이다.
1
2
배열 : [1,2,3,4,5,6,7]
합 배열 : [1,3,6,10,15,21,28]
구간 합
구간 합은 시간 복잡도를 줄이기 위해 합 배열을 이용하여 주어진 배열을 전처리하는 과정이다.
합 배열의 값을 이용하여 아래의 식으로 특정 구간의 값을 구할 수 있다.
1
2
3
4
5
int[] numbers = {1,2,3,4,5,6,7};
int[] sumArray = {0,1,3,6,10,15,21,28};
// 인덱스 i부터 j까지의 구간 합
int prefixSum = sumArray[j] - sumArray[i - 1];
이 때 arrayIndexOutOfBound가 발생하지 않도록 0번 인덱스의 값을 0으로 두고 주어진 배열보다 인덱스를 하나씩 증가시켜줘야 한다.
구간 합을 구할 때 배열의 첫 번째 원소가 포함된 경우의 구간 합을 구하게 된다면
sumArray[i - 1]에서 인덱스가 -1이 될 수 있으므로 구간 합 배열의 첫번째 원소를 0으로 설정하는 것이 좋다.
2차원 배열에서도 마찬가지로 합 배열을 이용하여 구간 합을 구할 수 있다.
1
2
3
4
5
6
7
int[][] numbers= {{1,2,3,4},{2,3,4,5},{3,4,5,6},{4,5,6,7}}
// 2차원 배열의 합 배열 구하기 : s(x,y) = s(x,y-1) + s(x-1,y) - s(x-1,y-1) + a(x,y)
int[][] sumArray = {{1,3,6,10},{3,8,15,24},{6,15,27,42},{10,24,42,64}}
// (x1,y1)부터 (x2,y2)까지의 구간 합
int result = sumArray[x2][y2] - sumArray[x2][y1 - 1] - sumArray[x1 - 1][y2] + sumArray[x1 - 1][y1 - 1];
마찬가지로 arrayIndexOutOfBound가 발생하지 않도록 행과 열의 0번 인덱스의 값을 0으로 두고 주어진 배열보다 인덱스를 하나씩 증가시켜줘야 한다.
투 포인터(Two pointer)
투 포인터
투 포인터는 배열을 순회하는 횟수를 줄이기 위해 변수를 이용하여 배열의 인덱스에 대한 2개의 포인터를 구현하고 수를 비교하거나 연산하여 시간 복잡도를 최적화하는 방법이다.
주로 정렬과 함께 사용되며 시간 복잡도에 따라 투 포인터를 사용하기 전에 정렬을 할지 여부를 결정해야 한다.
경우에 따라 두 개의 포인터가 배열을 순회하기 시작하는 위치를 결정하면 된다.
두 포인터가 같은 위치에서 순회를 시작하는 경우
1 2 3 4 5 6 7 8 9 10 11 12
int[] arr = {1,2,3,4,5,6} int sp = 0; // startPointer int ep = 0; // endPointer while(ep < arr.length) { if(조건1) { ep++; } else { sp++; } }
주로 배열의 연속된 원소의 합을 구하는 과정에서 사용된다.
두 포인터가 배열의 양쪽 끝에서 순회를 시작하는 경우
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
int[] arr = {1,2,3,4,5,6} int sp = 0; // startPointer int ep = arr.length - 1; // endPointer while(sp < ep){ if(조건1) { ep++; // 문제 조건에 따라 결과 중복을 방지하기 위해 적절하게 break를 사용 break; } else if { ep++; } else { sp++; } }
주로 순서와 상관없이 배열의 두 원소를 비교하거나 연산하는 과정에서 사용된다.
해결해야할 문제에 따라 두 포인터의 시작 위치와 이동 조건을 알맞게 설정하는 것이 중요하다.
투 포인터를 사용하기 전에 시간 복잡도를 고려하여 O(nlogn)의 정렬 알고리즘을 사용해도 될 것 같다면
java.util.Arrays의Arrays.sort(arr)을 사용하여 정렬
슬라이딩 윈도우(Sliding window)
슬라이딩 윈도우는 투 포인터의 특수한 형태로 두 포인터가 일정한 간격을 유지하며 배열을 순회하는 방식으로 동작한다.
주어진 크기의 슬라이딩 윈도우에 들어갈 데이터를 초기화해주고 변경되는 값에 대해서만 처리를 하면 되기 때문에 배열을 순회하는 데에 필요한 시간 복잡도를 감소시킬 수 있다.
주로 배열을 고정된 크기만큼 부분적으로 반복 순회해야할 경우에 사용한다.
슬라이딩 윈도우를 구현하기 위해 먼저 슬라이딩 윈도우의 크기만큼 슬라이딩 윈도우가 가지고 있을 값을 초기화 해주어야 한다.
또한 초기화한 결과가 원하는 결과와 일치하는지 검증하는 과정도 한 번 거친 뒤에 슬라이딩 윈도우의 이동을 진행해야한다.
슬라이딩 윈도우를 먼저 초기화 하고 검증한 뒤에 슬라이딩 윈도우를 이동시키며 배열을 순회하면 된다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
// 연달아 0이 3개가 나오는 경우 카운트
int[] arr = {0,0,1,0,0,0,0,1,1,0,0,1,1,1,0,0,0,0,1,1};
int count = 0;
int windowSum = 0;
for (int i = 0; i < 3; i++) {
windowSum += arr[i];
}
// 초기화 결과에 대해 조건에 부합하는지 검증한다.
if(windowSum == 0){
count++;
}
// 슬라이딩 윈도우의 end pointer와 start pointer는 초기보다 1만큼 높아야 한다.
for (int ep = 3; ep < arr.length; ep++) {
int sp = ep - k;
// 슬라이딩 윈도우의 이동에 따라 추가되는 값과 나가게 되는 값에 대한 연산을 진행한다.
windowSum += arr[ep];
windowSum -= arr[sp];
if(windowSum == 0){
count++;
}
}