주어진 합을 가지는 특정 구간 구하기

문제.
 수열과 어떤 값 하나가 주어진다. 구간의 합이 특정 값인 구간을 구하라.

이 문제를 풀기 위한 아이디어로 다음과 같이 생각했다.

 

1. 시간복잡도

시간복잡도는 적어도 O(N)이다. 절대로 이것보다 낮을 수는 없다. 구간의 "합"을 알아야 하므로 최악의 경우 수열의 전체 구간이 답이 될 수도 있기 때문이다. 

 

2. 나에게 주어진 정보

보통 알고리즘의 Big-O가 N^2이나 N^3이 되는 이유는 불필요한 계산을 하기 때문이다. 불필요한 계산은 문제에서 주어진 정보나, 본인이 계산을 진행해가며 얻은 값들을 정보로 활용하지 않을 때 발생한다. 그래서 나에게 주어진 정보는 아래와 같았다.

• 문제에서 주어진 정보 = 구간의 값.
• 계산을 하며 얻을 수 있는 정보 = 0번째 배열부터 시작해 p 까지의 누적합.

 

3. 최초의 아이디어

쉽게 떠올릴 수 있는 직관적인 대답은 "모든 구간의 경우의 수를 구한 뒤 그 합들을 특정 값과 비교한다"이다. 당연히 Big-O가 N^3이기 때문에 (개선해봤자 N^2에 불과하다) 실용성이 극히 떨어진다.

문제는 거꾸로 접근하는 것이 좋다. 거꾸로 생각하자. 만약 내가 어떤 구간을 알고 있다고 가정한다면? 그렇다면 그 구간의 합은 A일 것이다. 그리고 0번째부터 A의 오른쪽 한계 구간까지의 합 Sum가 있다. Sum-A를 구할 수 있다.

따라서 처음 내가 생각한 방식은 아래와 같았다.

• 0번째부터 누적합을 구하고 각각의 값을 배열에 저장한다. 
• 누적합에서 특정 값을 빼본다. 이 값은 Sum - A다.
• 이 값은 바로 왼쪽 구간 즉, Sum-A 값이다.
• 이 값이 배열에 있는지 확인하고, 있으면 그 배열의 index+1 값이 왼쪽 구간이다.
• 오른쪽 구간의 index는 누적합을 구하고 있는 바로 그 인덱스다.

문제는 위와 같은 방식에서는 Sum-A 값을 찾는데 또 N 시간이 걸려 결과적으로 알고리즘의 복잡도가 N^2가 된다는 것이다.

 

4. 개선

내가 왜 굳이 배열에 집어 넣었을까 싶다. 어차피 해당 값이 있다면, 그 값의 인덱스를 알고 싶은 것이다. 추가적으로 데이터를 변경할 일도 없고, 배치를 바꿀 이유도 없다. 따라서 해시맵을 통해 특정한 값의 검색의 시간복잡도를 N(1)로 가져가면 되는 것이었다.