[알고리즘] 투포인터(Two_Pointer) 알고리즘

 

투포인터 알고리즘이란

리스트에 순차적으로 접근해야 할 때 두 개의 점의 위치를 기록하면서 처리하는 알고리즘입니다.

두 개의 포인터를 사용하여 특정 조건을 만족하는 부분 구간을 효율적으로 탐색하는데 배열이나 리스트가 정렬되어 있을 때 사용합니다.

 

 

투포인터의 동작 방식과 구현

투포인터 알고리즘의 대표 문제로서 구간합 찾는 문제가 있습니다.

 

ex) 아래와 같은 배열에서 구간합이 9인 구간을 찾아주세요

1 2 5 3 7 2 4 3 2

 

해당 문제는 완전탐색을 이용하여 시작구간 i 와 i+1 시작하는 j를 사용하여 찾을 수 있지만 시간복잡도는 O(N^2) 임으로 데이터가 클수록 시간이 오래걸립니다 -> 이때 사용하면 좋은것이 투포인터 알고리즘입니다.

 

 

https://sehun5515.tistory.com/62

 

start 와 end 는 첫번째 원소를 가르킵니다. 현재 내가 원하는 값은 9 이지만 start 부터 end 까지의 합은 1 임으로 end를 한칸뒤로 보냅니다.

 

 

 

start 부터 end 까지의 합은 3 임으로 9보다 작습니다 따라서 end를 한 칸 뒤로 보냅니다. 위의 과정 반복을 통해 end가 5를 가르킬 때도 8이 됨으로 3을 가르킬떄 까지 옮깁니다.

 

 

 

start 부터 end 까지 더하면 11임으로 우리가 원하는 9보다 큽니다 따라서 start를 한칸 뒤로 보냅니다.

start가 2를 가르키고 있지만 start 부터 end 까지의 합은 10(2 + 5 + 3)임으로 9보다 큽니다 따라서 start를 한칸 뒤로 옮깁니다.

 

 

이때 sum의 값은 9보다 작음으로 end를 뒤로 옮깁니다. 그후 sum은 15가 됨으로 start를 뒤로 옮깁니다 -> sum의 값은 10

그 후 원하는값 9 보다 큼으로 3을 뺀후 start 와 end는 7을 가르키고 있습니다.

구간합 7은 9보다 작음으로 end를 뒤로 한칸 움직여 sum 9가 됩니다.

이제 우리가 찾는 값이 되었음으로 해당 구간을 답으로 출력합니다.

 

 

 

아래의 코드는 Swift로 투포인터 알고리즘 구현했을때 코드입니다.

import Foundation

//백준 1197번 https://www.acmicpc.net/problem/1197

var input = readLine()!.split(separator: " ").map { Int(String($0))! }
var target = input[1]
var arr : [Int] = readLine()!.split(separator: " ").map { Int(String($0))! }

var startIdx = 0
var endIdx = 0
var answer = 0
var sum = arr[0]

while startIdx < arr.count , endIdx < arr.count {

    if sum == target {
        startIdx += 1
        answer += 1
        if startIdx < arr.count {
            sum += arr[startIdx]
        }
    }else if sum > target {
        sum -= arr[endIdx]
        endIdx += 1
    }else{
        startIdx += 1
        if startIdx < arr.count {
            sum += arr[startIdx]
        }
    }
   
}

print(answer)

 

 

 

투포인터의 시간복잡도

start 가 배열끝까지 도달하는 시간복잡도 O(N) 과 end 가 배열끝까지 도달하는 시간복잡도 O(N)

이 둘을 더하여도 시간복잡도는 O(N) 입니다.

 

 

 

왜 사용해야할까 or 나만의 고민

리스트에서 다중 반복문이 사용되어야 할때 특정 조건을 만족하는 부분 구간을 효율적으로 탐색을 원할때 사용하는 알고리즘입니다. 

시간복잡도가 O(N) 이기 때문에 매우 빠른속도로 작동합니다.