[Panda] 2. 구간 합(Prefix Sum)과 투 포인터 알고리즘

알고리즘 판다 1,2주차 정리

 

구간 합 알고리즘

구간 합은 합 배열을 이용하여 시간 복잡도를 더 줄이기 위해 사용하는 특수한 목적의 알고리즘이다.

구간 합 알고리즘을 활용하려면 먼저 합 배열을 구해야한다.

 

합 배열 S 정의
S[i] = A[0] + A[1] + A[2] + ... + A[i-1] + A[i]

이 사진의 합 배열S를 살펴보면 해당 인덱스까지의 원래 배열A값들의 합을 저장하고 있다.

 

합 배열 S를 만드는 공식
S[i] = S[i-1] + A[i]

 

위 공식이 성립하는 이유를 위 사진의 예시로 생각해본다면 다음과 같이 합배열을 만들 수 있기 때문이다.

int[] A = {15, 13, 10, 7, 3, 12};

int[] S = new int[A.length];

S[0] = A[0];
for(int i = 1; i < S.length; i++) {
	S[i] = S[i-1] + A[i];
}

 

만약 중복계산을 제거하고 싶다면 이렇게도 생각해볼 수 있다.

int[] A = {15, 13, 10, 7, 3, 12};
int[] S = new int[A.length];

int sum = 0;
for(int i = 0; i < A.length; i++) {
    sum += A[i];
    S[i] = sum;
}

 

합 배열을 사용하여 구간 합을 구하는 공식
i에서 j까지 구간 합: S[j]  - S[i-1]

위 사진처럼 A[2]에서 A[5]까지의 구간 합을 구하고 싶다면 S[5] - S[1]을 하면 된다.

 

 

투 포인터 알고리즘

투 포인터 기법이란, 두 개의 포인터를 만들어서 각각이 가리키는 원소에 의미를 부여하여 요구하는 문제를 해결하는 알고리즘이다.

리스트에 순차적으로 접근해야할 때 두 개의 점의 위치를 기록하면서 처리해야한다는 것을 기억하면 좋겠다.

주로 정렬된 리스트에서 부분합이나 두 요소의 합을 구하는 등의 문제를 효율적으로 해결하는데 사용된다.

 

대표적인 예시에는 3가지가 있다.

• 포인터 2개가 같은 방향으로 진행해 나아가는 것
• 포인터 2개가 양끝에서 반대로 진행하는 것
• 포인터 하나는 한쪽 방향으로만 진행하고 다른 포인터는 양쪽으로 이동하는 것

일반적으로 두 가지 방식으로 구현된다.

1. 고정된 투 포인터: 리스트의 양 끝에서 시작하여 포인터를 움직이는 방식
   • 한 포인터는 리스트의 시작을, 다른 포인터는 끝을 가르키고 두 포인터가 움직이면서 특정 조건에 맞게 계산을 수행항거나 원하는 결과를 도출
2. 슬라이딩 윈도우: 리스트나 배열에서 고정된 길이의 부분 리스트를 지정하여  그 부분 리스트 내에서 원하는 조건을 만족하는 경우를 차는 방식
   • 부분 리스트의 길이를 조정하며 포인터를 이동시켜가며 문제를 해