[Leetcode] 53. Maximum Subarray (JS)

출처

53. Maximum Subarray

문제

포스팅이 오래되신 것을 보시면 아시겠지만, 제 뇌의 한계를 5일 동안 시험에 들게 한 아주 무지막지한 알고리즘이었습니다. 저번 포스팅 이후에 자신감이 상승해서 이번 문제를 마주했지만, 언제나 그렇듯이 약소한 행복 뒤엔 엄청난 고난이 오는 법이었나봅니다.

subarray의 배열의 길이가 1부터 커지면서 최대값이 달라지고, 이에 따라 subarray의 최대값을 구하는 알고리즘 문제였습니다.

같은 배열의 길이로써의 최대값은 구할 수 있고, 그리고 재귀함수를 통해서도 구할 수 있겠다 싶었지만 시간 복잡도 부분이 굉장히 걸렸습니다. 그리고 Follow Up에서 O(n)으로 해보고 그것도 했으면, 분할 정복 방식도 해봐라하는 말에 무너지기 시작했습니다.

그래서 나 혼자는 도저히 풀지 못하겠다 싶어서 이번 위코드 사전 스터디 조원분들에게 문제를 물어보기로 했습니다. 그리고 구세주 치헌님께서 동적 프로그래밍(Dynamic Programming)의 방식으로 풀이를 진행해주시면 된다고 알려주셨습니다.

이후에 슬랙을 통해서 다음날까지 정리를 해서 알려주신 덕분에 직접 알고리즘을 하나하나 뜯어보면서 이해를 할 수 있게 되었습니다.

다만, 아직 동적 프로그래밍(Dynamic Programming)이라는 개념에 대해서는 완전한 이해가 되지는 않아서 현재 보고 있는 강의에서 개념을 정립하는 방식으로 공부를 진행하려고 합니다. 무엇보다 치헌님께 깊은 감사를 드리며, 제가 이해한 코드로 설명을 진행하겠습니다.

추가적으로, 해당 사이트를 남겨드리니 동적 프로그래밍에 대해 알고싶은 분은 참고 부탁드립니다.

풀이 코드

코드만 보았을 때에는 굉장히 단순한 코드입니다. 이러한 코드로 저 복잡한 알고리즘을 해결할 수 있다니 놀라울 따름입니다.

동적 프로그래밍은 분할 정복과 비슷한 방식이며, 다만 다른 점은 작은 문제가 중복이 일어나는지 안 일어나는지에 따라 다르다고 합니다. 그래서 피보나치 수열은 이 동적 프로그래밍의 가장 유명한 예시가 됩니다.

1, 1, 2, 3, 5, 8, 13, 21 ...

이처럼 다음 수열값은 앞의 수열과 그 앞앞의 수열의 값을 더한 값이 됩니다. 이러한 작은 반복 구조를 지니기 때문에 동적 프로그래밍 방식으로 풀이가 가능합니다.

제가 이해한 바로 현재 문제에서 반복되는 값은 nums[i]값과 nums[i-1]의 합이 반복이 된다는 점이었습니다. 이어지는 배열 안에서 연결된 두 값의 합이 양수가 아닌 음수라면, 해당 subarray의 최대값은 작아지게 됩니다.

반드시, 연결된 두 값의 합이 음수가 아닌 양수여야만 최대값이 증가하는 패턴을 지니게 됩니다. 그러므로 여기서 현재의 값(nums[i])과 현재의 값 + 이전의 값(nums[i] + nums[i - 1])을 비교하여 현재의 값이 두 값을 더한 값보다 크다면, subarray를 끊어내야하는 것입니다.

for (let i = 1; i < nums.length; i++){
  nums[i] = Math.max(nums[i], nums[i] + nums[i - 1]);
}

그래서 위와 같은 코드를 구현할 수가 있습니다. 아래에 예를 들어서 살펴보시겠습니다.

[10, -4, 3, 1, 5, 6, -35, 12, 21, -1]

위와 같은 배열에서 위의 코드를 진행시켜본다면 어떻게 될까요? 인덱스 0의 값은 필요 없으니 생략을 하기로 하고 1부터 시작하여 배열의 길이만큼 진행하면 됩니다.

그리고 더한 값을 배열의 값으로 바꾸어 추후 그 값에서 최대값을 구하면 되는 방식입니다.

index	0	1	2	3	4	5	6	7	8	9
list	10	-4	3	1	5	6	-35	12	21	-1
nums[i]	10	6	9	10	15	21	-14	12	33	32

원래 있던 배열이 위의 반복문을 통해 배열의 값이 바뀌었음을 확인할 수 있습니다. 이 배열은 어떻게 나왔는지는 이제 여러 번 말씀드렸기 때문에 추가적으로 이야기 드리지는 않겠습니다.

[10, 6, 9, 10, 15, 21, -14, 12, 33, 32]

결국, 중요한 것은 index 7번에서 실제로 nums[i] = 12, nums[i] + nums[i - 1] = -2가 됩니다. 두 값을 비교하였을 때, nums[i] 값이 크기 때문에 지금까지와는 달리 초기화가 되어 nums[i]가 배열의 값으로 들어가게 됩니다.

이후에도 현재와 동일하게 진행되면서, 위 배열의 최대값인 33이 답이 되는 것입니다. 오랫동안 고민한 문제를 통해 동적 프로그래밍이라는 개념에 대해 알아볼 수 있었습니다.

재귀 함수보다 시간 복잡도면에서 우월하기 때문에 잘 알아두면 좋습니다. 혹시 위 문제와 관련하여 추가적으로 얘기해주실 부분이 있다면 언제든지 댓글로 달아주시기 바랍니다! 😆

실행 결과