코딩테스트 준비 과정에서 알고리즘 문제 풀이 능력은 매우 중요합니다. 이 포스팅에서는 ‘연속 합 구하기’라는 주제로 자바스크립트 코딩테스트 문제를 살펴보겠습니다. 문제를 이해하고 해결하는 과정을 단계별로 설명하겠습니다. 이 과정은 여러분이 복잡한 알고리즘 문제를 해결하는 데 도움을 줄 것입니다.
문제 설명
주어진 배열에서 연속된 숫자들의 합을 계산해야 합니다. 연속된 숫자란 배열에서 인접한 두 요소를 의미하며, 이들의 합을 구할 수 있습니다. 하지만 이 문제는 단순히 두 요소의 합을 구하는 것이 아니라, 모든 가능한 연속된 부분 배열의 합을 구하고, 그 중에서 가장 큰 합을 구하는 것입니다.
입력
- 정수 배열
arr가 주어집니다. (1 ≤ arr.length ≤ 10^5) - 배열의 각 요소는
-10^4 ≤ arr[i] ≤ 10^4의 범위를 가집니다.
출력
모든 연속된 부분 배열의 합 중 가장 큰 값을 반환합니다.
예제
입력: arr = [-2,1,-3,4,-1,2,1,-5,4] 출력: 6 설명: 연속된 배열 [4,-1,2,1]의 합이 6으로, 가장 큰 합입니다.
문제 접근 방식
이 문제를 해결하기 위해 연속된 부분 배열의 합을 효과적으로 계산할 수 있는 알고리즘이 필요합니다. 다음은 이 문제를 해결하기 위해 따라야 할 단계입니다:
1단계: 이해하기
문제의 요구사항을 명확히 이해하고, 어떤 경우에 큰 합이 발생하는지를 분석합니다. 예를 들어, 배열의 모든 요소가 음수일 경우, 그 중에서 가장 큰 값을 반환해야함을 깨닫습니다.
2단계: 알고리즘 선택
이 문제를 해결하기 위해 ‘카데인 알고리즘’을 사용할 것입니다. 카데인 알고리즘은 O(n) 시간 복잡도로 연속된 부분 배열의 최대 합을 구할 수 있는 매우 효율적인 알고리즘입니다. 이 알고리즘은 현재까지의 최대 합을 추적하고, 현재 요소를 포함할 것인지 결정하는 방식으로 작동합니다.
3단계: 알고리즘 구현
이제 카데인 알고리즘을 자바스크립트로 구현해 보겠습니다.
function maxSubArray(arr) {
let maxSoFar = arr[0]; // 모든 요소의 합 중 최댓값
let maxEndingHere = arr[0]; // 현재 위치에서의 최댓값
for (let i = 1; i < arr.length; i++) {
maxEndingHere = Math.max(arr[i], maxEndingHere + arr[i]); // 현재 값과 이전 합을 비교
maxSoFar = Math.max(maxSoFar, maxEndingHere); // 최대 합 업데이트
}
return maxSoFar;
}
4단계: 테스트
함수를 구현한 후에는 다양한 입력값으로 테스트해야 합니다. 아래는 몇 가지 테스트 케이스입니다:
console.log(maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4])); // 6
console.log(maxSubArray([1])); // 1
console.log(maxSubArray([5, 4, -1, 7, 8])); // 23
console.log(maxSubArray([-1, -2, -3, -4])); // -1
console.log(maxSubArray([-5, -2, -3, -4, -1])); // -1
결론
이번 포스팅에서는 ‘연속 합 구하기’ 문제를 카데인 알고리즘을 이용해 해결했습니다. 이와 같은 문제는 코딩테스트에서 자주 출제되므로, 충분한 연습이 필요합니다. 알고리즘을 이해하는 것은 물론, 다양한 테스터 케이스로 정확성을 검증하는 것이 중요합니다. 앞으로도 다양한 알고리즘 문제를 다루며 여러분의 코딩 능력을 향상시키기 위한 지속적인 노력이 필요합니다.