alogrithm 썸네일형 리스트형 2.1 Recursion에 대한 이해 앞선 내용에서는 Maximum Range Sum을 구하는 함수를 구현하고 거기에서 중복되는 연산부분을 없애는 방식으로 수행 속도를 향상시켰다. 이것을 하는데 있어서는 아무런 사전 지식이 없어도 생각을 해본다면 Live하게 짤 수 있는 알고리즘이었다. 이번에는 Recursion이 무엇인지에 대해 살펴보도록 하겠다.Recursion을 한국말로 번역을 하자면 '반복'이라는 뜻을 가지고 있다. 즉 Recursive function은 같은 함수가 반복해서 여러 번 불린다는 뜻을 의미한다. Recursive function을 이용해서 문제를 해결하기 위해서는 기본적으로 Divide & Conquer 전략을 사용한다. 즉, 큰 문제가 있다면 그것을 작은 부분 문제로 쪼개서 해결한 다음 그 결과를 이용해서 큰 문제를 .. 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 다음