오늘의 피드백 - 거꾸로 생각할 때 주의할 점.

1. N개의 수열에서 구간의 합이 최대인 구간 찾기

문제는 아래와 같다.

N개의 정수가 담긴 수열이 주어진다. 이때 특정 구간의 합이 최대가 되는 구간을 찾는 효율적인 방법은?

문제는 워낙 간단하다. 그래서 무식하게 풀 수 있다. 존재할 수 있는 모든 구간 (p, q) 범위를 for 문을 통해 일일이 접근한다. 해당 구간의 합을 구해서 최대인지 확인한다.

 

그러나 이러한 방식은 시간복잡도가 사실상 쓸모 없는 수준이다. O(N^3)이다. 무려 세제곱이다. for 문을 통해 모든 p, q 구간을 접근해야 하므로 N 제곱의 처리가 소요되고, 또 더하기 연산을 위해서 또 O(N)이 필요하다. 즉, 복잡도는 세제곱이다.

 

개선해봤자 O(N^2)이 될 뿐이다. 특정 p 값에서 시작해서 q를 하나씩 늘려나가면 이전에 사용한 sum 정보를 활용할 수 있기 때문이다. 그러나 제곱 시간복잡도 또한 쓸모가 없다.

 

컴퓨터의 본질은 거꾸로 생각하기다. 여러 번 포스트를 통해 이 부분을 작성하고 공부했다. 여기서도 거꾸로 생각할 수 있다. 답을 미리 안다는 가정 하에, 그 모습을 상상해서 거기서 정보를 추출해보자. 이때 먼저 이 알고리즘은 해당 구간의 sum을 구해야 하므로 어떻게든 최소 한 번은 모든 원소를 스캔해야 한다. 최소 O(N)의 시간복잡도가 걸린다. 일단 모든 원소를 접근해야 한다.

 

그렇다면 최대합 구간 (a, b)에서 왼쪽으로 a를 후퇴시키면 sum은 어떻게 될까? 당연히 줄어든다. 원래 구간이 최대합 구간이라고 가정했기 때문이다. 반대로 b를 오른쪽으로 후퇴시켜도 sum은 줄어든다. 마찬가지 원리다. 최대합 구간이므로 양쪽 방향으로 늘려나가면 최대합 구간의 값은 줄어든다.

 

그렇다면 a를 최대한 후퇴시켜 인데스 0번에서 처음 시작해 b까지 왔다고 해보자. 그것은 0에서 시작해 올 수 있는 최대값이다. 왜냐하면 b를 오른쪽으로 이동시키면 무조건 줄어든다는 원리 때문이다.

 

이로서 해답이 풀린다. 역방향으로 생각하니 답이 풀린다. 이 문제의 알고리즘은 바로 0에서 시작해 계속 sum을 해나가는 것이다. 직전의 sum에 새로운 값을 더하면 되니 시간복잡도는 O(N)이다. 이때 0에서 시작해 최대 구간이 되는 b 지점이 있다. 그곳이 바로 최대합 구간의 오른쪽 경계다. 왼쪽 경계는 이제 풀기 쉬울 것이다. 이 논리를 그대로 수열을 뒤집어 똑같이 생각하면 된다.

 

그렇다면 아래의 방법은 어떨까?

 

2. N개의 수열에서 구간의 합이 특정 값인 구간 찾기

문제는 위 제목 그대로다. 이제는 최대값이 아니라 값이 어떤 값으로 결정된다.

 

내가 이 문제에서 조금 애를 먹었다. 해답에서 시작해 거꾸로 가야 한다는 컴퓨팅 사고력의 원칙을 지켰지만 끝내 역산하지 못했다.

 

역시나 이 문제도 구간의 합을 알아야 하기 때문에 적어도 한 번은 모든 원소를 스캔해야 한다. 이 감각을 알고 있다면 아무래도 0부터 시작해서 무언가 조치를 취해야 할 것이라는 직관이 생긴다.

 

최대합 문제의 경우, 0부터 시작해서 스캔을 해나갈 때 해야하는 조치란, 0에서 시작해 해당 구간까지의 sum이 max인지 확인하는 것이다. 그렇다면 특정 값 구하기 문제에서는 무슨 조치가 필요할까?

 

생각보다 쉬운 해답이 있었다. 최대합과 똑같은 논리다. 0에서 시작해 구간합이 특정 값인 구간 (a, b)의 오른쪽 경계 b에 도착했다고 해보자. 즉, 구간은 (0, b)이다. 

 

이 구간은 특정 값 구간인 (a, b)를 포함하는 구간이다. 따라서 (0, b)에서 (a, b)를 빼면 (0, a) 구간이 나오는데, 우리는 이 값을 알고 있다. 만약 특정 값이 100이라고 해보자. 그리고 (0, b)가 134라고 해보자. 그러면 (0, a)는 34가 되어야 한다.

 

따라서 0에서 스캔을 진행해나가면서 전체 sum을 구하고, 해당 sum이 해답 구간이라고 가정할 수 있다면 직전까지 (0, a) 구간 sum에서 특정 값인 경우가 있을 것이므로 검색이 간편한 자료구조(해쉬테이블이나 맵)에 매번 저장해나가면 된다.

 

3. 피드백

첫 번째 문제의 설명을 들었는데, 두 번째 문제에서 애를 먹었다. 원칙을 뭐랄까, 좀 교조적으로 수용한 것 같다. 해답에서 생각해서 특징을 추출해 시작 지점으로 나아가기라는 원칙을 지키려고 애 썼는데, 약간 로직을 다르게 변경하니 그 특징을 추출할 수 없었다.

 

이런 유형의 알고리즘을 만나면, 먼저 최소한의 작업이 무엇인지 떠올려야 한다. 예를 들어, 모든 원소를 적어도 한 번은 스캔해야 한다면, 아마 첫 시작은 0번 인덱스에서 시작해야 할 것이다. 따라서 0에서 시작해 구간의 오른쪽 경계 b에 도달하는 구간 (0, b)를 생각해야 했다.

 

이 구간에서 얻을 수 있는 정보는 (0, b) 구간의 전체 sum과, 문제의 해답인 (a, b) 구간의 sum이다. 따라서 구간 (0, a)의 값을 얻을 수 있다. 이것만 할 수 있다면 게임 끝이다.

 

나는 동적인 변화만 너무 신경 썼다. 해답 구간 (a, b)에서 왼쪽으로 a를 조정해나갈 때 변화하는 특징만 캐치하려 했다. 그러나 최대합 문제가 아니라 특정 값 문제이기 때문에 정답에서 거꾸로 출발해도 그 어떤 패턴과 규칙도 발견할 수 없다. 따라서 첫 시작 지점에서의 구간 (0, b)와 (a, b) 사이의 관계를 바로 생각해야 했던 것이다.