Two pointer

title: 2025-09-09 author: 강병호 date: 2025-09-09 (날짜) category: TIL/강병호/2025/09(파일 경로 : TIL/{이름}/{연}/{월}) layout: post (자유) —

투포인터 알고리즘

• 가변 길이 슬라이딩 윈도우 + 고정 길이 슬라이딩 윈도우
• 실제로 가변 길이 슬라이딩 윈도우의 의미로 자주 쓰임
• 1차원 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작하며 원하는 것을 얻는 기법

• ex. N칸의 1차원 배열이 있을 때, 부분 배열 중 원소 합이 M이 되는 경우의 수

  

  

  • 부분 배열의 시작과 끝을 가리키는 s, e 선언
  • s = e = 0 부터 시작, 항상 s <= e 여야 함Í

  • s가 가리키는 칸은 포함, e가 가리키는 칸은 미포함 [s, e)

    → s = e 일 경우, 크기가 0인 아무것도 포함하지 않는 부분 배열을 의미

  • s < N 동안 다음 과정 반복
    1. 현재 부분합이 M 이상이거나, 이미 e = N이면 s++
    2. 그렇지 않다면 e++
    3. 현재 부분합이 M 과 같으면 결과++

  → s, e를 증가시키는 방향으로만 변화시켜 [s, e) 부분 배열의 합이 M이 되는 횟수를 카운트 하는 방법

• 코드 (가장 안전한 방식)

    int res = 0; // 결과 카운트
    int sum = 0; // 누적합
      
    // end 포인터 'e'가 배열의 끝까지 이동하며 윈도우를 확장한다.
    int s = 0;   // 시작 포인터 (start)
    for (int e = 0; e < N; e++) { //확장
          
        sum += arr[e]; // 1. 윈도우에 새로운 원소(arr[e])를 추가한다.
      
        while (sum >= M) { // 2. 현재 합(sum)이 M 이상이면, M보다 작아질 때까지 윈도우를 축소
            if (sum == M) { // 만약 합이 정확히 M과 같다면 결과 카운트 증가
                res++;
            }
            // 3. 윈도우의 맨 앞 원소(arr[s])를 빼고, 시작 포인터를 한 칸 뒤로 옮긴다.
            sum -= arr[s++]; //s++
        }
    }
  

  • 시간복잡도? $O(N)$