본문 바로가기

Programming

[Algorithm] 배열의 연속된 구간 최대 합을 구하는 알고리즘

728x90
반응형





배열의 연속된 구간의 최대 합을 구하는 알고리즘을 분석해 보겠다.

위와 같은 배열이 주어졌다면 빨간 구간의 합이 가장 크다. 이때 구간의 합 30을 리턴하는 알고리즘이다.


이 알고리즘은 개의 후보 구간을 검사하고, 각 구간의 합을 구하는데 의 시간이 걸리기 때문에 이 알고리즘은 의 시간이 걸린다.





다음은 같은 연산을 하는, 좀 더 빠른 알고리즘이다.


이 알고리즘에서는 번 수행되는 반복문 두 개를 겹쳤다. 따라서 시간 복잡도는 가 되는 것을 쉽게 알 수 있다.




다음 방법은 분할 정복 기법을 이용한 알고리즘이다. 


입력 받은 배열을 우선 절반으로 잘라 왼쪽 배열과 오른쪽 배열로 나눈다. 이때 우리가 원하는 최대 합 부분 구간은 두 배열 중 하나에 속해 있을 수도 있고, 두 배열 사이에 걸쳐 있을 수도 있다. 


각 경우의 답을 재귀 호출과 탐욕법을 이용해 계산하면 더욱 빠른 알고리즘을 얻을 수 있다.



위의 알고리즘을 살짝 살펴보면 이전 알고리즘과 가장 다른 점은 전달 받는 인자의 개수이다. 앞의 배열과 다르게 구간을 입력 받는데 이는 재귀 호출로 구간을 나누기 때문이다. 이를 그림으로 나타내면

위의 그림처럼 나타낼 수 있다. 즉 재귀로 나누고 다시 돌아 오면서 각 구간을 나눠 합을 먼저 비교해서 리턴하고 이 리턴 받은 값을 나누지 않고 구간의 합과 비교해서 마지막에 가장 큰 값을 리턴한다.





마지막 방법은 동적 계획법을 사용하는 방법이다.


이 알고리즘의 아이디어는 다음과 같다.


A[i]를 오른쪽 끝으로 갖는 구간의 최대 합을 반환하는 함수 maxAt(i)를 정의를 한다.

A[i]에서 끝나는 최대 합 부분 구간은 항상 A[i] 하나만으로 구성되어 있거나, A[i-1]를 오른쪽 끝으로 갖는 최대 합 부분 구간의 오른쪽에 A[i]를 붙인 형태로 구성되어 있다. 


이를 바탕으로 점화식을 쓰면 가 된다. 




지금까지 같은 문제를 해결하는 4개의 알고리즘을 보았다. 각 알고리즘의 시간 복잡도를 비교해보면

을 가진다. 즉 같은 방법을 풀더라도 더 좋은 알고리즘을 만들 수 있다.






반응형