이 글은 "아, 나도 이제 프로그래밍 언어 하나 정도는 자유자재로 다룰 수 있어!" 하면서 우쭐하고 있는 새싹들을 잘라버리기 위해(...) 씁니다. 어쩌면 연재물이 될지도 모르겠네요. 뭐 이렇게 말하는 저도 그냥 새싹들 중 하나긴 합니다만(...)


1번. 정수들의 배열 A가 있습니다. 여러분은 정수 i와 j를 입력받아 A[i]부터 A[j] 사이의 값을 모두 더한 결과(A[i] + A[i+1] + ... + A[j-1] + A[j])를 출력하는 프로그램을 만들어야 합니다. 그런데, 이러한 작업을 cntQuery번 수행해야 한다면 어떤 알고리즘을 사용하겠습니까? 그리고 그 알고리즘의 시간 복잡도는 무엇인가요?

참고 :  만약 프로그램의 실행 시간이 데이터의 크기 N의 제곱에 비례한다면 이 프로그램의 시간 복잡도를 O(N^2)이라고 합니다. cntQuery와 N^2의 곱에 비례한다면 O(cntQuery * N^2)이 되겠지요.

2번. 1번과 같습니다. 그러나 이번에는 구하여야 하는 것이 달라졌는데, A[i]와 A[j] 사이에서 가장 큰 값을 찾아 출력해야 합니다. 1번의 알고리즘을 변형시켜 그대로 이용할 수 있습니까? 그렇지 않다면 어떤 알고리즘을 이용해야 할까요?

3번. 1번과 같습니다. 그러나 고객이 새로운 요구사항을 추가했습니다. 그것은 배열의 내용을 변경시키고 싶다는 것입니다. 그래서 여러분은 고객이 음수인 i를 입력하였을 경우 A[-i] = j가 되도록 하겠다고 약속했습니다. 이 경우에도 1번의 알고리즘을 사용할 수 있나요? 그렇지 않다면 대안은 무엇입니까?

4번. 다른 모든 조건은 3번 문제와 같지만, 구하여야 하는 것은 2번과 같습니다. 이 경우는 어떻게 됩니까?

풀이는 지켜보다가 이 쯤이 적당하다 싶으면 올리겠습니다.

추가 1 : 메모리 사용량에 대해서 언급해야 할 것 같네요. 너무 무식하게 막 쓰지는 맙시다. 예를 들어 N^2개의 배열을 만들어서 죄다 인덱싱해 버린다거나 하는거 자제합시다 -,.-;;;

추가 2 : N의 크기가 상당히 큰 경우에, preprocessing을 통해 각각의 명령에 대한 수행 성능을 높일 수 있다면, preprocessing에 소요되는 복잡도와, 하나의 명령을 실행하는 데 드는 복잡도를 나눠서 써 봅시다.

추가 3 : 여러분이 사용하는 플랫폼은 너무 우월해서 정수 범위가 무한대로 제공되며 한 사이클 내에 처리된다고 가정합시다. 요컨대 한 번의 정수 연산은 졸라빨라염. 므겡므겡믱믱...