[알고리즘] 투 포인터 알고리즘 (Two Pointer Algorithm)

투 포인터 알고리즘 (Two Pointer Algorithm)

• 배열이나 리스트에서 '두 개의 포인터'를 사용하여 '특정 조건을 만족하는 부분 구간'을 효율적으로 탐색하는 알고리즘이다. 일반적으로 배열이나 리스트가 '정렬되어 있을 때' 사용한다.
• 투 포인터 알고리즘은 보통은 왼쪽 포인터와 오른쪽 포인터를 사용하며, 이들은 각각 탐색 범위의 시작과 끝을 가리킨다.
• 또는 동일한 시점을 기점으로 왼쪽 포인터를 고정한 상태에서 오른쪽 포인터를 이동하고, 조건에 따라 왼쪽 포인터도 이동하며 탐색하는 방식을 가진다.
• 해당 알고리즘은 탐색 범위 내에서 특정 조건을 만족하는 요소를 찾거나, 조건을 만족하는 부분 배열의 길이 등을 계산하는 데 사용될 수 있다.

 

투 포인터 수행 단계

1. 배열 또는 리스트의 시작 위치에 첫 번째 포인터와 두 번째 포인터를 설정한다.
2. 두 포인터 사이의 구간을 조사하고 조건을 확인한다.
3. 조건을 만족할 경우, 원하는 결과를 얻었으므로 알고리즘을 종료한다.
4. 조건을 만족하지 않을 경우, 첫 번째 또는 두 번째 포인터를 이동시킨다.
5. 다시 2번 단계로 돌아가 반복한다.

 

투 포인터 시간 복잡도

• 투 포인터 알고리즘은 선형시간 복잡도를 가지므로 효율적이다. 또한 한 번의 반복으로 모든 요소를 처리하기에 효율적이다.
• 일반적으로 빅오 표기법을 이용하여 표기하였을 때 O(N)이다. 이는 배열이나 리스트 크기에 비례하여 알고리즘의 수행시간이 증가한다는 의미이다.

출처 : https://adjh54.tistory.com /186

 

두 포인터의 합과 차

• 투 포인터 알고리즘을 사용하여 풀 수 있는 대표적인 문제의 유형이다.
• 배열이나 리스트에서 두 개의 포인터를 사용하여 합이나 차를 계산한다.
• 보통 왼쪽 포인터와 오른쪽 포인터를 사용하며, 이들은 각각 탐색 범위의 시작과 끝을 가리킨다.
• 이 유형은 두 요소의 합이나 차가 주어진 값과 일치하는지 확인하는 등의 문제에 사용될 수 있다.

출처 : https://colabear754.tistory.com/69

풀이 과정

 - 주어진 정수 배열에서 두 개의 숫자를 선택하여 합이 특정한 값(target)을 갖는지 확인하는 문제를 해결한다.

1. left와 right라는 두 개의 포인터를 배열의 양 끝에서 시작한다.
2. left 값보다 right 값이 큰 경우일 때까지 반복한다.
3. left와 right의 합을 sum에 저장한다.
4. 만약 sum이 target과 같다면, count 값을 증가하며 left 인덱스는 오른쪽으로 이동하고 right 인덱스는 왼쪽으로 이동한다.
5. 그렇지 않고 sum이 target보다 작다면, left를 한 칸 오른쪽으로 이동시킨다.
6. sum이 target보다 크다면, right를 한 칸 왼쪽으로 이동시킨다.
7. 해당 조건에 만족하는 count 값을 반환한다.

풀이 코드 예시

import java.util.Arrays;

public class TwoPointerSum {

    public static int twoPointerSum(int[] arr, int target) {
        // 배열을 정렬합니다. 투 포인터 알고리즘을 사용하기 위해 정렬이 필요합니다.
        Arrays.sort(arr);

        // 왼쪽 포인터를 배열의 첫 번째 요소로 설정합니다.
        int left = 0;

        // 오른쪽 포인터를 배열의 마지막 요소로 설정합니다.
        int right = arr.length - 1;

        // 조건을 만족하는 쌍의 개수를 세기 위한 변수를 초기화합니다.
        int count = 0;

        // 왼쪽 포인터가 오른쪽 포인터보다 작은 동안 반복합니다.
        while (left < right) {
            // 현재 포인터들이 가리키는 두 값의 합을 계산합니다.
            int sum = arr[left] + arr[right];

            // 두 값의 합이 목표 값과 같은 경우
            if (sum == target) {
                // 카운트를 증가시킵니다.
                count++;

                // 왼쪽 포인터를 오른쪽으로 한 칸 이동합니다.
                left++;

                // 오른쪽 포인터를 왼쪽으로 한 칸 이동합니다.
                right--;
            }
            // 두 값의 합이 목표 값보다 작은 경우
            else if (sum < target) {
                // 왼쪽 포인터를 오른쪽으로 한 칸 이동하여 합을 증가시킵니다.
                left++;
            }
            // 두 값의 합이 목표 값보다 큰 경우
            else {
                // 오른쪽 포인터를 왼쪽으로 한 칸 이동하여 합을 감소시킵니다.
                right--;
            }
        }

        // 조건을 만족하는 쌍의 개수를 반환합니다.
        return count;
    }

    public static void main(String[] args) {
        // 예시 배열과 목표 값을 정의합니다.
        int[] arr = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int target = 10;

        // 함수 호출 및 결과 출력
        System.out.println(target + "을(를) 만드는 쌍의 개수는: " + twoPointerSum(arr, target) + "개입니다.");
    }
}

 

투 포인터 알고리즘을 알고 있으면 문제를 풀다가 적용시킬 일이 꽤 많이 있다. 오늘도 하나 배웠다!😃

 

출처 / 참고 : https://adjh54.tistory.com/