투 포인터 테크닉에 대해 이해하기 쉽게 포스팅 하였습니다.

투포인터

• 1차원 배열에서 각자 다른 원소를 가리키는 2개의 포인터를 사용하여 목표값을 구할때 사용합니다.
• 완전탐색 O(n^2) 솔루션을 --> 선형 O(n)으로 성능 향상
  즉, 다시말해 포인터 알고리즘이 O(n)과 O(n log n) 사이의 성능을 제공합니다.
  따라서, 사용 시 알고리즘의 목적에 따라 투 포인터가 확실히 완전 탐색(O(n^2))보다 성능이 좋습니다.
• 보통 연속된 구간의 원소들을 처리하기를 원하거나, 정렬된 배열에서 무언가를 구할때 투 포인터를 사용한다고 보시면됩니다.
• 다시 말해, 투 포인터 알고리즘의 핵심은 정렬된 배열에서 두 개의 포인터를 이용해 효과적으로 목표 값을 찾는 것입니다.
  이를 통해 두 포인터(left와 right)를 적절하게 이동시키면서 문제를 해결할 수 있습니다.
  일반적으로 배열이 정렬되어 있어야 투 포인터 알고리즘이 동작합니다.--> 이러한 이유때문에 필자는 Arrays.sort 를 투포인터 문제면 거의 무조건 사용합니다.
  투 포인터 알고리즘을 사용하여 주어진 정렬된 배열에서 두 숫자의 합이 목표 값과 같은 경우를 찾는 로직을 이해하기 쉽게 자바코드로 구현해보았습니다. 도움이 되었으면 좋겠습니다.

import java.util.*;
public class TwoPointerAlgorithm {
    public static void main(String[] args) {
        int[] array = new int[] {1, 3, 5, 6, 8, 10, 12, 15};
        int target = 10; // 찾고자 하는 합

        int left = 0;
        int right = array.length - 1;
        boolean found = false;

        while (left < right) {
            int currentSum = array[left] + array[right];

            if (currentSum == target) {
                found = true;
                break;
            }

            if (currentSum < target) {
                left++; // 합이 작으면 왼쪽 포인터를 오른쪽으로 이동
            } else {
                right--; // 합이 크면 오른쪽 포인터를 왼쪽으로 이동
            }
        }

        if (found) {
            System.out.println("Found: " + array[left] + " + " + array[right] + " = " + target);
        } else {
            System.out.println("Not found");
        }
    }
}

코드 설명

위 코드에서 array[] 배열에 정렬된 정수 배열이 이미 주어져 있습니다.
만약 정렬되지 않은 배열이 주어진다면, 투 포인터 알고리즘을 적용하기 전에 정렬을 해줘야합니다.
이땐, 필자가 좋아하는Arrays.sort()를 사용하여 배열을 정렬해줘야 합니다.
위 코드는 목표 값(target이 여기서는 10)이 주어진 정렬된 배열에서 두 개의 숫자를 더했을 때, 합이 목표 값과 같은 경우를 확인하는 코드입니다. 배열에서 숫자를 찾지 못하면 "Not found"을 출력하고, 찾으면 해당 숫자와 목표 값의 합을 출력하게 됩니다.

1. 1차원 배열에서 2개의 포인터

그림에서 알 수 있듯이, 2개의 포인터가 모두 왼쪽에서 시작해서 같은 방향으로 이동하고 있습니다.

2. 2개의 포인터가 양쪽 편의 끝에서부터 서로를 향해 이동

다음의 키워드가 등장하면 투 포인터 접근을 시도해 볼 가치가 있다.

1. 1차원 배열에서의 "연속 부분 수열" or "순서를 지키며 차례대로"

2. 곱의 최소의 경우의 수

(출처)

참고

이 두개의 전제조건은, sorting이 되어있어야 최고의 시간 복잡도를 발휘할 수 있으며, 좋은 시너지를 낼 수 있습니다. 따라서 sortiong이 되어있어야 좋다는 점입니다.

투 포인터와 슬라이딩 윈도우 알고리즘의 차이점

이미지를 참고하면, 투 포인터는 구간의 넓이가 고정적이지 않습니다. --> 타겟으로 지정한 (좌, 우) 포인터를 조건에 따라서 이동시켜서 맞닥뜨려야지 끝나는 알고리즘이기 때문에 유동적으로 변합니다.
But, 슬라이딩 윈도우 같은 경우 타겟의 범위를 지정하여, 항상 구간의 넓이가 고정되어 있습니다.
즉, 정적으로 넓이가 표현되어 구현되는 것이 특징입니다.
이러한 특징 덕분에 슬라이딩 알고리즘 같은 경우, 상황에 맞게 잘 사용한다면 ALU의 시간 단축에 매우 효과적일 것입니다.