[알고리즘] 증명에 관해서

 

예시로 정렬된 두 배열에서 합 찾기를 들어보겠다.

 

x = 1, 3, 5, 9, 12, 13, 15, 20

y =2, 7, 8, 10, 11, 14, 16, 17

 

이렇게 배열이 주어질 때, x배열, y배열의 인자를 합쳐서 23이 있는지를 확인하는 알고리즘이다.

 

1. 직관

2. 증명

3. 풀이

 

이와 같은 3단계를 거쳐서 문제를 해결해 나가야 한다.

 

1. 직관 

x는 왼쪽부터, y는 오른쪽 부터 이동하면서 더하고,

더한 합이 33보다 크면 y를 왼쪽으로 이동시키고, 

더한 합이 33보다 작으면 x를 오른쪽으로 이동시키면 되지 않을까?

 

2. 증명

그러면 1번과 같은 알고리즘을 적용했을 때 빠트리는 경우가 없다는 것을 어떻게 증명할 것인가?

 

- 빠트리는 경우가 있다면 반드시 일어나야 하는 상황을 도출하고, 그 상황이 불가능 하다는 것을 증명해야한다.

 

예를들어서, x가 9, y가 16인 상황에서 직관으로 본다면

x가 9, y가 14가 되어  합이 23이 되고, 알고리즘이 종료한다.

 

그렇다면 과연 x가 9인데, y가 11이 되는 경우가 존재할 것인가??

반복문의 증가 인덱스는 1이기 때문에 불가능하다.

 

따라서 이 알고리즘은 증명이 되었다고 볼 수 있다.

 

3. 풀이

직관이 증명이 되고, 그 증명을 기반으로 상세한 알고리즘을 만들어서 풀어나가면 될 것이다.