[Algorithm] 투 포인터 / 슬라이딩 윈도우

투 포인터

1차원 배열에서 두개의 포인터를 조작하여 원하는 값을 얻는 것

투 포인터?

N개의 수열에서 특정 구간의 합을 구하고 싶다 이럴 떄 모든 경우의 수를 다 구해 찾을 수 잇겠지만 경우의 수가 O(N^2)이라 시간초과가 나는 경우가 있을 것이다. 이럴경우 투포인터를 사용하면 O(N)으로 답을 구할 수 있다.

투포인터 기념 개념

• 양 끝에 두개의 포인터를 사용하는 기법(start,end)
• 양 끝에서 조건에 만족할 떄 까지 가운데로 이동하며 진행
• 정렬이 되어있는 상태에서 사용이 가능함.
  

투포인터 문제 예시

배열의 양 끝에 두개의 포인터를 만들어준다.
start ,end로 보통 만든다. 그 후 target(원하는 값)을 찾는데 target 보다 작으면 왼쪽(start) 값을 오른쪽으로 이동시켜 숫자를 크게 만들어 준다 그 후 다시 비교하여 작다면 다시 왼쪽(start)를 오른쪽으로 이동 시키고 크다면 오른쪽(end)를 왼쪽으로 이동시켜 원하는 값을 찾으면 된다.

function solution() {
  const arr = [1,3,2,2,5,7,2,6];
  const M = 9;
  let ans = 0;
  let start = 0, end = 0, sum = arr[0];
  
  while(arr[start] && arr[end]){
    // M 과 같은 경우
    if(sum === M){
      ans++;
      end++;
      sum += arr[end];
    } 
    // M보다 큰 경우
    else if(sum > M){
      sum -= arr[start];
      start++;
    } 
    // M보다 작은 경우
    else{
      end++;
      sum += arr[end];
    }
  }
  
  return ans;
}

슬라이딩 윈도우

• 배열 혹은 리스트 위에 고정된 크기를 부여 하고 이동하면서 원소를 비교하는 것
• 이동 시 새로운 원소를 받아오는 대신 원래의 원소를 제거한다.(고정된 크기 유지하기위해)
• 계산을 반복하는 것이 아닌 변경된 요소만 계싼해 복잡도가 낮다.
• O(N)의 시간복잡도를 가짐
• 연속적인 구간에서 최대/최소 합을 구하는 문제에서 특정 원소를 찾을 때 유용함.

슬라이딩 윈도우 사용 예시

주어진 배열에서 길이가 K인 연속된 구간의 합이 가장 큰 경우와 가장 작은 경우를 구하시오

function maxSumArr(arr, size) {
    let maxSum = 0;
    let tempSum = 0;
  
    if(arr.length < size) return null;
  
    for(let i = 0; i < size; i++) {
       tempSum += arr[i];
    }
  
    tempSum = maxSum;
  
    for(let i = size; i < arr.length; i++) {
       tempSum = tempSum - arr[i - size] + arr[i];
       maxSum = Math.max(tempSum, maxSum);
    }      
    
	return maxSum;
}

크기가 정해지면 처음 크기의 개수만큼 하나의 값을 만들어 준다 그 후 하나의 원소를 추가하며 하나의 원소를 빼주며 계속 값을 비교하며 가장큰값 혹은 가장 작은값을 찾을 수 있다.