[알고리즘] 투포인터

1. 투포인터(Two Pointers)

• 정렬된 리스트를 두 개의 포인터를 이용해 순차적으로 접근하면서 두 포인터 구간의 값이 
  타겟 값과 같을 때까지 포인터를 조작하는 기법이다.
  → 보통 l(left), r(right) 또는 s(start), e(end) 같은 식으로 포인터의 이름을 붙임.
• 정렬되어있는 두 리스트의 합집합에도 사용
• 합병정렬의 counquer 영역의 기초가 되기도 함
• 시간 단축

 

1-1. 포인터 방식

• 맨 처음 두 포인터는 0에서 시작, start <= end 를 만족해야함.
• 부분합 배열의 합 < 구해야하는 값
  → end를 오른쪽으로 한 칸 이동하여 부분합 배열의 크기를 증가시킴
• 부분합 배열의 합 >= 구해야하는 값
  → start를 오른쪽으로 한 칸 이동하여 부분합 배열의 크기를 감소시킴
• 위 과정을 start 인텍스가 (리스트 크기-1)이 될때까지 반복

 

2. 투포인터 예제 및 풀이(백준 2003번 : 수들의 합2)

 

public class Main {
 
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 2, 5, 3, 1, 1, 2}; // 크기가 10인 1차원 배열 
        int m = 5; // 연속된 구간의 합이 5인 경우를 찾는다.
        
        int count = twoPointers(arr, m);
    }
    
    private static int twoPointers(int[] arr, int m) {
        int sum = 0, count = 0;
        int left = 0, right = 0;
        
        while (true) {
            if (sum > m) { // 1. left를 우측으로 옮기는 경우 
                sum -= arr[left++];
            } else if (right == arr.length - 1) { 
			// right를 우측으로 옮기기 전에 배열의 끝을 가리키는지 확인한다.
                break;
            } else { // 2. right를 우측으로 옮기는 경우 
                sum += arr[right++];
            }
            
            if (sum == m) count++;
        }
        
        return count;
    }
}

 

 

 

 

 

참고) https://github.com/WooVictory/Ready-For-Tech-Interview/blob/master/Algorithm/%ED%88%AC%ED%8F%AC%EC%9D%B8%ED%84%B0%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98.md

GitHub - WooVictory/Ready-For-Tech-Interview: 💻 신입 개발자로서 준비를 하기 위해 지식을 정리하는 공간

 

참고) https://ssungkang.tistory.com/entry/Algorithm-Two-Pointers-%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0

[Algorithm] Two Pointers, 투 포인터

 

참고) https://www.lifencoding.com/algorithm/13?p=1 

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

 

참고) https://www.acmicpc.net/problem/2003

2003번: 수들의 합 2