알고리즘 - 투 포인터(Two Pointer) / 슬라이딩 윈도우(Sliding Window)

 

 

 

 

 

투 포인터란?

 

 

• 투 포인터 알고리즘은 배열이나 리스트에서 사용할 수 있는 탐색 기법이다.
• 주로 정렬된 배열이나 리스트에서 연속적인 구간에서 합이나 원소를 찾아내는데 아주 유용한 알고리즘이다.
• 특정한 두 원소의 합을 구한다고 가정하면 완전 탐색의 경우에는 O(n²)의 시간 복잡도가 발생하지만 투 포인터로 이를 해결하면 O(n)의 시간 복잡도가 발생한다.

 

투 포인터의 기본 개념

 

• 투 포인터는 제목과 비슷하게 배열의 양 끝에 두개의 포인터를 이용하는 기법이다.
• 좌우 의 포인터는 양 끝에서 시작해서 특정 원소를 찾을때 까지 가운데로 이동하며 진행한다.
• 배열이나 리스트의 요소가 정렬 되어 있어야 사용이 가능하다.

 

투 포인터 사용 예시

 

배열의 여러 숫자 원소가 담겨있고 해당 원소 중 두 수의 합과 특정한 숫자가 일치하는 경우를 찾는 문제를 가정해보자.

 

 

static void Main(string[] args)
{
	int[] nums = { 1, 2, 3, 4, 6, 9, 10 };
	int target = 8;
}

 

 

우리는 nums 배열에 들어 있는 원소 중 두 수를 더해서 8이 나오는 원소의 인덱스를 찾아야 한다.

 

(1)

 

배열 양 끝에 다음과 같이 두개의 포인터를 만들어 준 뒤 양 포인터의 합이 target과 일치하는지 하나씩 검사하는 원리로 동작한다.

 

만약 해당 포인터의 원소 값 합이 목표하는 숫자보다 작다면 왼쪽의 포인터를 오른쪽으로 이동시키고,

 

원소 값 합이 목표하는 숫자보다 크다면 오른쪽의 포인터를 왼쪽으로 이동시킨다.

 

 

 

현재 타겟 넘버는 8이고, 각 원소의 합은 11이니 원소 값 합이 더 크기 때문에 오른쪽의 포인터를 왼쪽으로 이동시키고 다시 비교한다.

 

 

(2)

 

타겟 넘버는 8이고, 원소의 합은 아직 10이기 때문에 우측 포인터를 다시 왼쪽으로 이동시킨다. 

 

 

(3)

 

타겟 넘버는 8이고, 원소의 합은 7이기 때문에 타겟 넘버보다 합이 작다.

 

따라서 좌측 포인터를 우측으로 이동시킨다. 

 

(4)

 

타겟 넘버 8과 두 원소의 합이 8로 일치하기 때문에 반복을 종료하고 해당 포인터의 인덱스를 반환하면 투 포인터가 종료된다.

 

 

 

위 과정을 코드로 표현하면 다음과 같다.

 

static void Main(string[] args)
{
    Two_Pointer twoPointer = new Two_Pointer();

    int[] nums = { 1, 2, 3, 4, 6, 9, 10 };
    int target = 8;

    int[] result = twoPointer.TwoElementSum(nums, target);

    if (result != null)
    {
        Console.WriteLine($"{result[0] + 1 }번째 수, {result[1] + 1} 번째 수 의 합이 타겟 값 입니다.");
    }
    else
    {
        Console.WriteLine("타겟 합을 이루는 두 수를 찾을 수 없습니다.");
    }
}

class Two_Pointer
{
    public int[] TwoElementSum(int[] nums, int target)
    {
        int left = 0;
        int right = nums.Length - 1;

        while (left < right)
        {
            int sum = nums[left] + nums[right];

            if (sum == target)
            {
                // 두 수의 인덱스를 반환
                return new int[] { left, right };
            }
            else if (sum < target)
            {
                // 합이 타겟보다 작으면 왼쪽 포인터를 오른쪽으로 이동
                left++;
            }
            else
            {
                // 합이 타겟보다 크면 오른쪽 포인터를 왼쪽으로 이동
                right--;
            }
        }

        return null; // 합이 타겟이 되는 두 수가 없을 때
    }
}

 

 

 

 

 

 

 

 

 

