슬라이딩 윈도우와 투 포인터

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

• 두 알고리즘은 1차원 배열에서 사용시 선형 공간을 2회 이상 반복적으로 탐색해야할 경우 O(N^2) 이상 걸리는 시간 복잡도를 부분 배열을 활용하여 O(N)의 시간으로 단축 시키는데 의의가 있다
• 두 알고리즘의 차이는 부분 배열 길의의 변화
• 슬라이딩 윈도우 : 부분 배열의 길이가 고정적
• 투 포인터 : 부분 배열의 길이가 가변적

슬라이딩 윈도우 : 개념

• 부분 배열의 길이가 고정적인 알고리즘
• 투 포인터와 같이 2개의 포인터가 필요하지 않음 : 고정적인 부분 배열의 크기를 나타내는 변수가 있다면 포인터 하나로도 종료지점을 알 수 있음
• 배열의 부분 합을 구하는 문제 : 오른쪽으로 한 칸 옮기고 옮기기 전 부분 배열과 옮기고 난 후에 겹치는 부분이 존재할 때, 기존 구간에서 빠지게 되는 부분인 왼쪽의 값을 삭제하고 새로 추가되는 오른쪽 값을 삽입한다.

슬라이딩 윈도우 : 풀이

https://www.acmicpc.net/problem/2559

2559번: 수열

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N, M, arr[];


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        System.out.println(slidingWindow());


    }

    private static int slidingWindow() {
        int sum = 0;
        int max = 0;
        for (int i = 0; i < N; i++) {
            sum += arr[i]; // 값은 계속 갱신해야함
            if (i == M - 1) {
                max = sum; // 처음 최대값 저장
            }

            if (i >= M) {
                sum -= arr[i - M];
                max = Math.max(max, sum);
            }

        }
        return max;

    }

}

투 포인터 : 개념

• 투 포인터는 연속되고 길이가 가변적인 부분 배열들을 활용하여 특정 조건을 일치시키는 알고리즘

대표적인 2가지 유형

1. 2개의 포인터 변수 시작점이 배열의 시작점인 경우
2. 정렬된 배열 안에서 2개의 포인터 변수가 각각 시작점과 끝점에 위치하는 경우

• 투 포인터는 포인터를 가르키는 변수 2개를 사용 : left , right
• *포인터의 흐름 *

(1) 부분 배열의 합이 Target 값보다 크거나 같으면 Left = Left + 1 (부분 배열의 길이를 줄여 합을 빼준다. )

if(sum >= Target) Left++;

(2) 부분 배열의 합이 Target 값보다 작으면 Right = Right + 1 (부분 배열의 길이를 늘려 합을 더한다.)

if(sum < Target) Right++;

(3) 부분 배열의 합이 Target 값과 같다면 결과 값을 +1

if( sum == Target) count++;

 

 

투 포인터  : 풀이

https://www.acmicpc.net/problem/2230

2230번: 수 고르기

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }
        Arrays.sort(arr);

        int i = 0, j = 0;
        int ans = Integer.MAX_VALUE;
        // 투 포인터 알고리즘
        while (i < N) {
            if (arr[i] - arr[j] < M) {
                i++;
                continue;
            }

            if (arr[i] - arr[j] == M) {
                ans = M;
                break;
            }

            ans = Math.min(ans, arr[i] - arr[j]);
            j++;
        }

        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }

}