[알고리즘] 투포인터 알고리즘 (Two-Pointers)

Two-Pointers Algorithm

 

두 개의 포인터로 특정 조건의 목표를 탐색하자

 

 

투포인터 알고리즘은 동작원리가 간단하며 배열에 두개의 위치값 = 투포인터(start,end)로 특정 값을 탐색할 수 있는 알고리즘이다.

 

좀더 길게 이야기하면, 배열 또는 리스트와 같은 선형 데이터 구조에서 특정한 조건을 만족하는 부분 구간이나 원소들을 찾는 데에 유용한 알고리즘이다. 이름에서 유추하듯 두 개의 포인터(Index)를 조작하여 원하는 값을 얻어낸다.

 

투포인터 알고리즘은 두 번의 탐색을 두 개의 포인터로 대처하기 때문에 시간복잡도가 O(N²)이 아닌 O(N)이된다.

 

투 포인터 알고리즘의 주요 사용법은 크게 2가지로 나뉜다.

1. 두 개의 포인터를 배열의 양 끝에서 시작해서 서로 다가가며 움직이는 것
2. 두 개의 포인터를 배열의 같은 시작점에서 각 포인터가 조건에 의해 따로 움직이는 것
   • 배열이 1개이냐 2개이냐에 따라 사용법이 조금 달라진다.

출처 : https://benn.tistory.com/9

 

 

---

예제

배열의 같은 시작점에서 움직이는 것

목표 : 배열에서 순차적으로 연결된 원소들의 합이 5가될 수 있는 조합을 모두 찾아라

using System;

public class HelloWorld
{
    public static void Main(string[] args)
    {
        int[] array = new int[] { -1, 0, 1, 1, 1, 5, 5, 4 };
        int[] array2 = new int[] { 5, 0, 1, 0, 4, 5, 1, 4, 5 };
        int[] array3 = new int[] { 2, 3, 1, 0, 3, 1, 4, 5, 1, 0, 3, 1, 4, 5 };
        
        Console.WriteLine("Result1 : " + TwoPointer(array, 5));
        Console.WriteLine("Result2 : " + TwoPointer(array2, 5));
        Console.WriteLine("Result3 : " + TwoPointer(array3, 4));
    }
    
    private static int TwoPointer(int[] array, int target) {
        int start = 0;
        int end = 0;
        int sum = array[0];
        int result = 0;
        
        while(start < array.Length && end < array.Length) {
            Console.WriteLine("Sum : " + sum + ", Start : " + start + ", End : " + end);
            
            if (sum == target) {
                result++;
                
                if (end != start) {
                    sum -= array[start++]; 
                } 
                else {
                    if (++end < array.Length)
                        sum += array[end];
                }
                
                continue;
            }
            
            if (sum > target) {
                sum -= array[start++]; 
            } 
            else if (sum < target) {
                if (end + 1 < array.Length)
                    sum += array[++end];
            }
        }
        
        return result;
    }
}

Array : [-1, 0, 1, 1, 1, 5, 5, 4]
Sum : -1, Start : 0, End : 0
Sum : -1, Start : 0, End : 1
Sum : 0, Start : 0, End : 2
Sum : 1, Start : 0, End : 3
Sum : 2, Start : 0, End : 4
Sum : 7, Start : 0, End : 5
Sum : 8, Start : 1, End : 5
Sum : 8, Start : 2, End : 5
Sum : 7, Start : 3, End : 5
Sum : 6, Start : 4, End : 5
Sum : 5, Start : 5, End : 5
Sum : 10, Start : 5, End : 6
Sum : 5, Start : 6, End : 6
Sum : 9, Start : 6, End : 7
Sum : 4, Start : 7, End : 7
Result1 : 2

Array : [5, 0, 1, 0, 4, 5, 1, 4, 5]
Sum : 5, Start : 0, End : 0
Sum : 5, Start : 0, End : 1
Sum : 0, Start : 1, End : 1
Sum : 1, Start : 1, End : 2
Sum : 1, Start : 1, End : 3
Sum : 5, Start : 1, End : 4
Sum : 5, Start : 2, End : 4
Sum : 4, Start : 3, End : 4
Sum : 9, Start : 3, End : 5
Sum : 9, Start : 4, End : 5
Sum : 5, Start : 5, End : 5
Sum : 6, Start : 5, End : 6
Sum : 1, Start : 6, End : 6
Sum : 5, Start : 6, End : 7
Sum : 4, Start : 7, End : 7
Sum : 9, Start : 7, End : 8
Sum : 5, Start : 8, End : 8
Result2 : 7

