문제 설명
주어진 정수 배열에서 연속적으로 더해지는 부분 배열의 합을 구하는 문제입니다.
이 문제는 알고리즘 문제 풀이에서 자주 등장하는 유형으로, 면접이나 코딩 테스트에서
응용될 수 있습니다.
문제 정의:
정수로 이루어진 배열 nums가 주어질 때, 다음의 두 가지 질문에 답하십시오:
- 주어진 배열의 모든 연속 부분 배열의 합을 계산하여 반환하십시오.
- 가장 큰 연속 부분 배열의 합을 계산하여 반환하십시오.
문제 해결 접근법
이 문제를 해결하기 위해, 우리는 특정 알고리즘을 사용할 수 있습니다.
특히, “Kadane의 알고리즘”을 이용하면 가장 큰 연속 부분 배열의 합을
효율적으로 구할 수 있습니다.
Kadane의 알고리즘은 동적 프로그래밍의 일종으로, 배열을 한 번만 순회하면서
필요한 값을 메모리에 저장하여 최적의 해를 찾는 방식입니다.
이 알고리즘의 아이디어는 현재까지의 최대 합을 저장하고, 새 요소를 추가하면서
최대 값을 갱신하는 것입니다.
문제 풀이 단계
1단계: 기본 아이디어 구상
연속 부분 배열의 합을 구하기 위해, 먼저 현재 인덱스에서의 최대 합을 계산해야 합니다.
이는 현재 배열 요소와 이전까지의 최대 합을 비교하여 결정됩니다.
2단계: 알고리즘 구현
이제, Java 언어를 사용하여 본 문제를 해결하는 코드를 작성해 보겠습니다.
아래의 코드는 해당 알고리즘을 구현한 예시입니다.
public class ContinuousSum {
public static void main(String[] args) {
int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
System.out.println("가장 큰 연속 부분 배열의 합: " + maxSubArray(nums));
}
public static int maxSubArray(int[] nums) {
int maxSoFar = nums[0];
int maxEndingHere = nums[0];
for (int i = 1; i < nums.length; i++) {
maxEndingHere = Math.max(nums[i], maxEndingHere + nums[i]);
maxSoFar = Math.max(maxSoFar, maxEndingHere);
}
return maxSoFar;
}
}
3단계: 복잡도 분석
위의 알고리즘은 O(n) 시간 복잡도를 가지며, 공간 복잡도는 O(1)입니다.
이는 배열을 한 번만 순회하기 때문에 시간 효율성이 매우 좋습니다.
예제 및 테스트
제공된 알고리즘을 테스트하기 위해 몇 가지 예제를 사용하여 결과를 검증할 수 있습니다.
아래는 다양한 입력에 대한 예제입니다.
- 입력: [-2, 1, -3, 4, -1, 2, 1, -5, 4] → 출력: 6
- 입력: [1] → 출력: 1
- 입력: [5, 4, -1, 7, 8] → 출력: 23
- 입력: [-1, -2, -3] → 출력: -1
결론
오늘은 연속적으로 합을 구하는 문제를 Kadane의 알고리즘을 이용해 해결해 보았습니다.
알고리즘 문제 풀이에서 자주 접할 수 있는 유형이며,
효율적인 방법을 통해 문제를 해결하는 것은 매우 중요합니다.
다양한 문제를 접하면서 알고리즘과 데이터 구조에 대한 이해도를 높여보세요.