코딩 테스트 대비: 슬라이딩 윈도우 기법 - 연속된 구간의 최대 합 구하기 (C#)

안녕하세요, GameLabMaster입니다! 이번 코딩 테스트 대비 포스팅에서는 슬라이딩 윈도우(Sliding Window) 기법을 활용한 문제 풀이에 대해 알아보겠습니다.

 

문제

길이가 N인 배열 A가 주어집니다. 이 배열에서 연속된 K개의 원소의 합이 최대가 되는 구간의 합을 찾는 프로그램을 작성하세요.

 

입력

• 배열의 길이 N (1 ≤ N ≤ 10^5)
• 연속된 원소의 개수 K (1 ≤ K ≤ N)
• N개의 정수 A1, A2, ... , AN (|Ai| ≤ 10^4)

출력

• 연속된 K개의 원소의 합이 최대가 되는 구간의 합

풀이

이 문제는 슬라이딩 윈도우 기법을 사용하여 해결할 수 있습니다. 슬라이딩 윈도우 기법은 고정된 길이의 구간(윈도우)을 배열에 슬라이딩 시키며 각 구간에 대한 정보를 구하는 방법입니다.

 

다음은 C#으로 작성한 연속된 구간의 최대 합을 구하는 코드입니다.

 

using System;
using System.Linq;

class Program {
    static void Main(string[] args) {
        int n = int.Parse(Console.ReadLine());
        int k = int.Parse(Console.ReadLine());
        int[] arr = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();

        int windowSum = 0;
        int maxSum = int.MinValue;

        for (int i = 0; i < k; i++) {
            windowSum += arr[i];
        }
        maxSum = windowSum;

        for (int i = k; i < n; i++) {
            windowSum += arr[i] - arr[i - k];
            maxSum = Math.Max(maxSum, windowSum);
        }

        Console.WriteLine(maxSum);
    }
}

 

이 코드는 먼저 K개의 원소의 합을 구한 후, 슬라이딩 윈도우 기법을 사용하여 각 구간의 합을 구하고 최대 합을 찾습니다.

 

이렇게 슬라이딩 윈도우 기법을 활용하여 문제를 해결할 수 있습니다. 이 기법을 익히면 다양한 구간 관련 문제를 쉽게 해결할 수 있으므로, 코딩 테스트 대비에 도움이 될 것입니다. 다음 포스팅에서는 다른 슬라이딩 윈도우 문제에 대해 알아보겠습니다. 이 기법을 활용한 문제들은 시간 복잡도를 줄여 효율적인 코드를 작성할 수 있게 도와주므로 꼭 기억해두시길 바랍니다. 코딩 테스트 준비에 화이팅하세요