[Algorithm 기초] 투 포인터

 

Two Pointer (투 포인터) 

- 두 개의 포인터를 사용하여 문자열, 배열, List에서 원하는 값을 찾는 선형 구조 알고리즘

- 포인터 배치 방법

   --> 같은 방향에서 시작 : 첫 번째 원소에 둘 다 배치

   --> 서로 다른 방향에서 시작 : 첫 번째 원소와 마지막 원소에 배치

- 한 번의 반복으로 모든 요소를 처리하기에 효율적이며 다중 for문의 복잡도를 좀 더 선형적으로 풀 수 있음

알고리즘 복잡도 : O(n)

투 포인터의 종류

 

1. 고정 길이 슬라이딩 윈도우
- 고정된 길이의 윈도우를 사용하여 배열이나 리스트를 탐색
- 윈도우의 크기를 일정하게 유지하면서 왼쪽 포인터와 오른쪽 포인터를 이동시키며 필요한 계산을 수행
- 부분 배열의 합이나 평균을 계산하는 등의 문제에 사용

2. 가변 길이 슬라이딩 윈도우
- 가변 길이의 윈도우를 사용하여 배열이나 리스트를 탐색
- 윈도우의 크기를 필요에 따라 변경하면서 왼쪽 포인터와 오른쪽 포인터를 이동시키며 필요한 계산을 수행
- 최소 길이 부분 배열이나 최대 길이 부분 배열을 찾는 등의 문제에 사용

3. 두 포인터의 합과 차
- 배열이나 리스트에서 두 개의 포인터를 사용하여 합이나 차를 계산하는 문제를 해결
- 보통 왼쪽 포인터와 오른쪽 포인터를 사용하며, 이들은 각각 탐색 범위의 시작과 끝을 가리킴
- 두 요소의 합이나 차가 주어진 값과 일치하는지 확인하는 등의 문제에 사용

 

 

//투포인터 사용예제
public class twoPointer {
    public static int[] twoPointers(int[] arr, int target){
        int p1 = 0;
        int p2 = 0;
        int sum = 0;
        int[] result = {-1, -1};

        while (true){
            if (sum > target){
                sum -= arr[p1++];
            }else if (p2 == arr.length){
                break;
            }else {
                sum += arr[p2++];
            }

            if (sum == target){
                result[0] = p1;
                result[1] = p2 - 1;
                break;
            }
        }

        return result;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 5, 3, 7, 2, 4, 3, 2};
        System.out.println(Arrays.toString(twoPointers(arr, 9)));
        System.out.println(Arrays.toString(twoPointers(arr, 14)));
    }
}

 

 

 

 

참고link

https://adjh54.tistory.com/398

[Java/알고리즘] 투 포인터 알고리즘(Two Pointer Algorithm) 이해하기 -2: 문제로 이해하기

https://gaybee.tistory.com/36

[알고리즘/JAVA] 투포인터 알고리즘

 

https://hstory0208.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0Two-Pointers-%EC%8A%AC%EB%9D%BC%EC%9D%B4%EB%94%A9-%EC%9C%88%EB%8F%84%EC%9A%B0Sliding-Window

[알고리즘] 투 포인터(Two Pointers)란?

 

https://colabear754.tistory.com/69

투 포인터(Two Pointer) with Kotlin