[JS] 투 포인터, 구간 합

 이 포스팅은 동빈나님의 코딩테스트 & 알고리즘 대회 핵심 노트 - 투 포인터, 구간 합이라는 강의를 보고 쓴 것이다.

 

배열의 특정 연속된 구간을 처리하기 원하는 경우

•   문제에서 연속된 데이터 구간을 처리하기를 원한다면?
•   다양한 접근 방법을 떠올려 보는 것이 중요!
•   자주 사용되는 기법들로는 어떤 것들이 있을까?

 

 이 강의에서 나오는 대단한 풀이를 보고 그냥 지나칠 수가 없었다. 세상엔 정말 날고 기는 사람들이 많다는 것을 다시 한 번 느낀다.

분명히 프로그래머스라는 사이트에서 이러한 유형의 문제를 풀때 이중 반복문을 남발했던 것 같은데... 요새 자료구조를 복습하는 입장에서 볼 때, 과거의 나는 효율성이라고는 1도 고민하지 않고 문제를 풀었던 것 같다.

 

 

 이 강의는 배열의 특정 연속된 구간을 처리하는 것을 목적으로 하는 문제를 만났을 때, 가장 처음으로 떠올려보고 접근해보기에 좋은 기법들을 알려주는 강의다. 문제 예시는 총 2개가 나왔으며, 첫 번째 예시는 투 포인터 기법에 관한 것이고, 두 번째 예시는 구간 합이라는 기법에 관한 것이다.

 

 

 이제 영상에 나온 두 문제들을 한번 포스팅해보도록 하겠다.

 

첫 번째 문제

 부분 연속 수열에 대한 합을 구하는 문제이다. 자연수로 구성된 배열에서 특정한 범위의 합을 구하려면 어떻게 해야될까?

문제의 조건은 다음과 같다.

 

• 아래와 같이 자연수로 구성된 수열이 있다.

• 합이 5인 부분 연속 수열의 개수를 구해라.

 

 

 위 그림과 같이 연속된 배열의 합이 5가되는 것들을 찾으면 된다. 중요한 것은 연속적이어야 한다는 점이다.

 이중 반복문을 이용하면 쉽게 풀 수는 있는 문제지만, 이는 O(N²)의 시간복잡도가 되버려서 효율성에 문제가 있다.

 

 그렇다면 이 문제를 효율적으로 풀려면 어떻게 해야할까?

 강의에서는 투 포인터 기법을 활용해서 풀 것을 권장하고 있다. 여기서 투 포인터 기법이란, 리스트에 순차적으로 접근해야 할 때 두 개의 점을 이용해 위치를 기록하면서 처리하는 기법을 말한다.

 

이를 활용한 설명은 다음과 같다.

 

 먼저, 시작점과 끝 점이 첫 번째 원소의 인덱스 0을 가리키도록 한다.

 

  

 그 다음으로 현재 부분의 합이 5와 같다면 개수(정답 수)를 카운트하고, 합이 5보다 작거나 같다면 End를 1중가시키고, 합이 5보다 크다면 Start를 1 증가시킨다. 따라서 1은 5보다 작기 때문에 End를 1 증가시킨다. 

 

 

 그러면 Start는 인덱스 0을 가리키고 있고, End는 인덱스 1을 가리키고 있는데, Start인덱스에서 End인덱스 까지의 합은 3이다.

하지만, 3은 5보다 여전히 작기 때문에 End를 1증가시켜야 한다.

 

 

 그러면 Start는 인덱스 0을 가리키고 있고, End는 인덱스 2를 가리키고 있다. Start에서 End까지의 합은 6이다.

6은 5보다 값이 크므로, Start를 1 증가시켜야 한다.

 

 

 그 후에 Start는 인덱스 1, End는 인덱스 2이 된다. 두 범위 사이의 합은 5가 되므로 답 개수를 카운트 시키고 End를 1 증가시킨다.

 

 

 그 후에 Start와 End사이의 범위 값은 7이 된다. 7은 5보다 크기 때문에 Start를 1 증가시키면 된다. 이런 과정을 반복하면 정답을 찾아낼 수 있을 것이다.

 

 이 알고리즘을 코드로 짜면 다음과 같다. 

const arr = [1, 2, 3, 2, 5];
let answerNum = 0;
let start = 0;
let end = 0;
let loopCount = 0;
let result = 0;

while(arr[start] !== undefined){
  while(result < 5 && end < arr.length){
    result += arr[end];
    end++;
  }
  if(result === 5)
    answerNum++;
  result -= arr[start];
  start++;
  loopCount++;
}

console.log("정답 개수:", answerNum); // 정답개수: 3
console.log("연산 횟수:", loopCount); // 연산횟수: 5

 

두 번째 문제

• N개의 정수로 구성된 수열이 있다.

• M개의 쿼리 정보가 주어진다.

• 각 쿼리는 L과 R로 구성된다.

• [L, R] 구간에 해당하는 데이터들의 합을 모두 구하라.

 

   

 L이 1이고, R이 3이면 10 + 20 + 30이 되고, L이 2이고 R이 4일 경우 20 + 30 + 40을 하면 된다.

 

 풀이는 다음과 같다.

 

 1. 앞에서부터 누적 합을 구해준다.

 

 

 2. 매 M개의 쿼리 정보를 확인할 때, 구간 합은 P[R] - P[L-1]이다.

• 1) R = 3, L=1 -> P[3] - P[1-1] = 60

• 2) R = 3, L=3 -> P[3] - P[3-1] = 60 - 30 = 3

•  

•  

• M) R = 2, L = 1 -> P[2] - P[1-1] = 30

 프로그래밍은 다음과 같다.

const arr = [10, 20, 30, 40, 50];
const acc = [];
const m = [{'L': 2, 'R': 3}, {'L': 1, 'R': 4}];
const answer = [];
let result = 0;
let accCount = 0;

for(let i=0; i<arr.length; i++){
  acc.push(result);
  result+=arr[i];
  accCount++;
}

for(let i=0; i<m.length; i++){
  answer.push(acc[m[i].R] - acc[m[i].L-1]);
  accCount++;
}

console.log(answer);
console.log("연산횟수:", accCount); //연산횟수 7