Algorithm/Data Structure, Algorithm

투포인터 알고리즘, 슬라이딩 윈도우

SH_Roh 2021. 7. 25. 18:40
반응형

투포인터 알고리즘(Two Pointers Algorithm)

투포인터 알고리즘은 1차원 배열에서 각자 다른 원소를 가르키는 2개의 포인터를 조작해가면서 원하는 것을 얻는 형태이다. 알고리즘 문제를 풀다가 완전 탐색으로 해결하다가 시간 초과가 발생하는 경우에 사용할 수 있다.

 

문제는 N칸의 1차원 배열이 있을 때, 부분 배열 중 그 원소의 합이 M이 되는 경우의 수를 구하는 것이다. 이 문제에서 각 원소는 자연수이고 M 또한 자연수인데, 이 조건이 성립할 경우 사용할 수 있는 알고리즘은 다음과 같다.

  • 포인터 2개를 준비. 이를 left, right라고 함.
  • 처음에는 left = right = 0. 항상 left <= right 을 만족
  • 두 개의 포인터는 현재 부분 배열의 시작과 끝을 가리키는 역할을 함

left = right 일 경우. 즉, 크기가 0인 아무것도 포함하지 않는 부분 배열일 때, 아래의 과정을 left < N 인 동안 반복

  1. 현재 부분합이 M 이상이거나 이미 right = N이면 left++
  2. 그렇지 않다면 right++
  3. 현재 부분합이 M과 같다면 count++

쉽게 이해하자면, right와 left를 무조건 증가시키는 방향으로만 변화시켜가면서, 도중에 부분 배열의 합이 정확히 M이 되는 경우를 세는 것이다. 

 

아래는 예시 코드

<!DOCTYPE html>
<html>
  <head>
    <meta charset="UTF-8" />
    <title>출력결과</title>
  </head>
  <body>
    <script>
      function solution(m, arr) {
        let answer = (lt = sum = 0);
        for (let rt = 0; rt < arr.length; rt++) {
          sum += arr[rt];
          if (sum === m) answer++;
          while (sum > m) {
            sum -= arr[lt++];
            if (sum === m) answer++;
          }
        }
        return answer;
      }

      let a = [1, 3, 1, 2, 3];
      console.log(solution(5, a));
    </script>
  </body>
</html>

 

  • 추천 문제(백준)
    • 2003: 수들의 합
    • 1644: 소수의 연속합
    • 1806: 부분합
    • 2230: 수 고르기

 

슬라이딩 윈도우(Sliding Window)

그리고 이와 비슷한 슬라이딩 윈도우(Sliding Window) 유형도 존재한다. 이는 마치 창문을 한 쪽으로 밀면서 문제를 푸는 것과 유사해서 붙여진 이름인데, 이는 투 포인터처럼 구간을 훑으면서 지나간다는 공통점이 있으나 슬라이딩 윈도우는 어느 순간에도 그 구간의 넓이가 동일하다는 차이점이 있다. 

 

 

슬라이딩 윈도우 알고리즘은 배열이나 리스트의 요소의 일정 범위의 값을 비교할 때 사용하면 유용한 알고리즘이다. 예를 들어 정수로 이루어진 배열에서 길이가 3인 서브배열의 합계가 가장 큰 서브배열은 무엇인가? 같은 문제에서 사용될 수 있다. 

 

이는 단순하게 for 루프로 모든 배열 요소를 특정 길이만큼 순회하며 합계를 구해 최대 값을 구할 수도 있지만 더 효율적으로 코드를 작성하려면 슬라이딩 윈도우를 사용하는 것이 좋다.

 

 

우선 기존 단순한 방식에서 서브 배열의 요소를 순회하다 보면 중복되는 요소들이 존재한다. 위의 이미지 처럼 범위가 5인 서브배열을 탐색하는 경우, 0~4 범위의 서브 배열과 1~5 서브배열은 공통적으로 1~4 범위가 중복된다. 이 때, 중복되는 요소들을 재사용하는 방법이 슬라이딩 윈도우 알고리즘의 핵심이다.

 

 

ex) k=3인 경우

먼저 0~2 범위의 합을 sum과 answer에 저장을 한 후, sum에 arr의 k번째 요소에서 arr의 0번째 인덱스를 빼준 값을 더해주는 식으로 풀 수 있다.

(아래 코드는 자바스크립트로 짜 본 예시, 요즘 JS 공부를 열심히 하고 있기 때문에..!)

 

<!DOCTYPE html>
<html>
  <head>
    <meta charset="UTF-8" />
    <title>출력결과</title>
  </head>
  <body>
    <script>
      function solution(k, arr) {
        let answer,
          sum = 0;
        for (let i = 0; i < k; i++) sum += arr[i];
        answer = sum;
        for (let i = k; i < arr.length; i++) {
          sum += arr[i] - arr[i - k];
          answer = Math.max(answer, sum);
        }
        return answer;
      }

      let a = [12, 15, 11, 20, 25, 10, 20, 19, 13, 15];
      console.log(solution(3, a));
    </script>
  </body>
</html>
반응형