정수합, 가우스 덧셈 - 자료구조와 함께 배우는 알고리즘 입문(자바)

해당 포스팅은 "자료 구조와 함께 배우는 알고리즘 입문"이라는 책을 바탕으로 공부한 내용임.

정수의 합 구하기 - while을 이용

특정 숫자를 메서드 안에 넣으면 1부터 해당 숫자까지의 합을 구하는 식이다.

 

public static int while_test(int a){

        int i = 0; // 연산에 기준이 될 값
        int sum = 0; // 반환할 값

        while(i <= a){
        
            sum += i; // while문이 한번 반복될 때 증가한 i는 sum에 계속 저장
            
            i++; // while문이 한번 반복될 때마다 i는 1씩 증가
            
        }
        
        return sum;
    }

 

while문을 이용할 줄 안다면 기본적으로 이해하기는 어렵지 않을 것이다.

 

참고로 단항 연산자 ++와 --에 대한 건 앞으로도 많이 쓸텐데 다음과 같이 움직인다.

 

종류	설명
++i	해당 코드가 완전히 수행되기 전 +연산을 수행
i++	해당 코드가 완전히 수행된 후 +연산을 수행
--i	해당 코드가 완전히 수행되지 전 -연산을 수행
i--	해당 코드가 완전히 수행된 후 -연산을 수행

 

예를 들면 다음과 같다.

 

public static void operator(){

        int i = 0;

        System.out.println(i++); // 0 출력
        System.out.println(i); // 1출력
        
    }

 

단항 연산자 ++는 변수 뒤에 오면 해당 연산자가 있는 코드가 수행되고 나서 +연산이 실행된다.

 

위의 경우 콘솔창에 i값이 출력되고나서야 +연산이 실행되서 다음번 출력에 반영되는 것을 볼 수 있다.

 

public static void operator(){

        int i = 0;

        System.out.println(++i); // 1출력
        System.out.println(i); // 1출력

    }

 

반대로 ++를 변수 앞에 두면 뒤에 두는 것과 반대로 코드 수행 전에 +연산이 실행되는 것을 볼 수 있다.

정수의 합 구하기 - for 문을 이용

public static int for_test(int a){

        int sum = 0; // 반환될 값

        for(int i = 1; i <= a; i++){
        
            sum += i; // for문이 한번 실행될 때마다 i가 누적되어 더해짐
            
        }

        return sum;
    }

 

정수합을 구할 때는 while도 있지만 아래와 같이 for문을 이용할 수도 있다.

 

책에서는 변수 1개를 이용할 때는 while보다는 for문이 유리하다고 쓰여있다.

 

하지만 이런 단순 연산에선 둘의 차이는 그리 크지 않다.

가우스의 덧셈 구하기

정수를 더하는 법칙 중 가우스의 덧셈이라는 것이 있다.

 

가우스란 천재 수학자가 10살 때 발견한 법칙이라고 하는데 이해하기 쉽고 써먹기도 좋다.

 

일정한 간격의 정수가 순서대로 나열되있을 때 맨 앞의 정수와 맨 뒤의 정수를 더해나가는 방식으로

 

덧셈을 해나가는 것이다. 아마 그림으로 보면 더 쉬울 것이다.

 

그림처럼 맨 앞과 맨 뒤 정수를 순서대로 더한 뒤 나온 합을 다 더하면 모든 정수의 합을 얻을 수 있다.

 

이 방법을 쓰면 for문과 while문에 비해 연산 횟수가 적어진다.

 

그래서 답은 같더라도 훨씬 효율적인 알고리즘이 되는 것이다.

 

해당 알고리즘에 대해 내가 구현한 코드는 다음과 같다.

 

public static int gauss2(int a){

        int result; // 결과물을 담을 변수

        result = (1+a)*(a/2); // 맨앞과 맨끝 정수의 합을 구하는 식

        if(a%2!=0){ // 만약 정수의 개수가 홀수라면 남은 1개의 홀수를 더하는 선택문
            result += (a+1)/2;
        }

        return result;
    }

 

위의 그림을 보면 알겠지만 맨 앞과 맨 끝의 정수의 합은 일일이 해줄 필요가 없다.

 

1~6까지의 합을 구하랬다고 1+6, 2+5, 3+4 이런 식으로 해줄 필요가 없다는 말이다.

 

정수의 개수가 짝수일 경우 맨 끝의 숫자에 1을 더하고 이 숫자에 전체 정수 개수를 2로 나눈 수를 곱한다.

 

대략적인 식으로 표현하면 아래와 같다.

 

계산할 정수 개수가 짝수일때: 결과값 = ( 맨 끝 숫자 + 1 ) * ( 전체 정수 개수 / 2 )

 

즉 1~6까지의 합이라면 ( 1 + 6 ) * ( 6 / 2 ) = 21 가 된다.

 

만약 나열된 정수 개수가 홀수면 가운데 한 개의 숫자가 남는다.

 

그래서 이렇게 남은 한 개의 숫자는 if문을 통해 추가해줄 수 있도록 만들었다.

 

public static int gauss(int a){

        int result; //결과물을 담을 변수

        result = (1+a)*(a/2) + (a%2==0?0:(1+a)/2);

        return result;
        
    }

 

위 코드는 책에 나온 알고리즘이다.

 

잘 살펴보면 알겠지만 형태만 다르고 연산하는 방법과 결과는 똑같다.

 

다만 책에 나온 알고리즘은 3항 연산자를 사용해서 더욱 간결하게 나타낸 것이 특징이다.

2개의 정수를 받아 그 사이의 모든 정수의 합을 구하여 반환하기

2개의 정수를 받아서 작은 정수에서 큰 정수까지의 합을 구하는 문제다.

 

예를 들어 정수 2와 7을 매개변수로 전달하면 2~7까지의 정수를 합해서 27을 반납하는 것이다.

 

public static int sumof(int a, int b){
        
        int max; // 가장 큰 수를 담을 변수 선언
        int min; // 가장 작은 수를 담을 변수 선언
        int sum = 0; // 모든 정수의 합을 담을 변수 선언

        // a와 b중 어떤 숫자가 큰지 판단하는 식
        if(a>b){
            max=a;
            min=b;
        }
        else{
            max = b;
            min = a;
        }

        // for문을 이용해서 작은 수부터 큰 수까지의 1씩 증가하면서 전부 합쳐서 반환
        for(int i = min; i <= max; i++){
            sum+=i;
        }
        
        return sum;
    }

 

이 문제는 어렵지 않다.

 

두개의 정수를 받아서 정수끼리 크기를 비교한다.

 

그 뒤 작은 수에서 시작해서 큰 수까지 1씩 증가시키면서 더한 뒤 반환하면 된다.