투 포인터

✨ 투 포인터란?

• 정렬된 배열이나 리스트에서 주로 사용되는 알고리즘 기법
• 두 개의 포인터를 사용하여 효율적으로 문제 해결
• 시간 복잡도를 O(n²) → O(n) 으로 개선 가능
• 전제 조건: 배열이 오름차순(또는 내림차순)으로 정렬되어 있어야 함

---

🧩 투 포인터의 종류

두 방향 포인터

• 시작(start)과 끝(end) 포인터가 중앙으로 이동하며 조건 탐색
• 예시: 합이 k인 두 수 찾기

한 방향 포인터

• 한쪽 포인터 고정, 다른 포인터만 이동하며 모든 부분 배열 또는 쌍 순회
• 예시: 두 수의 차가 k인 쌍 개수 세기

슬라이딩 윈도우

• 고정된 크기 혹은 조건을 만족하는 구간을 이동하며 탐색
• 구간 길이가 고정인 경우와 조건 만족 시까지 크기가 가변적인 경우 존재
• 예시: 고정 길이 k인 부분 배열의 최대 합

---

❓ 두 수의 합이 특정 값이 되는 쌍 찾기

https://jojozhuang.github.io/algorithm/algorithm-two-pointers/

Brute Force (완전 탐색)

• 모든 쌍을 비교해 목표 값과 같은지 확인
• 시간 복잡도: O(n²)

이진 탐색

• 각 원소에 대해 이진 탐색 수행
• 시간 복잡도: O(n log n)

투 포인터 알고리즘

• 배열의 양 끝에서 포인터를 시작하여 조건에 따라 포인터 이동
• 시간 복잡도: O(n)

https://jojozhuang.github.io/algorithm/algorithm-two-pointers/

투 포인터 코드

function findPairWithSum(nums, target) {
  let start = 0;
  let end = nums.length - 1;

  while (start < end) {
    const sum = nums[start] + nums[end];

    if (sum === target) {
      return [nums[start], nums[end]];
    }

    if (sum < target) {
      start++;
    }

    else {
      end--;
    }
  }

  return null;
}

---

🔗 예제

1. 수들의 합 2 https://www.acmicpc.net/problem/2003
2. 좋다 https://www.acmicpc.net/problem/1253
3. 부분합 https://www.acmicpc.net/problem/1806
4. 구명보트 https://school.programmers.co.kr/learn/courses/30/lessons/42885
5. 보석 쇼핑 https://school.programmers.co.kr/learn/courses/30/lessons/67258