구간 합 (Prefix sum)
- 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘
- 코딩 테스트에서 사용 빈도가 높으니 잘 알아둘 것!!
// 배열 A. 합 배열 S
S[i] = A[0] + A[1] + ... + A[i-1] + A[i]; // A[0]부터 A[i]까지의 합
// 합 배열 S 만드는 공식
S[i] = S[i-1] + A[i];
// 구간 합을 구하는 공식
S[j] - S[i-1]; // i에서 j까지 구간 합
// 2차원일 경우 S[i][j]의 값을 채우는 구간 합 공ㅇ식
S[i][j] = S[i][j-1] + S[i-1][j] - S[i-1][j-1] + A[i][j];
투 포인터 (Two Pointers)
- 2개의 포인터로 알고리즘의 시간복잡도를 최적화
- 연속되고 길이가 가변적인 "부분 연속 " 리스트에 사용
- 시간 복잡도 O(N)으로 처리 가능
- 유형
- 2개의 포인터 변수 시작점이 배열의 시작점인 경우
- 정렬된 배열 안에서 2개의 포인터 변수가 각각 시작점과 끝점에 위치한 경우
- 부분배열의 합이 Target값보다 크거나 같을 경우 Start ++
- 부분배열의 합이 Target값보다 작을 경우 End ++
// 투 포인터 이동 원칙
sum > N : sum = sum - start; start++;
sum < N : end++; sum = sum + end;
sum == N : end++; sum = ssum + end; count++
슬라이딩 윈도우 (Sliding Window)
- 연속되고 길이가 고정적인 "부분 연속 " 리스트에 사용
- 시간 복잡도 O(N)으로 처리 가능
투 포인터와 슬라이딩 윈도우
- 공통점
- 1차원 배열을 부분 배열을 활용하여 시간복잡도를 O(N)으로 줄일 수 있음
- 차이점
- 투 포인터는 길이가 가변적인 반면, 슬라이딩 윈도우는 길이가 고정
- 투 포인터는 2개의 포인터 변수가 필요한 반면, 슬라이딩 윈도우는 고정길이이기 때문에 1개의 포인터 변수만 있으면 됨
