본문 바로가기

Computer/Etc

kadane's algorithm(maximum contiguous subarray)

분명히 어디선가 봤던 문제였는데...

이렇게 볼때마다 새로운지...

내 기억력이 이렇게 짧다는 것을 다시 한번 확인했다.


내 기억력을 확인해 준 문제는...


maximum contiguous subarray problem


어떤 배열이 주어졌을 때, 배열에서 연속된 부분배열 중 가장 큰 합을 찾는 문제이다.


예를 들면,

array = [2, -1, 2, 3, 4, -5]

에서 maximum contiguous subarray는 [2, -1, 2, 3, 4] 가 되어 maximum은 10 이 된다.


어찌보면, 간단해 보이지만...

각 배열의 index에서 가능한 모든 sum을 구해야 한다고 생각하면 그리 쉽지 않다.


하지만, 이 문제의 해법과 관련된 유명한 알고리즘이 있는데...

그 알고리즘이 kadane's algorithm이다.

http://en.wikipedia.org/wiki/Maximum_subarray_problem


알고리즘을 간단히 설명하면, 1차원으로 이뤄진 배열에서 

배열을 한번 스캔하면서, 각 포지션에서 가지는 최대값을 구하는 그런 알고리즘이다.

(글로 적다보니... 내가 제대로 이해한 것인가에 대한 의문이 든다.)

좀 더 명확한 설명은 위에 있는 위키 링크를 보시길...


내가 풀었던 방법은 index가 필요한 계산은 아니였기에...

maximum sum만 확인하면서 문제를 해결한다.(find_contiguous_subarray() 참고)


아래에 있는 코드를 보며... 다음에는 이 문제를 보고 당황하지 않기를 바라며...

이 포스팅을 마무리한다.


'Computer > Etc' 카테고리의 다른 글

git tag  (0) 2015.03.31
git color 설정하기  (0) 2015.03.31
kadane's algorithm(maximum contiguous subarray)  (0) 2015.03.21
mvn 설치  (0) 2015.03.09
mvn proxy 설정  (0) 2015.03.07
mongodb 설치 및 사용  (0) 2015.01.15