Array : [2, 3, 1, 0, 3, 1, 4, 5, 1, 0, 3, 1, 4, 5]
Sum : 2, Start : 0, End : 0
Sum : 5, Start : 0, End : 1
Sum : 3, Start : 1, End : 1
Sum : 4, Start : 1, End : 2
Sum : 1, Start : 2, End : 2
Sum : 1, Start : 2, End : 3
Sum : 4, Start : 2, End : 4
Sum : 3, Start : 3, End : 4
Sum : 4, Start : 3, End : 5
Sum : 4, Start : 4, End : 5
Sum : 1, Start : 5, End : 5
Sum : 5, Start : 5, End : 6
Sum : 4, Start : 6, End : 6
Sum : 9, Start : 6, End : 7
Sum : 5, Start : 7, End : 7
Sum : 0, Start : 8, End : 7
Sum : 1, Start : 8, End : 8
Sum : 1, Start : 8, End : 9
Sum : 4, Start : 8, End : 10
Sum : 3, Start : 9, End : 10
Sum : 4, Start : 9, End : 11
Sum : 4, Start : 10, End : 11
Sum : 1, Start : 11, End : 11
Sum : 5, Start : 11, End : 12
Sum : 4, Start : 12, End : 12
Sum : 9, Start : 12, End : 13
Sum : 5, Start : 13, End : 13
Result3 : 9

 

다른 분들일 작성하신 코드도 살펴보았다.

 

 

 

배열의 다른 방향에서 시작하여 움직이는 것

하나의 배열로 실행

목표 : 배열에서 원소의 합이 목표값 이하가 될 수 있는 조합을 모두 찾아라.

using System;

public class HelloWorld
{
    public static void Main(string[] args)
    {
        int[] array = new int[] { -1, 0, 1, 1, 1, 5, 5, 4 }; // -1, 0, 1, 1, 1, 4, 5, 5
        int[] array2 = new int[] { 5, 0, 1, 0, 4, 5, 1, 4, 5 }; // 0, 0, 1, 1, 4, 4, 5, 5, 5
        int[] array3 = new int[] { 2, 3, 1, 0, 3, 1, 4, 5, 1, 0, 3, 1, 4, 5 }; // 0, 0, 1, 1, 1, 1, 2, 3, 3, 3, 4, 4, 5, 5
        int[] array4 = new int[] { 1, 2, 3, 4, 2, 5, 3, 1, 1, 2 }; // 1, 1, 1, 2, 2, 2, 3, 3, 4, 5
        
        Console.WriteLine("Result1 : " + TwoPointer(array, 4));
        Console.WriteLine("Result2 : " + TwoPointer(array2, 4));
        Console.WriteLine("Result3 : " + TwoPointer(array3, 3));
        Console.WriteLine("Result3 : " + TwoPointer(array4, 3));
    }
    
    private static int TwoPointer(int[] array, int limit){
        int start = 0;
        int end = array.Length - 1;
        int sum = 0;
        int result = array.Length;
        
        Array.Sort(array);
        
        while (start != end && start <= end) {
            sum = array[start] + array[end];
            
            if (sum > limit) {
                end--;
            } else {
                result--;
                start++;
                end--;
            }
        }
        
        return result;
    }
}

Original : -1, 0, 1, 1, 1, 5, 5, 4
Sorted : -1, 0, 1, 1, 1, 4, 5, 5
Sum : 4, Start : 0, End : 7
Sum : 5, Start : 1, End : 6
Sum : 4, Start : 1, End : 5
Sum : 2, Start : 2, End : 4
Result1 : 5

Original : 5, 0, 1, 0, 4, 5, 1, 4, 5
Sorted : 0, 0, 1, 1, 4, 4, 5, 5, 5
Sum : 5, Start : 0, End : 8
Sum : 5, Start : 0, End : 7
Sum : 5, Start : 0, End : 6
Sum : 4, Start : 0, End : 5
Sum : 4, Start : 1, End : 4
Sum : 2, Start : 2, End : 3
Result2 : 6

Original : 2, 3, 1, 0, 3, 1, 4, 5, 1, 0, 3, 1, 4, 5
Sorted : 0, 0, 1, 1, 1, 1, 2, 3, 3, 3, 4, 4, 5, 5
Sum : 5, Start : 0, End : 13
Sum : 5, Start : 0, End : 12
Sum : 4, Start : 0, End : 11
Sum : 4, Start : 0, End : 10
Sum : 3, Start : 0, End : 9
Sum : 3, Start : 1, End : 8
Sum : 4, Start : 2, End : 7
Sum : 3, Start : 2, End : 6
Sum : 2, Start : 3, End : 5
Result3 : 10

Original : 1, 2, 3, 4, 2, 5, 3, 1, 1, 2
Sorted : 1, 1, 1, 2, 2, 2, 3, 3, 4, 5
Sum : 6, Start : 0, End : 9
Sum : 5, Start : 0, End : 8
Sum : 4, Start : 0, End : 7
Sum : 4, Start : 0, End : 6
Sum : 3, Start : 0, End : 5
Sum : 3, Start : 1, End : 4
Sum : 3, Start : 2, End : 3
Result3 : 7

 

 

 

 

---

참고자료

 

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

 

투 포인터 알고리즘 - 1. 같은 방향

 

투 포인터 알고리즘 - 2. 다른 방향(배열 1개)

 

투 포인터 알고리즘 - 2. 다른 방향(배열 2개)