투 포인터

[SeoMiYoung]

1. 투 포인터

✨ 투 포인터 이동 규칙

• ⚠️ 중요: 각 포인터는 한 방향으로만 움직인다!
  • 패턴1: start는 오른쪽으로만, end는 왼쪽으로만 움직인다.
  • 패턴2: start와 end 모두 오른쪽으로만 움직인다.

---

1-1. 패턴1: 양 끝에서 만나기

📍 포인터 초기화

int start = 0;
int end = arr.length - 1;

🎯 이동 규칙

• arr[start] + arr[end] < target → start를 증가 (작은 값 키우기)
• arr[start] + arr[end] > target → end를 감소 (큰 값 줄이기)
• arr[start] + arr[end] == target → 정답 처리 후 start++, end--

🔄 종료 조건

while (start < end) {
    // 포인터가 만나거나 교차하면 종료
}

💡 사용 예시

• 정렬된 배열에서 두 수의 합 찾기
• 팰린드롬 판별
• 3sum, 4sum 문제

📝 예시 코드

int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int target = 10;
int start = 0;
int end = arr.length - 1;

while (start < end) {
    int sum = arr[start] + arr[end];
    
    if (sum == target) {
        // 찾았다!
        start++;
        end--;
    }
    else if (sum < target) {
        start++;  // 합을 키워야 함
    }
    else {
        end--;    // 합을 줄여야 함
    }
}

---

1-2. 패턴2: 같은 방향 (연속 구간)

📍 포인터 초기화

int start = 1;  // 또는 0
int end = 1;    // 또는 0

🎯 이동 규칙

• sum < target → end를 증가 (구간을 늘려서 합을 키움)
• sum > target → start를 증가 (구간을 줄여서 합을 작게 만듦)
• sum == target → 정답 카운트 후 다음 탐색

❓ sum == target일 때 이동 방향

• start++ 또는 end++ 중 하나만 증가시키면 된다
• 둘 중 어느 쪽을 선택해도 투 포인터 알고리즘 특성상 결국 모든 가능한 구간을 탐색하게 되므로 결과는 동일하다
• 일반적으로 end++만 증가시키는 것이 관례이다 (start++만 해도 무방)
• start++와 end++ 둘 다 증가시키는 것은 비효율적이므로 권장하지 않는다

🔄 종료 조건

while (start <= n) {
    // start가 범위를 벗어나면 종료
}

• start가 n을 넘으면 더 이상 n을 만들 수 없음
• 예: n=15일 때 start=16이면 최소값이 16이므로 15를 만들 수 없음

💡 사용 예시

• 연속된 자연수의 합
• 부분 배열의 합이 k인 경우
• 조건을 만족하는 최소/최대 구간 길이

📝 예시 코드

int n = 15;
int start = 1;
int end = 1;
int count = 0;

while (start <= n) {
    // start부터 end까지의 합 계산
    int sum = (end * (end + 1)) / 2 - ((start - 1) * start) / 2;
    
    if (sum == n) {
        count++;
        end++;     // 다음 구간 탐색
    }
    else if (sum < n) {
        end++;     // 구간 확장
    }
    else {         // sum > n
        start++;   // 구간 축소
    }
}

---

📊 패턴 비교 정리

구분	패턴1 (양 끝)	패턴2 (연속 구간)
초기화	start=0, end=n-1	start=0, end=0
이동 방향	start ➡️, end ⬅️	start ➡️, end ➡️
종료 조건	start < end	start <= n
대표 문제	두 수의 합	연속 구간 합
전제 조건	정렬된 배열	연속된 값