코딩테스트나 알고리즘 문제풀이를 준비하면서, 다양한 유형의 문제에 대한 이해와 접근 방식을 익히는 것이 중요합니다. 오늘은 연속 합 구하기 문제에 대해 깊이 있게 알아보도록 하겠습니다.
문제 설명
주어진 정수 배열에서 연속된 요소들의 합을 계산하여, 특정 기준에 도달하는 가장 짧은 연속 부분 배열을 찾는 문제를 살펴보겠습니다.
문제 정의
문제: 연속 합 구하기
주어진 정수 배열 nums와 정수 target가 주어질 때,
target 이상의 합을 가지는 가장 짧은 연속 부분 배열의 길이를 반환합니다.
만약 그 조건을 만족하는 부분 배열이 없다면 0을 반환합니다.
입력 예시:
nums = [2,3,1,2,4,3]
target = 7
출력 예시:
2 (부분 배열 [4,3]의 길이)
문제 풀이 접근 방법
이 문제를 해결하기 위해 두 가지 주요 접근 방법을 사용할 수 있습니다: 브루트포스(완전 탐색)와 투 포인터(슬라이딩 윈도우) 방법입니다. 여기서는 효율적인 해결을 위해 투 포인터 방법을 사용하겠습니다.
투 포인터 접근 방법
투 포인터 접근 방법은 배열을 탐색하면서 두 개의 포인터(왼쪽, 오른쪽)를 사용하여 원하는 조건을 만족하는 부분 배열을 찾아내는 방식입니다. 이 방법의 장점은 시간 복잡도가 O(n)으로 효율적이라는 점입니다.
단계별 풀이
-
초기화: 두 개의 포인터를 초기화합니다. 왼쪽 포인터
left는 0으로, 오른쪽 포인터right는 0으로 설정합니다. 또한, 현재 합currentSum을 0으로 설정하고, 최소 길이minLength를 무한대로 초기화합니다. -
조건 검사:
right포인터를 이용해 배열을 순회하면서currentSum에nums[right]를 더합니다. 그 후,currentSum이target이상인지 확인합니다. -
부분 배열 조정: 만약
currentSum이target보다 크거나 같다면, 최소 길이를 업데이트하고left포인터를 증가시키며currentSum에서nums[left]를 빼 줍니다. 이렇게 함으로써 가능한 짧은 부분 배열을 찾습니다. -
종료 조건:
right포인터가 배열의 끝에 도달할 때까지 이 과정을 반복합니다.
함수 구현
이제 C# 코드를 통해 위의 논리를 실제로 구현해보겠습니다.
using System;
public class Solution {
public int MinSubArrayLen(int target, int[] nums) {
int left = 0;
int currentSum = 0;
int minLength = int.MaxValue;
for (int right = 0; right < nums.Length; right++) {
currentSum += nums[right];
while (currentSum >= target) {
minLength = Math.Min(minLength, right - left + 1);
currentSum -= nums[left];
left++;
}
}
return minLength == int.MaxValue ? 0 : minLength;
}
}
코드 설명
위의 C# 코드는 다음과 같은 방식으로 작동합니다:
- 초기 변수 설정:
left와currentSum,minLength를 초기화합니다. - 배열 순회:
right변수를 통해 배열을 순회하며 현재 요소를currentSum에 추가합니다. - 조건 검사:
currentSum이target이상인 경우,minLength를 업데이트하고left포인터를 증가시키며currentSum에서nums[left]를 빼줍니다. - 결과 반환: 최종적으로
minLength가 업데이트되지 않았다면 0을 반환하고, 그렇지 않으면 찾은 최소 길이를 반환합니다.
예제 테스트 케이스
이제 이 함수를 테스트하기 위한 몇 가지 예제 테스트 케이스를 작성해 보겠습니다.
public static void Main(string[] args) {
Solution sol = new Solution();
Console.WriteLine(sol.MinSubArrayLen(7, new int[] { 2, 3, 1, 2, 4, 3 })); // 출력: 2
Console.WriteLine(sol.MinSubArrayLen(4, new int[] { 1, 4, 4 })); // 출력: 1
Console.WriteLine(sol.MinSubArrayLen(11, new int[] { 1, 1, 1, 1, 1, 1 })); // 출력: 0
Console.WriteLine(sol.MinSubArrayLen(8, new int[] { 2, 3, 1, 2, 4, 3 })); // 출력: 2
}
결론
이번 강좌에서는 연속 합 구하기 문제를 통해 투 포인터를 활용한 문제 해결 접근 방법을 익혔습니다. 알고리즘 문제를 해결하기 위해서는 문제의 성격을 정확히 이해하고, 적절한 접근 방법을 선택하는 것이 중요합니다. 실전에서는 다양한 문제를 풀어보며 경험을 쌓고, 여러 알고리즘을 친숙하게 다룰 수 있도록 지속적으로 연습하는 것이 좋습니다.
여러분도 다양한 문제를 접하고 풀어보면서 알고리즘 감각을 키워보세요!