수열의 어떤 두 정수의 합이 주어진 숫자가 되는 경우 판별

트랙백: 어떤 두 정수의 합이 주어진 숫자가 되는 경우가 있는가? - object 님


일단 문제는, 다음과 같이 정렬된 임의의 숫자 배열있다고 할 때...

int a[] = {1, 4, 7, 9, 10};

여기에 어떤 정수 n 이 주어졌다고 할때, 배열 내의 두 정수의 합이 n이 되는 경우가 있는지 판별하는 겁니다.
가령 n = 19라고 하면, 9 + 10 = 19 이므로 참(true) 입니다.

뭐, 자세한 내용은 트랙백된 주소를 따라가 보면 되겠고... (무책임...)

그런데 중요한 문제는, 이것을 가능한 최적화된 알고리즘(속도도 빠르면서 메모리도 덜 잡아먹는)으로 풀어보자는 것입니다.

일단 아직 검증이 끝난건 아니지만, 제가 생각한 알고리즘은 대략 이렇습니다.

bool CheckSum(unsigned int numbers[], unsigned int length, unsigned int sum)
{
   unsigned int* num1 = &numbers[0];
   unsigned int* num2 = &numbers[length-1];
   unsigned int  pair = 0;

   while (*num1 < *num2) {
      if (sum >= *num2) {
         pair = sum - *num2;

         if (*num1 == pair) return true;
         else if (*num1 < pair) {
            num1++;
            continue;
         }
      }

      num2--;
   }

   return false;
}