1. 알고리즘이란?, 연속된 숫자의 합

컴퓨터는 프로그램의 명령에 따라 순서대로 일을 처리하고, 이 때 효율적인 결과를 얻기 위해 필요한 것이 알고리즘이다.
그리고 자료구조는 정보를 효율적으로 저장하고 관리하는 방법으로서 효율적인 자료구조의 선택이 곧 효율적인 알고리즘이다. 이처럼 알고리즘과 자료구조는 상호 보완 관계에 있다.

오늘부터 자료구조, 알고리즘을 함께 배우며 기록해보려고 한다.

 

반복문을 사용한 간단한 알고리즘부터 살펴보겠습니다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.println("1부터 n까지의 합");
        int n = sc.nextInt();

        int sum = 0;
        int i = 1;
        while(i <= n) { //while문 사용
            sum += i;
            i++;
        }
        System.out.println("n : "+ sum);
    }
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.println("1부터 n까지의 합");
        int n = sc.nextInt();

        int sum = 0;
        int i;
        for(i = 1; i <= n; i++) { //for문 사용
            sum += i;
        }
        System.out.println("n : "+ sum);
    }
}

1부터 입력받은 값 n까지의 합을 구하는 간단한 알고리즘입니다. 하나의 변수를 사용하는 반복문은 while문보다는 for문을 사용하는 편이 더 좋습니다.

이러한 방식으로 숫자의 합을 구할수도 있지만 가우스의 덧셈을 활용하여 구할 수 있습니다.

가우스의 덧셈은 연속된 숫자의 합을 구할 때 유용한 원리인데 어떤 숫자 a, b가 주어졌을 때 a부터 b까지의 연속된 숫자의 합을 구하기 위한 식은 (a+b) * (b-a+1)/2 입니다. 즉 a+b를 한 쌍으로 본다면 a부터 b까지의 합은 a+b를 a부터 b까지의 갯수/2 만큼 곱하는 것과 같은 것입니다.

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        System.out.println("a부터 b까지의 합");
        System.out.print("a:");
        int a = sc.nextInt();
        System.out.print("b:");
        int b = sc.nextInt();


        int tmp;
        if(a >= b) { //a가 b보다 큰 경우
            tmp = a;
            a = b;
            b = tmp;
        }
        int Sum = (a + b) * (b - a + 1) / 2; //가우스 덧셈 공식
        System.out.println(a + "부터 " + b + "까지의 합: " + Sum);
    }
}