<div id="readability-page-1" class="page"><section>LeetCode를 시간이 날때마다 풀고 있습니다.
워낙 알고리즘에는 잼병이기도 하고, 생각의 폭을 넓히기 위해서 푸는데요.
easy에 있는 <code>Maximum subarray</code> 를 풀게 되었습니다.처음에는 효율이 굉장히 낮게 for 문 여러개를 돌려서 풀었는데요 (거의 3중 포문 😭)
시간이 오버되어서 울며 겨자먹기로 방법을 검색해보았습니다. 알고보니 굉장히 유명한 문제이고, 가장 효율적인 방법이 소개되어있어
이해한 것을 공유합니다. <h2>Maximum Subarray - 최대 부분합 문제?</h2>최대 부분합 문제는 유명한 알고리즘 문제 중 하나입니다. 배열이 있을 때, 연속하는 부분집합을 구할 수 있는데요.
그 부분집합의 합 중 가장 큰 값을 구하는 문제입니다.
 
 <img alt="img" title="img" src="https://juneyr.dev/static/7194ae1a28579b9c4edd8401205d539d/5a032/1.png" sizes="(max-width: 748px) 100vw, 748px" loading="lazy">
 <h2>최초의 접근법</h2>예를 들어 [-2, -3 ,4] 는 비연속하는 상태이므로 포함되지 않겠지요?
이런식으로 가능한 경우를 모두 써보면 생각보다 부분집합이 많지는 않습니다. (특히 이 경우는요.)
그래서 저는 모든 부분집합을 구하고 그 합을 매번 비교하는 방식을 처음에 생각했습니다.
 
 <img alt="img" title="img" src="https://juneyr.dev/static/aec619a02e501a149f3677fe02fb906e/5a032/2.png" sizes="(max-width: 748px) 100vw, 748px" loading="lazy">
 
 
 <img alt="img" title="img" src="https://juneyr.dev/static/ee9f9a6f6256421d5235dfd6fc1a89db/5a032/3.png" sizes="(max-width: 748px) 100vw, 748px" loading="lazy">
 
 
 <img alt="img" title="img" src="https://juneyr.dev/static/f921b387197c90b129a88a25932de78a/5a032/4.png" sizes="(max-width: 748px) 100vw, 748px" loading="lazy">
 위의 이미지처럼, 시작하는 원소를 기준으로 잡고 모두 적어보면 4 + 3 + 2 + 1 = 10개가 됩니다. 꽤 쉽고 간단하게 문제가 해결되는 것처럼 보이지만, 이를 구현하려면 다음과 같이 구현해야합니다.머리로 생각해봤을 때는 직관적이지만, 계산하기에는 수가 너무 많습니다.
이때 카데인 알고리즘이 등장합니다. <h2>카데인 알고리즘</h2>카데인 알고리즘은 이 <a href="https://en.wikipedia.org/wiki/Maximum_subarray_problem#Kadane's%20algorithm%20(Algorithm%203:%20Dynamic%20Programming)">최대부분합 문제 wikipedia</a>에 솔루션으로 등장합니다. 처음 생각해봐야할 것은 위처럼 <code>시작하는 원소</code>를 중심으로 하지 않고, <code>끝나는 원소</code>를 기준으로 한다는 것.
그리고 max 값의 집합에서 한번 더 max 를 찾는다는 점인 것 같습니다.위 [-2, 1, -3, 4] 예제를 봅니다. 
 
 <img alt="img" title="img" src="https://juneyr.dev/static/eea6e1843a03f4b08485ae854e52e430/5a032/5.png" sizes="(max-width: 748px) 100vw, 748px" loading="lazy">
 위와 같이 <code>끝나는 원소</code>를 기준으로 10개의 부분 배열을 모두 써보겠습니다. 0번째로 끝나는 부분배열들은 <code>E(0)</code> 라고 표기합니다.그러면 E(0) 은 [ {-2}],E(1) 은 [ {-2, 1}, {1}] .. 와 같은 식으로 정리할 수 있습니다. 
 
 <img alt="img" title="img" src="https://juneyr.dev/static/9e2ac887f1c2172b9449371c1f2832af/7d769/6.png" sizes="(max-width: 960px) 100vw, 960px" loading="lazy">
 이렇게 적으면 공통점이 보이시나요? <ul><li>E(1)은 <code>E(0) 의 모든 원소에 1을 포함시킨 것 + 1 만 있는 원소</code> 과 같습니다.</li><li>E(2)는 <code>E(1)의 모든 원소에 -3을 포함시킨 것 + -3 만 있는 원소</code> 와 같고요.</li><li>E(3)은 <code>E(2)의 모든 원소에 4를 포함시킨 것 + 4만 있는 원소</code> 입니다. </li></ul>합도 동일한 방식으로 흘러갑니다. 위와 비슷하게, i번째로 끝나는 부분배열의 합들 중 최대인 값을 M(i) 라고 하겠습니다. 즉, <ul><li>M(0) = -2, </li><li>M(1) = max(-2+1, 1) = 1 입니다. </li></ul>
 
 <img alt="img" title="img" src="https://juneyr.dev/static/60e5c1d95582937dbaaa7359c5b69557/7d769/7.png" sizes="(max-width: 960px) 100vw, 960px" loading="lazy">
 이를 관찰해보면 다음과 같은 결론이 나옵니다. <blockquote>M(i+1) 는 둘 중 하나이다. M(i) 값 + i+1 번째 원소 이거나 i +1 번째 원소 그 자체.</blockquote>이유는 단순합니다. maximum 값이 나온다고 하면, 이전에 컸던 것에 더하는게 더 크기 때문입니다. <code>a &lt; b -&gt; a + c &lt; b + c</code> 인 거죠.
 
 <img alt="img" title="img" src="https://juneyr.dev/static/f7f200d29e4d2c3cfff1ea60174aa8fe/7d769/8.png" sizes="(max-width: 960px) 100vw, 960px" loading="lazy">
 이런 규칙에 따라서 <code>i번째 원소로 끝나는 부분배열의 합</code> 들을 모두 나열해보고, 여기에서 다시 최대 값을 구하면 됩니다. 즉 여기서는 4입니다. <h2>코드로 옮겨보자!</h2>코드에서도 이 과정이 드러납니다. 두번 max를 구하여 값을 구합니다. <h3>마치며</h3>단순해보이지만 이해하는 것도, 정리하는 것도 쉽지는 않네요.
의견이 있다면 둥글게 댓글 부탁드립니다.<h2>참고</h2><a href="https://topdori.com/?p=234">2nd life of cfranck</a></section></div>

Juneyr.dev RSS Feed

June Kim

LeetCode를 시간이 날때마다 풀고 있습니다.
워낙 알고리즘에는 잼병이기도 하고, 생각의 폭을 넓히기 위해서 푸는데요. 
easy에 있는  Maximum subarray  를 풀게 되었습니다. 처음에는 효율이 굉장히 낮게 for 문 여러개를 돌려서 풀었는데요 (거의…

Maximum Subarray 최대 부분합을 푸는 방법 : 카데인 알고리즘 👩‍🏫

댓글