[Algorithm] 투포인터(Two Pointer) & Sliding Window

투포인터(Two Pointer)

리스트에 순차적으로 접근해야 할 때 두개의 점의 위치를 기록하면서 처리하는 알고리즘

 

예제 (연속 부분 수열)

어떤 숫자들의 리스트가 주어질 때, 해당 리스트의 연속 수열의 합이 특정 값(m)을 가지는 경우의 

public class p04 {
    public static int solution(int n , int m, int[] arr){
        int answer = 0;
        int lt = 0;
        int sum = 0;
        for(int rt = 0; rt < n; rt++){
            sum += arr[rt];
            if(sum == m) answer ++;

            while(sum >= m) {
                lt++;
                sum -= arr[lt];
                if(sum == m) answer++;
            }
        }
        return answer;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] arr = new int[n];
        for(int i = 0; i < n; i++) arr[i] = sc.nextInt();
        System.out.println(solution(n,m,arr));
    }
}

---

Sliding Window

고정 사이즈의 윈도우가 이동하면서 윈도우 내에 있는 데이터를 이용해 문제를 풀이하는 알고리즘

교집합의 정보를 공유하고, 차이가 나는 양쪽 끝 원소만 갱신하는 방법

투 포인터 알고리즘과 연동하여 많이 쓴다.

 

---

source

https://butter-shower.tistory.com/226

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

https://ji-musclecode.tistory.com/37

슬라이딩 윈도우 알고리즘(Sliding Window) (feat. 투 포인트)

https://www.inflearn.com/course/%EC%9E%90%EB%B0%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%ED%85%8C%EB%8C%80%EB%B9%84/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 - 인프런 | 강의