[자료 구조/알고리즘] 투 포인터 기법 - 구현
투 포인터 기법 구현
투 포인터(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(height: IntArray) {
var left = 0
var right = height.size - 1
var maxArea = 0
while (left < right) {
// 현재 두 선 사이의 너비
val width = right - left
// 현재 두 선 중 더 짧은 선의 높이
val minHeight = minOf(height[left], height[right])
// 현재 넓이 계산
val currentArea = width * minHeight
// 최대 넓이 갱신
maxArea = maxOf(maxArea, currentArea)
// 더 짧은 선을 가리키는 포인터 이동
if (height[left] < height[right]) {
left++
} else {
right--
}
}
return maxArea
}
다음은 배열의 원소의 값을 높이, 배열의 두 원소의 인덱스 차이를 너비라고 할 때 최대 넓이를 구하는 구현 예이다.
연결 리스트 자료 구조에서 두 포인터를 동일한 시작점에서 시작하여 서로 같은 방향으로 이동시키되 서로 다른 속도로 이동시켜 특정 시점에 서로 만나도록 하는 구현 예는 다음과 같다.
// 연결 리스트 노드 클래스
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