정렬된 두 배열에서 합 찾기

다음과 같은 두 개의 배열이 있다.

A 배열에서 하나의 자연수, B의 배열에서 하나의 자연수를 뽑아 그 합이 19가 되게 만들 수 있을까?

만들 수 있다면 어떻게 탐색해야 할까? 가장 직관적으로 생각보면 두 개의 배열의 크기만큼 이중 반복문을 통해 탐색할 수 있을 것이다. 그럴때 시간복잡도가 O(N^2)가 된다는 것은 명백하다.

Slider

더 효율적인 방법은 아래와 같은 방법을 사용하는 것이다.

A배열에서는 가장 왼쪽에서, B배열은 가장 오른쪽에서 시작한다.

현재 위치의 합이 목표보다 작으면 위쪽 배열의 위치를 오른쪽으로..

현재 위치의 합이 목표보다 크면 아래쪽 배열의 위치를 왼쪽으로 이동시킨다.

직관적으로 맞는거 같은데 뭔가 확실히 그렇다라고 말하기엔 애매한 느낌이 든다.

증명

이를 증명하기 위해서는 답을 놓치는 경우 반드시 발생되는 상황을 만들고, 그 상황이 불가능한 것임을 보이면 된다(귀류법). 합이 19가 되기 위해서는 인덱스가 아래처럼 위치해야 한다.

만약 i의 위치가 A배열에서 5의 위치에 있을때, j가 B배열에서 14의 위치보다 왼쪽에 있어야 불가능한 상황이 연출된다.

따라서 i가 A배열에서 5의 위치보다 왼쪽에 있을때, j가 14의 위치에 있는 상황에서 j가 왼쪽으로 이동하는 상황이 발생한다면 우리가 만들고자 하는 알고리즘이 잘못된 것임을 증명할 수 있다.

하지만 이 상태에서 3+14 = 17이므로 찾고자하는 값인 19보다 작다. 19보다 작으므로 B배열을 이동시키는 것이 아니라 A배열을 우측으로 이동시켜야하므로 자연스럽게 아래처럼 답을 찾을 수 밖에 없다. 따라서 Slider 방식의 탐색 로직은 타당하다고 볼 수 있다.