[자료 구조/알고리즘] 투 포인터 기법 - 구현
투 포인터 기법 구현
투 포인터(two pointers) 기법은 배열과 리스트 같은 선형(linear) 자료 구조에서 데이터를 순차적으로 탐색하는데 사용되는 방법 중 하나이다. 배열이나 리스트 자료 구조에서 두 개의 서로 다른 포인터를 사용하여 자료 구조를 탐색한다.
배열 자료 구조에서 두 포인터를 각각 양쪽 끝에서 시작하여 서로 반대 방향으로 이동시켜 서로 만나도록 포인터를 이동시키는 구현은 다음과 같다.
val nums: IntArray
val target = 0
val left = 0
val right = nums.length - 1
while (left != right) {
if (왼쪽 포인터 이동 조건) {
left += 1;
} else if (오른쪽 포인터 이동 조건) {
right -= 1;
} else {
// 포인터 이동이 필요 없는 경우 (문제의 해답을 구한 경우)
}
}
다음은 배열에서 두 원소를 더하여 특정 값을 만들 수 있는 두 원소의 인덱스를 반환하는 구현 예이다.
fun solve(nums: IntArray, int target) {
val left = 0
val right = nums.size - 1
while (left != right) {
if (nums[left] + nums[right] < target) {
left += 1;
} else if (nums[left] + nums[right] > target) {
right -= 1;
} else {
return intArrayOf(left, right)
}
}
return intArrayOf(0, 0)
}
연결 리스트 자료 구조에서 두 포인터를 동일한 시작점에서 시작하여 서로 같은 방향으로 이동시키되 서로 다른 속도로 이동시켜 특정 시점에 서로 만나도록 하는 구현 예는 다음과 같다.
// 연결 리스트 노드 클래스
data class ListNode(var `val`: Int, var next: ListNode? = null)
fun solve(head: ListNode?) {
if (head?.next == null) {
// 빈 리스트이거나 노드가 하나만 있는 경우
}
var slowPointer: ListNode? = head
var fastPointer: ListNode? = head
// 두 포인터가 만날 때까지 반복
while (fastPointer != null && fastPointer.next != null) {
// 느린 포인터는 한 칸 이동
slowPointer = slowPointer?.next
// 빠른 포인터는 두 칸 이동
fastPointer = fastPointer.next?.next
if (slowPointer == fastPointer) {
// 두 포인터가 만나는 경우
}
}
// 두 포인터가 만나지 않고 빠른 포인터가 null에 도달
}
위 구현은 연속적인 자료 구조에서 주기적인 반복 참조 구조인 순환(cycle) 구조를 찾는 순환 탐지(cycle detection) 알고리즘에서 사용된다. 연결 리스트에서 마지막 노드가 첫 번째 노드를 참조하는 경우 해당 연결 리스트는 순환 구조를 가지고 있다. 순환 탐지 알고리즘 중 하나인 플로이드 알고리즘은 두 개의 포인터가 동일한 위치에서 이동을 시작하지만 서로 다른 속도로 이동(하나의 포인터는 한 번에 1씩, 다른 포인터는 2씩 이동)한다. 순환 구조가 존재한다면 두 포인터는 어느 시점에 만나게 되며 순환 구조가 없다면 두 포인터는 각각 양쪽 끝에 도달한다.
슬라이딩 윈도우 기법 구현
슬라이딩 윈도우(sliding window) 기법이란 고정된 크기의 데이터를 포함하는 윈도우(window)를 사용하여 이를 이동시키면서 전체 데이터를 탐색하여 문제를 해결하는 방법이다.
슬라이딩 윈도우는 기본적으로 두 개의 포인터(left와 right)를 사용하여 배열의 연속적인 부분(윈도우)을 정의하고, 이 윈도우를 배열 상에서 움직이면서 특정 조건을 만족하는 값을 찾는 방식으로 구현한다.
슬라이딩 윈도우 기법은 크게 두 가지 방법으로 구현할 수 있다.
- 고정 크기 슬라이딩 윈도우: 슬라이딩 윈도우의 크기가 미리 정해져 있는 경우
- 가변 크기 슬라이딩 윈도우: 슬라이딩 윈도우의 크기가 동적으로 변하는 경우
고정 크기 슬라이딩 윈도우 기법에서는 윈도우의 크기가 k
로 미리 정해져 있다. 초기에는 윈도우의 크기를 k
까지 확장한다. 윈도우의 크기가 정해진 크기인 k
에 도달하면 right
포인터를 k
부터 배열의 끝까지 한 칸씩 이동시킨다. 이때, left
포인터도 함께 한 칸씩 이동시킴으로써 고정 크기의 윈도우를 한 칸씩 움직인다. left
포인터의 배열 인덱스 값은 right - k
값과 동일하다.
fun solve(arr: IntArray, k: Int) {
val n = arr.size
if (n < k) {
// 배열 길이가 k보다 짧을 경우
}
// 1. 초기 윈도우 (left = 0, right = k-1)에 대한 계산 수행
for (i in 0 until k) {
...
}
// 2. 윈도우 슬라이딩
// 오른쪽 포인터를 k부터 배열의 끝까지 이동시킨다.
for (right in k until n) {
// 슬라이딩 윈도우의 가장 오른쪽 포인터는 right이며, 가장 왼쪽 포인터는 right - k이다.
// 윈도우를 슬라이딩 하면서 이전에 계산한 값을 재사용한다.
}
...
}
주어진 정수 배열에서 길이가 k
인 모든 부분 배열의 합을 구하는 예는 다음과 같다.
fun solve(arr: IntArray, k: Int): List<Int> {
val n = arr.size
if (n < k) {
// 배열 길이가 k보다 짧으면 빈 리스트 반환
return emptyList()
}
var windowSum = 0
val resultSums = mutableListOf<Int>()
// 1. 초기 윈도우 (left = 0, right = k-1)의 합 계산
for (i in 0 until k) {
windowSum += arr[i]
}
resultSums.add(windowSum)
// 2. 윈도우 슬라이딩
// 오른쪽 포인터를 k부터 배열의 끝까지 이동시킨다.
for (right in k until n) {
// 윈도우에 새로운 요소 추가 (arr[right])
// 윈도우에서 가장 왼쪽 요소 제거 (arr[right - k]는 left 포인터가 가리키는 값이다.)
windowSum += arr[right] - arr[right - k]
resultSums.add(windowSum)
}
return resultSums
}
가변 크기 슬라이딩 윈도우 기법에서는 윈도우의 크기가 미리 정해져 있지 않다. right
포인터를 처음부터 배열의 끝까지 한 칸씩 이동시키며 윈도우의 크기를 확장한다. 이때, 특정 조건이 충족되면 left
포인터를 한 칸씩 이동시켜 윈도우 크기를 축소한다. 이렇게 함으로써 윈도우의 크기를 계속해서 변화시키며 이동시킨다.
fun solve(arr: IntArray) {
val n = arr.size
if (n == 0) {
...
}
var left = 0
// 윈도우 슬라이딩
// 오른쪽 포인터를 처음부터 배열의 끝까지 이동시킨다.
for (right in 0 until n) {
// 윈도우를 슬라이딩 하면서 이전에 계산한 값을 재사용한다.
while(왼쪽 포인터 이동 조건) {
left++
}
}
...
}
중복 문자가 없는 가장 긴 부분 문자열의 길이를 찾는 예는 다음과 같다.
fun solve(s: String): Int {
val n = s.length
if (n == 0) {
return 0
}
// 현재 윈도우 내의 고유 문자를 저장할 Set
val charSet = HashSet<Char>()
var left = 0
var maxLength = 0
// 오른쪽 포인터를 처음부터 문자열의 끝까지 이동시킨다.
for (right in 0 until n) {
val currentChar = s[right]
// 윈도우에 현재 문자가 이미 있다면 (중복 존재)
// 왼쪽 포인터를 이동시켜 중복을 제거한다.
while (charSet.contains(currentChar)) {
// 왼쪽 포인터에 해당하는 문자를 Set에서 제거한다.
charSet.remove(s[left])
left++
}
// 중복이 제거되었거나 새로운 문자이므로 Set에 추가
charSet.add(currentChar)
// 현재 윈도우의 길이 계산 (right - left + 1) 및 최대 길이 업데이트
maxLength = maxOf(maxLength, right - left + 1)
}
return maxLength
}
Comments