안녕하세요! 오늘은 슬라이딩 윈도우(Sliding Window)라는 알고리즘 기법에 대해 알아보겠습니다. 이 기법은 주로 연속적인 데이터에서 부분 합계나 최대/최솟값을 찾는 문제에 적합합니다. 또한, 이 기법은 시간 복잡도를 크게 줄여주기 때문에 코딩 테스트에서 자주 출제되는 주제 중 하나입니다.
슬라이딩 윈도우란?
슬라이딩 윈도우는 배열이나 문자열과 같은 선형 데이터 구조에서 특정 크기의 윈도우를 만들어 그 윈도우의 내용을 조작하는 기법입니다. 이 기법은 주로 다음과 같은 상황에서 유용하게 사용됩니다:
- 연속된 원소의 합 또는 평균을 계산해야 할 때
- 특정 조건을 만족하는 최대/최솟값을 찾아야 할 때
- 각종 최적화 문제에서 정의된 구간 내에서의 값을 찾아야 할 때
문제 설명
문제: 최대 길이의 부분 배열
정수 배열 nums와 정수 k가 주어졌을 때, 합이 k 이하인 최대 길이의 부분 배열의 길이를 구하세요.
입력 예시
nums = [1, 2, 3, 4, 5]
k = 5출력 예시
2부분 배열 [2, 3] 또는 [1, 2]와 같이 합계가 5 이하인 최대 길이는 2입니다.
문제 풀이 과정
1. 문제 분석
주어진 배열에서 합이 k 이하인 최대 길이의 부분 배열을 찾는 문제입니다. 이 문제는 브루트 포스로 해결할 경우 O(n^2)의 시간 복잡도를 가지므로, 슬라이딩 윈도우 기법을 사용하여 개선할 수 있습니다.
2. 슬라이딩 윈도우 기법 적용
슬라이딩 윈도우 기법은 배열의 시작과 끝을 가리키는 두 개의 포인터를 사용하여 현재 윈도우의 합계를 유지합니다. 윈도우의 크기를 조정하면서 최대 길이를 찾아야 합니다. 기본적인 접근 방법은 다음과 같습니다:
알고리즘
- 두 개의 포인터
start와end를 사용하여 윈도우의 시작과 끝을 가리킵니다. - 포인터
end를 배열의 끝까지 이동시키면서 현재 윈도우의 합을 계산합니다. - 합이
k를 초과할 경우, 포인터start를 오른쪽으로 이동시켜 현재 윈도우의 합을 줄입니다. - 각 경우에 대해 현재 윈도우의 길이를 계산하고 최대 길이를 갱신합니다.
3. 자바 코드 구현
이제 위의 알고리즘을 바탕으로 자바 코드를 작성해 보겠습니다:
public class MaxLengthSubarray {
public static int maxLengthSubarray(int[] nums, int k) {
int start = 0, end = 0;
int maxLength = 0;
int sum = 0;
while (end < nums.length) {
sum += nums[end];
while (sum > k) {
sum -= nums[start];
start++;
}
maxLength = Math.max(maxLength, end - start + 1);
end++;
}
return maxLength;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4, 5};
int k = 5;
System.out.println("최대 길이의 부분 배열: " + maxLengthSubarray(nums, k));
}
}
4. 코드 설명
위의 코드에서는 다음과 같은 작업을 수행합니다:
maxLengthSubarray함수는 입력 배열nums와 정수k를 인자로 받습니다.- 포인터
start와end를 초기화하고,sum변수를 사용하여 현재 윈도우의 합계를 유지합니다. - while 루프에서
end포인터를 이동시키며sum에nums[end]를 추가합니다. - 현재
sum이k를 초과하면start포인터를 오른쪽으로 이동하여sum을 갱신합니다. - 매번 최대 길이를 갱신하며, 최종적으로 최대 길이를 반환합니다.
결론
슬라이딩 윈도우는 코딩 테스트에서 매우 유용한 기법 중 하나입니다. 이 문제를 통해 알고리즘 문제를 보다 효율적으로 해결할 수 있는 방법에 대해 배웠습니다. 이 기법을 활용하면 다양한 문제를 보다 빠르게 해결할 수 있는 가능성이 높아집니다.
이 블로그 포스트가 도움이 되셨다면, 다른 문제들도 한번 시도해 보세요. 더 많은 알고리즘과 문제 해결 기법에 대해 배워보기를 바랍니다!