코딩 테스트 대비: 투 포인터 알고리즘 이해 및 적용 (C#)

안녕하세요, GameLabMaster입니다! 오늘의 코딩 테스트 대비 포스팅에서는 투 포인터 알고리즘(Two Pointer Algorithm)에 대해 알아보겠습니다. 투 포인터 알고리즘은 배열에서 연속된 부분 배열을 탐색하는데 사용되며, 시간 복잡도와 공간 복잡도를 줄이는 데 도움이 됩니다.

 

문제
주어진 정수 배열에서, 합이 특정 값인 연속된 부분 배열을 찾으세요.

 

풀이
투 포인터 알고리즘을 사용하면 이 문제를 효율적으로 해결할 수 있습니다. 먼저, 배열의 시작점을 가리키는 start 포인터와 끝점을 가리키는 end 포인터를 설정합니다. 그 다음, 현재 부분 배열의 합이 주어진 값과 같으면 결과를 반환하고, 현재 부분 배열의 합이 주어진 값보다 작으면 end 포인터를 증가시키며, 현재 부분 배열의 합이 주어진 값보다 크면 start 포인터를 증가시킵니다. 이 과정을 반복하면 원하는 부분 배열을 찾을 수 있습니다.

 

다음은 이 문제를 해결하는 C# 코드입니다.

 

public static int[] FindSubarrayWithSum(int[] arr, int targetSum) {
    int start = 0;
    int end = 0;
    int currentSum = 0;

    while (end < arr.Length) {
        if (currentSum == targetSum) {
            return arr[start..end];
        } else if (currentSum < targetSum) {
            currentSum += arr[end];
            end++;
        } else {
            currentSum -= arr[start];
            start++;
        }
    }

    return new int[0]; // No subarray found
}

 

이제 주어진 배열과 합을 가지고 함수를 호출해보겠습니다.

 

public static void Main(string[] args) {
    int[] arr = { 1, 3, 2, 5, 6, 1, 4, 8 };
    int targetSum = 10;

    int[] subarray = FindSubarrayWithSum(arr, targetSum);
    Console.WriteLine($"Subarray with sum {targetSum}: [{string.Join(", ", subarray)}]");
}

 

이 예제에서는 주어진 배열과 합을 가지고 함수를 호출해봤습니다.

 

public static void Main(string[] args) {
    int[] arr = { 1, 3, 2, 5, 6, 1, 4, 8 };
    int targetSum = 10;

    int[] subarray = FindSubarrayWithSum(arr, targetSum);
    Console.WriteLine($"Subarray with sum {targetSum}: [{string.Join(", ", subarray)}]");
}

 

이 예제에서는 주어진 배열에서 합이 10인 연속된 부분 배열을 찾으려 합니다. 함수를 호출하면 결과로 [2, 5, 3] 또는 [5, 1, 4]와 같은 부분 배열이 반환됩니다.

 

이상으로 오늘의 코딩 테스트 대비 포스팅을 마치겠습니다. 투 포인터 알고리즘은 주로 연속된 부분 배열을 찾는 문제에서 활용되며, 시간 복잡도와 공간 복잡도를 줄이는 데 도움이 됩니다. 다음 포스팅에서는 더 다양한 문제와 알고리즘에 대해 알아보겠습니다. 감사합니다!