수달씨의 개발공간

✅ 개념 정의

Two Pointers(투 포인터) 알고리즘은 두 개의 인덱스(포인터)를 이용해 배열이나 문자열을 효율적으로 탐색하는 알고리즘 기법입니다. 보통 O(N) 시간에 문제를 해결할 수 있어, 정렬된 데이터나 연속된 구간을 처리할 때 유용합니다.

✅ 언제 사용하는가?

상황 설명

✅ 패턴 1: 양쪽에서 좁혀오는 방식

🔹 구조

let left = 0;
let right = arr.length - 1;

while (left < right) {
  if (arr[left] + arr[right] === target) {
    return [left, right];
  } else if (arr[left] + arr[right] < target) {
    left++;
  } else {
    right--;
  }
}

🔹 사용 예시: 정렬된 배열에서 합이 target인 쌍 찾기

const arr = [1, 2, 3, 4, 6];
const target = 6;
// 출력: [1, 3] (2 + 4)

• 포인터를 왼쪽/오른쪽에서 이동하며 값을 비교
• 정렬된 배열일 때 효율적으로 동작함

✅ 패턴 2: 앞뒤 포인터로 구간 조절 (슬라이딩 윈도우)

🔹 구조

let left = 0;
let sum = 0;

for (let right = 0; right < arr.length; right++) {
  sum += arr[right];

  while (sum > target) {
    sum -= arr[left++];
  }

  if (sum === target) {
    console.log(`Found from ${left} to ${right}`);
  }
}

🔹 사용 예시: 부분 배열의 합이 target과 같은 구간 찾기

const arr = [1, 2, 3, 4, 5];
const target = 9;
// 출력: Found from 1 to 3 (2 + 3 + 4)

• left와 right로 구간을 유연하게 이동
• 누적합과 비교하며 구간의 길이 조절

✅ 장점 요약

항목 설명

✅ 마무리 정리

Two Pointers는 다양한 배열/문자열 문제에 활용 가능한 강력한 도구입니다. 특히 정렬된 배열이나 구간 탐색 문제에서 매우 유용하며, 슬라이딩 윈도우와 함께 쓰이기도 합니다.

복잡한 알고리즘보다도 간단한 반복문 조작으로 충분한 문제에서는 가장 먼저 고려해볼 전략입니다.

✅ 관련 문제 풀이

Easy

• 392. Is Substring?
• 125. Valid Palindrome