투포인터 & 슬라이딩 윈도우

1. Two Pointers Algorithm

투 포인터 알고리즘이란 N개가 있는 1차원 배열에서 부분 배열 중 합이 M이 되는 지점을 구하는것이다.
사용 조건으로는 각 원소는 자연수이고 M 또한 자연수여야만 사용 할 수 있다. 알고리즘의 작동 방식은 우선 두 개의 포인터(start,end)를 지정한다. 이 변수는 각 각 부분배열의 첫 부분과 끝 부분을 의미한다.

Start = 0, End = 1 이여야하며 Start <= N-2, End <= N -1 까지 진행한다.

그 이후 sum[N] 배열을 준비하여 1차원 배열에 1 .... N번째까지의 합을 구한다. 두 포인터가 움직이는 규칙은 간단하다.

• sum[end] - sum[start] >= M 이라면 start를 한 칸 뒤로 옮긴다.
• 반대의 경우 end를 한 칸 뒤로 옮긴다.

따라서 start와 end를 옮겨가며 모든 부분 배열을 훑으면 되는것이다.

정말 모든 부분배열을 훑고 가는지 확인하기 위해 다음과 같은 상황을 예상 할 수 있다.

검은색 네모칸이 현재 부분배열의 Start,End라 하고 합이 m이 되는 부분배열을 tStart,tEnd라 해보자.

저 배열을 지나치기 위해선 2가지 조건이 있는데 Start가 tStart를 지나치거나 End가 tEnd를 지나쳐야 된다. Start = tStart일때 지나가려면 Start 값이 증가를 해야하는데, 위에 말했던 조건대로 M >= 을 만족해야 한다. 하지만 End < tEnd 상태에서는 M의 값을 만족할 수 가 없다. End값은 1씩 증가하고 End값이 tEnd에 도착하기 전에 Start 값은 절대 움직일수 없다. 반대의 경우도 똑같다.

1-1. 구현

SUM[N] = SUM[1...N까지의 합]

start = 0
end = 1

while start < N:
	tempSUM = SUM[end] - SUM[start]
    
    	if tempSUM > M:
        	start += 1
            	해당 조건의 인덱스의 갯수 = end - start + 1
        else:
        	if end != N:
            		end += 1
             	else:
                	start += 1

2. Sliding Window

슬라이딩 윈도우는 단순하게 배열 A에 A[1]...A[N]의 부분배열의 갯수인 K가 최대 부분배열의 갯수인 T보다 클 때(K >= T) 공통부분의 배열만 가지고 가면서 앞쪽 배열을 빼는 것이다. 즉 슬라이드 윈도우라는 임의의 배열을 가지고 오른쪽으로 옮겨가는 것이다.

for end in range(N):
	tempSum += A[end]
    
    	if end >= ( T - 1 ):
        	resultSum = max(tempSum,resultSum)
            	tempSum -= A[start]
               	start += 1