에이쥬어의 이러쿵저러쿵 :: 어떤 두 정수의 합이 주어진 숫자가 되는 경우가 있는가?

2007/08/08 20:29

어떤 두 정수의 합이 주어진 숫자가 되는 경우가 있는가?

2007/08/08 20:29 in 프로그래밍과 알고리즘

어떤 두 정수의 합이 주어진 숫자가 되는 경우가 있는가? - art. oriented님의 블로그에서 트랙백

문제를 간단히 설명하자면, 어떤 수열이 있다.
이 수열 내에서 어떤 두 정수를 더하여, 임의의 정수 M을 만들 수 있는가? 하는 것이다.
수열은 오름차순으로 정렬되어 있다.

다음과 같은 O(N^2) 알고리즘은 쉽게 찾을 수 있을 것이다.

for(front=0; front < N; ++front){
for(last=front+1;last < N; ++ last)
if(A[front]+A[last]==M)
printf("%d %d\n",A[front],A[last]);

그러나, 이 방법은 N이 조금만 커져도 너무 오랜 시간이 걸린다. 개선해야 한다.
두 번째의 loop를 다음과 같이 고쳐보자.

for(last = N-1; last > front && A[last] >= M - A[front]; -- last)

여전히 알고리즘은 O(N^2)의 복잡도를 보이지만, 약간 개선된 것을 알 수 있다.
하나의 숫자를 A[first]로 정하면, 찾아야 하는 다른 숫자는 M-A[first]이다.

수열은 오름차순 정렬 상태이기 때문에, last가 감소할수록 A[last]의 값은 감소한다.
자, 마찬가지 이유로, first가 증가하면 A[first]도 증가한다.

따라서, M-A[first]는 감소한다.

찾고자 하는 값인 M-A[first]가 감소했으므로, 그에 대응하는 짝인 A[pair]의 위치도 감소할 것이다. 이를 이용해서 간단한 O(N) 알고리즘을 만들 수 있다.

for(front=0, last=N-1; front < N; ++front){
for(; last > front && A[last] >= M - A[front]; -- last)
if(A[front]+A[last]==M)
printf("%d %d\n",A[front],A[last]);