Two Pointers

이번에는 투 포인터 알고리즘에 대해 알아보자.
투 포인터는 배열이나 리스트와 같은 자료구조에서 두 개의 포인터를 사용하여 효율적으로 문제를 해결하는 방법으로, 특히 연속된 부분 구간을 다루는 문제에서 매우 유용하다.

투 포인터 알고리즘 개요

투 포인터 알고리즘은 배열의 특정 구간을 탐색하거나 두 개의 포인터를 조정해가며 문제를 해결하는 방법이다.
일반적으로 시작 지점과 끝 지점에서 두 개의 포인터를 두고, 조건에 따라 포인터를 이동시키면서 문제를 해결한다.
이 방법은 주로 정렬된 배열에서 많이 사용된다.

투 포인터 알고리즘의 동작 원리

투 포인터 알고리즘은 다음과 같은 단계로 동작한다:

1. 초기화
   배열의 시작과 끝 또는 특정 위치에 두 개의 포인터를 설정한다.
2. 조건에 따른 포인터 이동
   두 포인터를 문제의 조건에 따라 이동시킨다. 포인터는 보통 한 번에 한 칸씩 움직이며, 필요에 따라 한쪽 포인터만 이동하거나 양쪽 포인터를 모두 이동할 수 있다.
3. 조건 충족 시 결과 처리
   포인터가 특정 조건을 만족하는 경우, 원하는 값을 저장하거나, 문제를 해결하는 데 필요한 연산을 수행한다.
4. 반복
   포인터가 배열의 끝에 도달할 때까지 또는 문제 해결 조건이 충족될 때까지 2번과 3번 과정을 반복한다.

투 포인터 알고리즘의 시간 복잡도

투 포인터 알고리즘의 시간 복잡도는 O(n)이다.
이는 두 포인터가 배열을 한 번씩만 탐색하기 때문에, 매우 효율적이다.
투 포인터 알고리즘은 특히 배열 내에서의 부분 합, 두 수의 합 등 다양한 문제를 빠르게 해결하는 데 유용하다.

투 포인터 알고리즘 예제 코드

아래는 투 포인터 알고리즘을 사용해 정렬된 배열에서 두 수의 합이 특정 값이 되는지를 찾는 예제 코드이다.

public class TwoPointersExample {

    public static boolean hasPairWithSum(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;

        while (left < right) {
            int sum = arr[left] + arr[right];

            if (sum == target) {
                return true;  // 두 수의 합이 target과 같은 경우
            } else if (sum < target) {
                left++;  // 합이 target보다 작으면 왼쪽 포인터를 오른쪽으로 이동
            } else {
                right--;  // 합이 target보다 크면 오른쪽 포인터를 왼쪽으로 이동
            }
        }

        return false;  // 원하는 두 수를 찾지 못한 경우
    }

    public static void main(String[] args) {
        int[] sortedArray = {1, 2, 3, 4, 6, 8, 9};
        int target = 10;

        if (hasPairWithSum(sortedArray, target)) {
            System.out.println("Array has a pair with the given sum.");
        } else {
            System.out.println("No pair with the given sum found in the array.");
        }
    }
}

투 포인터 알고리즘 사용 사례

• 두 수의 합 문제
  정렬된 배열에서 두 수의 합이 특정 값이 되는지 확인하는 문제에서 투 포인터 알고리즘이 자주 사용된다.
  위의 예제 코드가 바로 이 경우에 해당한다.

• 연속된 부분 배열의 합 문제
  배열에서 연속된 부분 배열의 합이 특정 값을 만족하는지 찾는 문제에서도 투 포인터 알고리즘이 매우 유용하다.

• 팰린드롬 검사
  문자열이 팰린드롬(앞뒤가 같은 문자열)인지 확인하는 문제에서도 투 포인터를 양쪽 끝에 두고 중앙으로 이동시키며 비교하는 방식으로 해결할 수 있다.

• 슬라이딩 윈도우
  투 포인터는 슬라이딩 윈도우 알고리즘에서도 사용된다. 슬라이딩 윈도우는 연속된 데이터의 부분 집합에서 최대 또는 최소 값을 찾는 데 효과적이다.

투 포인터 알고리즘의 장점과 한계

• 장점
  투 포인터 알고리즘은 배열을 한 번만 순회하면서 문제를 해결할 수 있어 매우 효율적이다. 정렬된 배열에서는 특히 강력하며, 다양한 문제를 O(n) 시간 복잡도로 해결할 수 있다.

• 한계
  배열이 정렬되지 않은 경우 투 포인터를 바로 적용하기 어렵다. 이 경우 배열을 정렬한 후 투 포인터 알고리즘을 적용해야 하며, 이로 인해 시간 복잡도가 O(n log n)으로 증가할 수 있다.

투 포인터 알고리즘은 간단하면서도 매우 강력한 도구이다.
이 알고리즘을 잘 이해하고 응용하면 다양한 문제를 효율적으로 해결할 수 있을 것이다.
이 글을 통해 투 포인터 알고리즘에 대해 이해하고, 문제 해결에 활용하는 데 도움이 되길 바란다.