---

 

 

슬라이딩 윈도우란?

 

• 슬라이딩 윈도우는 배열이나 리스트 위에 고정된 크기의 창(윈도우)를 부여하고 그 윈도우를 이동시키면서 원소들을 비교하는 알고리즘이다.
• 윈도우를 이동할 때 윈도우 바깥에 있는 원소는 제거하고 새로 들어온 원소는 추가하는 방식으로 동작한다.
• 새로운 계산을 매번 반복하는 것이 아니라 변경된 요소만 계산하기 때문에 계산량을 줄여 시간 복잡도를 낮출 수 있다.
• 슬라이딩 윈도우는 대부분의 경우 O(n)의 시간복잡도를 가진다.
• 주로 연속적인 구간에서 최대/최소 합을 구하거나 연속적인 부분 타겟과 일치하는 특정 원소를 찾을 때 유용하다.

 

 

슬라이딩 윈도우 사용 예시

 

 

주어진 배열 arr에서 길이가 k인 연속된 구간의 합이 가장 큰 경우와 가장 작은 경우를 구하는 문제를 풀어보자.

 

 

static void Main(string[] args)
{
	int[] nums = { 7, 3, 28, 4, -3, 12, 10, 21 };
	int target = 3;
}

 

 

 

윈도우의 크기는 3으로 제한하고 3칸짜리 윈도우에서 원소의 합이 가장 큰 경우와 작은 경우를 구해야 한다.

 

(1)

 

 

해당 원소에 윈도우를 끼워 넣고 한칸씩 이동시키면서 원소의 합을 구한다.

 

 

(2)

 

현재 윈도우의 합은 38이고 해당 값을 저장한다.

 

 

(3)

 

 

윈도우를 이동시키고 첫번째 원소였던 7을 38에서 빼주고 새로 추가된 원소 4를 더해준다.

현재의 합은 35 이고, 앞의 38과 비교해서 최대 값에 해당하는 변수에 더 큰 합이었던 38을 넣어주고 현재 윈도우는 최소 값에 넣어준다.

 

(4)

 

 

해당 과정을 끝까지 반복해 주면 최대 합과 최소 합을 구할 수 있다.

 

 

위 과정을 코드로 표현하면 다음과 같다.

 

 static void Main(string[] args)
 {
     int[] nums = { 7, 3, 28, 4, -3, 12, 10, 21 };
     int target = 3;

     twoPointer.FindMaxMinSum(nums, target);
 }


public void FindMaxMinSum(int[] arr, int k)
{
    if (arr.Length < k) 
        return;  // 배열의 길이가 k보다 작으면 의미가 없음

    int windowSum = 0;

    // 첫 번째 윈도우의 합 계산
    for (int i = 0; i < k; i++)
    {
        windowSum += arr[i];
    }

    // 초기 최대/최소 합은 첫 번째 윈도우의 합으로 설정
    int maxSum = windowSum;
    int minSum = windowSum;

    // 두번째 윈도우 부터 슬라이딩 윈도우 적용
    for (int i = k; i < arr.Length; i++)
    {
        // 새로 들어온 숫자를 더하고, 빠져나간 숫자를 뺌
        windowSum += arr[i] - arr[i - k];

        // 최대 합과 최소 합 갱신
        maxSum = Math.Max(maxSum, windowSum);
        minSum = Math.Min(minSum, windowSum);
    }

    // 결과 출력
    Console.WriteLine($"최대 합: {maxSum}");
    Console.WriteLine($"최소 합: {minSum}");
}

 

 

 

 

 

 

 

 

 

 

 

 

사진 출처 :
https://www.linkedin.com/pulse/two-pointer-method-vasily-kalmykov-cimle/

https://medium.com/@rishu__2701/mastering-sliding-window-techniques-48f819194fd7