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

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

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

 

 

 

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 정도의 값만 들어가도 이상한 값이 출력된다.

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

 

 

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

 

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

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