[알고리즘] 투 포인터 알고리즘과 슬라이딩 윈도우 알고리즘

오규성·2025년 11월 1일

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

하나의 배열이나 리스트 같은 선형적인 자료구조에서 두 개의 포인터 를 활용하여 문제를 해결하는 기법으로, 두 개의 포인터 간의 길이가 가변적이다.

투 포인터 알고리즘의 경우 중첩 루프를 활용하면 O(n^2) 의 시간이 소요되는 것을 두 포인터가 배열을 한 번만 훑게 만들어 O(n) 의 시간복잡도로 해결할 수 있게 만들어준다.

특징

투 포인터이기에 두 개의 변수를 지정. 보통은 left, right 나 start, end 라는 이름으로 지정하여 사용한다.

사전 조건으로 정렬을 필요로 한다.

조건은 항상 left <= right, start <= end 이다. 이것이 거짓이 되면 탐색을 종료한다.

두 포인터간의 간격이 가변적이다.

예시 문제

백준 3273 - 두 수의 합

수열 내에서 x 와 같은 ij 쌍이 몇 개인지 구하는 문제이다.
투 포인터 알고리즘을 활용한다. (left, right)

수열 객체를 선언하고 정렬한다.
left = 0, right = 수열 사이즈 - 1 로 지정한다.
값을 비교하여 left, right, count 를 변경해준다.
3-1.arr[left] + arr[right] 가 x 와 같다면 count 를 증가시키고 left++ 한다.
3-2. arr[left] + arr[right] 가 x 보다 크다면 right-- 한다.
3-3. arr[left] + arr[right] 가 x 보다 작다면 left++ 한다.
이를 left < right 가 거짓이 될 때 까지 반복한다.

fun `3273 - 두 수의 합`(){
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val n = br.readLine().toInt()
    val token = java.util.StringTokenizer(br.readLine())
    val arr = IntArray(n){ token.nextToken().toInt() }
    val x = br.readLine().toInt()
    var count = 0

    arr.sort()

    var left = 0
    var right = n - 1

    while(left < right){
        val sum = arr[left] + arr[right]

        when {
            sum == x -> {
                left++
                count++
            }
            sum > x -> right--
            else -> left++
        }
    }

    bw.write(count.toString())
    bw.flush()
    bw.close()
    br.close()
}

슬라이딩 윈도우 (Sliding Window) 알고리즘의 정의

투 포인터 알고리즘과 비슷하게 포인터들을 사용하지만, 포인터 간의 간격 (길이) 가 고정적이다.

슬라이딩 알고리즘의 경우의 경우 투 포인터 알고리즘과 동일하게 시간복잡도가 O(n) 을 가진다.

슬라이딩 윈도우 알고리즘의 특징

두 개의 포인터를 사용하기에 투 포인터에 속하지만, 그와는 다른 특별한 알고리즘이다.
데이터의 연속된 부분을 다루기 때문에, 원래 순서가 보장되어야 한다. 즉, 정렬이 권장되지 않는다.
연속된 데이터 구간에서 최대값, 최소값, 합계 등을 구할 때 사용된다.
포인터 간격이 가변적일 수 있고, 고정일 수 있다.
두 포인터는 같은 방향으로 움직인다.

예시 문제

[백준] 1806 - 부분합

이것은 특정한 합 이상을 나타내는 연속적인 부분합의 최소 개수 구하기 문제이다.
가변 슬라이딩 윈도우을 활용하여 풀 수 있다.


fun `1806 - 부분합`(){
    val br = System.`in`.bufferedReader()
    val bw = System.out.bufferedWriter()
    val (n, s) = br.readLine().split(" ").map { it.toInt() }
    val token = java.util.StringTokenizer(br.readLine())
    val arr = IntArray(n){ token.nextToken().toInt() }

    var start = 0
    var end = 0
    var currentSum = 0
    var minLength = Int.MAX_VALUE

    while(true){
        when {
            // 현재 합이 S 보다 크거나 같은 경우 minLength, currentSum 을 조정하고 start 늘려주기
            currentSum >= s -> {
                minLength = kotlin.math.min(minLength, end - start)
                currentSum -= arr[start]
                start++
            }
            // currenSum 이 s 이상이 아니고 end 가 n 과 같다면 종료
            end == n -> break
            // currentSum 이 s 미만이므로 end 를 늘리면서 currentSum 합해주기.
            currentSum < s -> {
                currentSum += arr[end]
                end++
            }
        }
    }

    bw.write(if(minLength == Int.MAX_VALUE) "0" else minLength.toString())
    bw.flush()
    bw.close()
    br.close()
}