Kotlin 연습하기(11) - 투 포인터와 슬라이딩 윈도우 알고리즘

투 포인터란 무엇일까?

투 포인터 기법은 배열이나 리스트 등에서 두 개의 인덱스(포인터)를 사용하여 문제를 해결하는 알고리즘이다. 주로 정렬된 배열에서 조건에 맞는 쌍을 찾거나, 두 포인터를 이용해 특정 구간을 탐색할 때 유용하다.

 

 

슬라이딩 윈도우란 또 무엇일까?

슬라이딩 윈도우는 연속된 구간(윈도우)을 다루는 기법으로, 한 번에 한 구간씩 보면서 원하는 조건(예: 합, 평균, 최대/최소값 등)을 만족하는 최적의 결과를 찾는 방법이다.

이때 "윈도우"는 배열이나 문자열에서 연속된 부분을 의미하며, 이 윈도우를 한칸씩 옮겨가며 문제를 해결한다.

 

 

이해가 잘 안된다 실생활 비유? or 더 쉬운 비유로 한번 이해를 해보자.

 

투 포인터 비유 : 책의 양쪽 끝에서 찾기

생각해보자  한 권의 책에서 특정 단어를 찾으려고 할 때, 책의 앞쪽과 뒤쪽에서 동시에 찾아본다면 더 빨리 찾을 수 있지 않을까? 투 포인터는 배열의 양쪽 끝에 포인터를 두고, 조건에 맞게 서로 이동시키면서 문제를 해결하는 기법이다.

 

 

슬라이딩 윈도우 비유 : 창문을 옮겨서 보는 풍경

슬라이딩 윈도우는 마치 큰 창문을 옮겨가며 밖의 풍경을 보는 것과 같다. 창문 너머의 한 부분만 보면서 그 부분의 특징(예: 평균, 합 등)을 차악하고, 창문을 조금씩 옮겨 전체 풍경을 보는 것처럼 배열의 연속된 구간을 살펴본다.

 

살짝 느낌이 온다.

 

 

투 포인터의 기본 원리

동작 방식 : 정렬된 배열에서 왼쪽 포인터는 가장 작은 값을, 오른쪽 포인터는 가장 큰 값을 가리킨다. 두 값을 합하여 조건(target)과 비교한다.

• 합이 target보다 작으면, 더 큰 값을 찾기 위해 왼쪽 포인터를 오른쪽으로 이동한다. 
• 합이 target보다 크면, 더 작은 값을 찾기 위해 오른쪽 포인터를 왼쪽으로 이동한다.

이렇게 하면 조건을 만족하는 두 수를 찾거나, 조건에 맞는 구간을 빠르게 탐색할 수 있다.

 

흠.. 그렇다면 두 구간의 합을 비교하거나, 두 구간의 조건을 동시에 고려 할 때, 두 수의 합이나 곱, 차 등을 구할때 사용하면 좋을 것 같다는 생각이 든다.

 

 

두 수의 합(target)을 구하는 예제를 Kotlin으로 작성해보자

class Solution {
    fun solution(nums: IntArray, target: Int): IntArray {
        var left = 0
        var right = nums.size - 1
        
        while (left < right) {
            val sum = nums[left] + nums[right]
            when {
                sum == target -> return intArrayOf(left, right)
                sum < target -> left++   // 합이 작으면 왼쪽 포인터 이동
                else -> right--          // 합이 크면 오른쪽 포인터 이동
            }
        }
        return intArrayOf() // target을 만족하는 쌍이 없으면 빈 배열 반환
    }
}

// 테스트
fun main() {
    val sol = Solution()
    val result = sol.solution(intArrayOf(1, 2, 3, 4, 6), 7)
    println("두 수의 인덱스: ${result.joinToString(", ")}")
}

 

코드에서 left, right 변수를 따로 설정해 투 포인터 기법을 통해 원하는 두 수의 인덱스를 찾아주었다.

 

 

 

 

슬라이딩 윈도우의 기본 원리

동작 방식 : 배열이나 문자열에서 고정된 크기의 구간(윈도우)를 설정하고, 이 윈도우를 좌우로 옮기면서 원하는 조건(예: 합,평균)을 계산한다.

 

어떻게 작동을 하는걸까?

 

슬라이딩 윈도우는 매번 윈도우를 이동하면서, 윈도우 내의 값을 효율적으로 갱신한다. 새로운 값이 추가되고, 이전 값이 제외되면서 구간의 합이나 평균 등이 빠르게 업데이트된다.

 

글로만 보니까 무슨 말인지 이해가 잘 안된다. 코드로 보면 좀 나으니 예제를 봐보자

 

 

정수 배열에서 연속된 부분 배열의 합이 target 이상이 되는 최고 길이를 찾는 예제이다.

class Solution {
    fun solution(nums: IntArray, target: Int): Int {
        var sum = 0
        var left = 0
        var minLength = Int.MAX_VALUE
        
        for (right in nums.indices) { // indices 파라미터 인덱스 값에 접근한다.
            sum += nums[right]
            
            // 현재 윈도우의 합이 target 이상이면, 최소 길이를 갱신하고 윈도우를 좁힙니다.
            while (sum >= target) {
                minLength = minOf(minLength, right - left + 1)
                sum -= nums[left] // 윈도우를 좁히는 부분
                left++
            }
        }
        
        return if (minLength == Int.MAX_VALUE) 0 else minLength
    }
}

// 테스트
fun main() {
    val sol = Solution()
    val result = sol.solution(intArrayOf(2, 3, 1, 2, 4, 3), 7)
    println("최소 길이: $result")
}

 

실제로 출력되는 값

최소 길이: 2

 

처음에는 왜? 어떻게 동작하는거지? 했지만... 결국 이해했는데 이해한 내용을 적어둔다.

 

1. 주어진 배열 : [2, 3, 1, 2, 4, 3]
2. 목표 합(target) : 7

여기서 연속된 부분의 합이 7 이상이 되는 최소 길이를 찾는 과정인 것이다.

1. 처음 right 포인터가 이동하면서 누적합(sum)이 증가한다.
2. 누적합이 7 이상이 된느 첫 번째 구간은 [2, 3, 1, 2]로, 합은 8이고 길이는 4이다.
3. 윈도우를 좁혀서 최소 길이를 갱신하면, 더 짧은 구간 [4, 3]이 조건을 만족한다. 이 구간의 길이는 2이다.

따라서 최소 길이는 2가 되어, 최종적인 값이 출력되는 것이다.