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

art.oriented에 올라온 어떤 두 정수의 합이 주어진 숫자가 되는 경우가 있는가?라는 글의 트랙백입니다.

코드가 비교적 단순해서 코드만 보시면 어떤 방법인지 아실 수 있습니다. 실행 파일을 만들 수 있는 전체 코드입니다. (에러 체크같은건 없습니다. ;-) )


#include

using namespace std;

int main(int argc, char *argv[])
{
int V[] = { 1, 4, 7, 9, 10 };
int N = sizeof(V) / sizeof(*V);

int K = atoi(argv[1]);

int* l = V;
int* r = V + N - 1;

while (l < r) {
int sum = *l + *r;

if (sum < K) ++l;
else if (sum > K) --r;
else break; // sum == K
}

if (l < r) cout << "found(" << *l << ", " << *r << ")\n";
else cout << "not found\n";
}


간단히 설명하면, 제일 작은 수와 제일 큰 수를 각각 left, right로 놓고 이 두 수의 합을 원하는 값과 비교합니다. 만약 두 수의 합이 원하는 값보다 작다면 left를 다음 작은 수로 설정합니다. 이와 반대로 원하는 값보다 크다면 right를 다음 큰 값으로 놓습니다. 같으면 원하는 숫자의 합이 발견된 것이므로 바로 종료합니다.

적어 보니 그냥 단순 searching인것 같은데... 맞나요? :-)

Comments

  1. 오 최대n번의 비교로 값이 나오는군요..

    ReplyDelete
  2. 오랜만의 포스팅이시네요~.

    ReplyDelete
  3. 풍선생/ 네, 어쩌다보니 값이 나오네요. :-)

    홍민희/ 정말 오랫만이죠. 세달도 넘었네요. 처음엔 뭐 준비할게 있어서 잠시 쉰건데 쉬다보니 다시 시작하기가 어렵더라고요. 마침 object님이 문제를 하나 내셔서 덕분에 다시 시작하게 되었습니다.

    홍민희님 댓글을 보니 왠지 기다려 주신 것 같아서 무지 반갑고 고맙네요. :-)

    ReplyDelete
  4. 정렬된 자료에 대해서만 성립하나요? 그러면 정말 단순한 알고리즘이 나올텐데.. 정렬되지 않은 자료에 대해서 exact value를 계산하려면 다 돌리는 것 말고는 방법이 있을 수가 없겠죠.

    ReplyDelete
  5. 네, 위의 코드는 배열이 정렬되어 있다는 가정하에 작성된 코드죠. 혹시 더 간단한 방법을 알고 계신가요? 8-O

    ReplyDelete
  6. 뒤늦게 이제서야 답글을 다네요. 도움 주셔서 감사합니다~ 자주 들리고 있습니다 ㅎㅎ

    ReplyDelete
  7. 저도 늘 잘 보고 있습니다. :-)

    ReplyDelete

Post a Comment

Popular Posts