개발/알고리즘 & 자료구조

[C++] 두 정수 사이의 모든 합 구하기

신매력 2013. 9. 21. 17:56

어제 올린 글에는 최적화를 생활화하자는 글을 썼었는데,

오늘은 반대로 최적화를 잘못하면 화를 부를 수 있다는 것을 정리해보고자 한다ㅋㅋㅋㅋ




1. 문제


두 정수 사이의 모든 합을 구하는 것이다.


3, 5를 입력받으면

3 + 4 + 5 를 한 결과를 출력하면 됨.


작은 수부터 입력 받는다고 가정하자.



2. 알고리즘


가장 먼저 생각할 수 있는 알고리즘은

입력 받은 수부터 두번째 입력 받은 수 까지 반복문 돌리면서 더하는 것이다.




반복문을 좀 줄여본다면???



1 + 2 + 3 + 4 + 5 + 6 를 보면 규칙을 찾을 수 있다.


1 + 6 = 7

2 + 5 = 7

3 + 4 = 7



이것을 이용하면, 포문을 반으로 줄일 수 있다!


여기서 잠깐,

더할 수의 개수가 홀수이면 이렇게 된다.


1 + 2 + 3 + 4 + 5


1 + 5 = 6

2 + 4 = 6

그 다음 가운데 홀로 남은 3을 더해주면 된다.



위에 언급한 두 알고리즘으로 작성한 예제를 보자.



3. 예제


문제 : 두 정수 사이의 모든 합 구하기


다 더하기 >>


void sumOfTwoNumber(int val1, int val2) {

    unsigned long sum = 0; // 큰 숫자를 넣기위해 양수형 long으로..


    for (int i = val1; i <= val2; i++) {

        sum += i;

    }

 

    cout << sum << endl;

} 


int main(void) {

    sumOfTwoNumber(1, 5);

}



반복문 반으로 줄이기 >>


bool isEvenNumber(int val1, int val2) {  // 짝수인지 판별하는 함수

    if ((val2 - val1) % 2 != 0) {

        return true;

    }

    

    return false;

}


void sumOfTwoNumber(int val1, int val2) {

    unsigned long sum = 0;

    int j = 0;

    

    for (int i = val1; i <= (val1 + val2) / 2; i++) {

        /** 아직 i가 val1,val2를 2로 나눈 값과 같지 않거나,

             i가 val1, val2를 2로 나눈값과 같으면서 짝수인 경우에만 뒤에 값을 더한다.

        **/

        if (i != (val1 + val2) / 2 

            || (i == (val1 + val2) / 2 && isEvenNumber(val1, val2))) {

            

            sum += val2 - j;

        }

        

        sum += i;

        j++;

    }

  

    cout << sum << endl;

}

 

int main(void) {

    sumOfTwoNumber(1, 5);

}


결과 >>

15 



반으로 나누는 조건에서부터 헷갈려지기 시작하고, 이렇게까지 해야하나 싶어졌다.

어려운 길은 길이 아니라는 말이 있는데 그 말이 나의 상황인가 싶었음.

포문 한번 돌리면 될 일을 저런 조건을 추가해야하는가.... ㅠ

가독성도 떨어지고..



시간을 재봤다.


차이가 없었다....... '_'...



괜한 함수까지 만들고 로직 생각에 시간 버리느니 

그냥 포문 다 돌리는게 낫다. 어차피 돌려봐야 복잡도는 O(n)이기 때문이다.




다른 알고리즘도 있다.


바로, 공식을 이용하는 방법이다.


 ((첫번째 수 + 맨 끝 수) * 총 더할 수의 개수) / 2



만약 3부터 7까지 더한다고 하면,


((3 + 7) * 5) / 2  이고 답은 25가 된다.



공식을 이용한 방법 >>


void sumOfTwoNumber(int val1, int val2) {

    unsigned long sum = 0;

    

    sum = ((val1 + val2) * (val2 - val1 + 1)) / 2;

    

    cout << sum << endl;

}


int main(void) {

    sumOfTwoNumber(1, 5);

}


가장 짧게 끝나고 반복문도 없으니 좋아보인다.


하지만, val2에 30000 정도의 값만 들어가도 이상한 값이 출력된다.

왜냐면 큰 수를 곱하면서 변수에 들어갈 수 있는 최대 값이 넘어가버리기 때문이다.



결정적으로 속도차이는 세개 모두 그닥 없다. ㅋㅋ


그래서 성능에 아주 큰 영향을 미치지 않는다면 가독성이 좋고 짜기 쉬운 코드를 짜는 것이 좋다.

상황에 따라 융통성있게 짜면 되겠다.



1 2 3 4 5 6 7 ··· 10