ABOUT ME

    -

    Today
    -
    Yesterday
    -
    Total
    -
    • [코테] 투포인터
      카테고리 없음 2025. 11. 22. 20:54

       

      핵심 원리:

      • right는 0 → N까지 한 번만 증가
      • left는 필요할 때만 증가 (역방향 없음)
        → 전체 O(N)

       

       

      💎 투 포인터 공통 템플릿 (슬라이딩 윈도우 기본형)

       
      int left = 0;
      long sum = 0;  // 누적 상태 (합이든, 카운트든 조건 체크용)

      for (int right = 0; right < N; right++) {

          // 1) right 확장
          sum += A[right];

          // 2) 조건을 위반하면 left 조정 (왼쪽을 줄여서 다시 만족시키기)
          while (sum > K) {  // 문제에 따라 조건 변경
              sum -= A[left];
              left++;
          }

          // 3) 여기 왔을 때는 sum이 조건을 만족
          //    → 문제 유형별로 다른 처리
          //    예: count += (right - left + 1);
          //    예: ans = Math.min(ans, right-left+1);
          //    예: ans = Math.max(ans, right-left+1);
      }

       

       

      🚀 1. 투 포인터(Two Pointers)란?

      두 개의 인덱스(왼쪽, 오른쪽)를 움직이면서
      O(N²) 문제를 O(N) 또는 O(N log N)으로 줄이는 기법

      즉,

      • i = 시작 지점(left pointer)
      • j = 끝 지점(right pointer)

      이 두 변수를 조절하면서
      모든 (i,j) 쌍을 “정확히 한 번씩” 확인하는 구조를 만드는 알고리즘이야.

      🚨 2. 왜 필요한가?

      예를 들어, 다음 문제가 있다고 해봐.

      “연속 부분 배열 중 합이 K 이하인 모든 구간의 수 구하기”

      이걸 단순히 이중 for문으로 풀면:

       
      for (i = 0..N) for (j = i..N)

      → O(N²)
      → N = 200,000이면 절대 못 풀어.

      그래서 나온 아이디어가 투 포인터야.

      🔥 3. 투 포인터의 핵심 아이디어 3줄 요약

      ✔ (1) 오른쪽 포인터를 0부터 N까지 한 번만 증가시킨다

      → “확장”

      ✔ (2) 조건을 만족하지 않으면 왼쪽 포인터를 증가시켜 조절한다

      → “축소”

      ✔ (3) 두 포인터 각각 최대 N번씩만 이동

      → 전체 시간복잡도 O(N)

      즉,
      중첩 for문처럼 모든 조합을 다 도는 게 아니라,
      포인터가 뒤로만 가므로 절대 뒤로 가지 않음 (no backtracking).

       

      🌈 4. 투 포인터가 가능한 문제 조건

      투 포인터는 이 조건이 있을 때만 가능해:

      ✔ 배열 원소가 “음이 아닌 경우”

      (≥ 0)

      왜?

      • 합이 커지면 right를 줄여도 다시 작아지지 않음
      • left를 당기면 합이 반드시 감소함
      • 단조(monotonic)한 특성이 필요

      즉,
      왼쪽으로 이동하면 sum 감소,
      오른쪽으로 이동하면 sum 증가.

      그래서 left/right 둘 다 뒤로 돌아갈 필요가 없음.

      🧠 5. 한 번에 이해하는 예시

      배열:

       
      A = [10, 1, 6, 5, 2, 1] K = 15

      우리는:

      합이 K 이하인 구간 (i,j)의 개수를 구하고 싶다.

      👉 투 포인터 흐름 (직관적 설명)

      step1: right=0

      sum=10 → OK
      구간 개수 += (0 - 0 + 1) = 1

      step2: right=1

      sum = 10 + 1 = 11 → OK
      구간 2개:

      • (0,1)
      • (1,1)
        count += 2

      step3: right=2

      sum = 11 + 6 = 17 → K 초과
      left 증가 → left=1
      sum = 17 - 10 = 7 → OK
      구간 2개:

      • (1,2)
      • (2,2)
        count += 2

      step4: right=3

      sum = 7 + 5 = 12 OK

      구간 3개

      • (1,3), (2,3), (3,3)

      count += 3

      이런 식으로 left/right 둘 다 앞으로만 움직이면서 모든 구간 세기 가능

       

      • [0 ~ right+1]은 당연히 예전에 K를 넘던 데다가 더 큰 수를 더했으니까,
        또 K 넘을 가능성이 더 큼
      • 그러니까 다시 left=0으로 돌아가서 볼 필요가 없음

      🧩 6. 투 포인터 표준 코드 (암기용 sum<=K)

       
      long count = 0;
      int left = 0;
      long sum = 0;

      for (int right = 0; right < N; right++) {
          sum += A[right];

          // 조건 위반 → left 증가
          while (sum > K && left <= right) {
              sum -= A[left];
              left++;
          }

          // 여기서 sum <= K를 만족
          // right를 끝으로 하는 유효 구간 수:
          count += (right - left + 1);
      }

      ✔ 복잡도

      • right: 0→N 까지 N번
      • left: 한 번 증가하면 다시 줄지 않음 → 최대 N번
      • 따라서 O(N)

       

      🎯 7. 투 포인터가 쓰이는 문제 패턴

      📌 (1) 합 조건을 만족하는 구간 찾기

      • 부분합 ≤ K
      • 부분합 = K
      • 최소 길이
      • 최대 길이

      📌 (2) 길이가 최소/최대인 구간 찾기

      📌 (3) 두 포인터 정렬 배열에서 값 찾기

      • A[left] + A[right] == target
      • 삼각형 조건
      • 3sum / 4sum

      📌 (4) 문자열에서 길이 가지는 윈도우

      • "슬라이딩 윈도우" 문제들이 사실상 투 포인터 변형

      💎 투 포인터 공통 템플릿 (슬라이딩 윈도우 기본형)

       
      int left = 0;
      long sum = 0;  // 누적 상태 (합이든, 카운트든 조건 체크용)

      for (int right = 0; right < N; right++) {

          // 1) right 확장
          sum += A[right];

          // 2) 조건을 위반하면 left 조정 (왼쪽을 줄여서 다시 만족시키기)
          while (sum > K) {  // 문제에 따라 조건 변경
              sum -= A[left];
              left++;
          }

          // 3) 여기 왔을 때는 sum이 조건을 만족
          //    → 문제 유형별로 다른 처리
          //    예: count += (right - left + 1);
          //    예: ans = Math.min(ans, right-left+1);
          //    예: ans = Math.max(ans, right-left+1);
      }

       

      핵심 원리:

      • right는 0 → N까지 한 번만 증가
      • left는 필요할 때만 증가 (역방향 없음)
        → 전체 O(N)

      🔥 단계별 설명

      1) right 확장 (윈도우 키우기)

       
      sum += A[right];

      지금 보고 있는 요소를 윈도우에 포함함.

      2) 조건 위반 시 left를 이동 (윈도우 줄이기)

       
      while (sum > K) { sum -= A[left]; left++; }

      문제 유형에 따라 조건은 달라짐:

      • sum > K
      • 길이가 초과됨
      • 포함해야 할 문자가 없음
      • distinct 개수가 많음
      • 특정 문자의 빈도가 넘침

      등등.

      3) 조건을 만족하는 상태에서 문제별 처리 로직 적용

      • 모든 구간 개수 세기
        → count += (right-left+1);

      -최소 길이
      → minLen = Math.min(minLen, right-left+1);

      • 최대 길이
        → maxLen = Math.max(maxLen, right-left+1);
      • 특정 문자 개수 유지
        → if (sum == K) count++;
      • 필요한 문자 모두 포함됨
        → 정답 갱신, left를 당겨 최소화 시도

      🎯 이 템플릿에서 바뀌는 부분은 딱 2곳

      ① 조건 위반 기준

      (ex: sum > K, 길이 초과, distinct > 2 등)

      ② 조건 만족 상태에서 처리하는 로직

      (ex: count += …, minLen 갱신, maxLen 갱신)

      둘만 바뀌면 모든 투포인터/슬라이딩 윈도우 문제를 해결할 수 있다.

      📌 문제 유형별 템플릿 적용 예시 요약

      ① 부분합 ≤ K인 모든 구간 개수

       
      while (sum > K) sum -= A[left++]; count += (right - left + 1);

      ② sum ≥ K인 “최소 길이” 구하기

       
      while (sum >= K) { minLen = Math.min(minLen, right-left+1); sum -= A[left++]; }

      ③ sum ≤ K인 “최대 길이” 구하기

       
      while (sum > K) sum -= A[left++]; maxLen = Math.max(maxLen, right-left+1);

      ④ 문자열에서 조건 만족하는 최소 윈도우

       
      // 오른쪽으로 확장 (문자 카운트 늘리고 조건 달성) while (조건 달성됨) { minLen = Math.min(minLen, right-left+1); // left 줄이기 시도 left++; }
    Designed by Tistory.

    티스토리툴바