maximum range sum 썸네일형 리스트형 1.2 Maximum Range Sum (2) 앞에서 사용한 알고리즘의 Time Complexity는 $O(n^3)$이었다. 이것을 줄이기 위해서는 불필요한 연산을 줄이는 것이 가장 먼저 할 수 있는 방법이다. 일단 앞의 알고리즘을 이용해서 작성한 소스코드를 다시 살펴보도록 하자. int getMaximumRange1(int *arr, int size){ int max = INT_MIN; for(int i=0; i 1.1 Maximum Range Sum (1) Maximum Range Sum이란 길이가 n인 배열을 받아서 구간을 잡아 그 구간에 있는 모든 배열 값을 더해서 그 값이 최대가 되도록 하는 값을 찾도록 하는 문제이다. 그냥 바로 생각하면 배열의 모든 값을 더하면 최댓값이 될 수 있다고 생각할 수도 있지만, 이렇게 하려면 배열의 모든 값이 양수라는 조건이 있어야 한다. 즉, 임의의 숫자에 대해서는 이렇게 생각할 수 없다는 것이다. 그러면 이 문제를 어떻게 하면 해결 할 수 있을까? 가장 간단한 방법은 모든 구간에 대해서 Range Sum을 계산해서 그 값을 계속 비교해나가면서 최대인 것을 선택해서 그 값을 반환해주면 된다. 이제 이것을 C++ 코드로 작성하면 아래와 같다. int getMaximumRange1(int *arr, int size){ in.. 이전 1 다음