[Java] 8.0. 필수 알고리즘 - 알고리즘이 필요한 이유

1. 전체 탐색

• 무작정 더하기(for문을 돌면서)

package algo;

public class BruteForce {
    public static void main(String[] args) {
        // O(n) -> O(1): bruteforce -> gauss
        int n = 1000000;

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

2. 가우스 연산

• S: 총합

• n: 항의 개수(10개)

• a: 첫 번째 항(1)

• l: 마지막 항(10)
$S = n * (a + l) / 2$

package algo;

public class Gauss {
    public static void main(String[] args) {
        // 가우스 연산 1, 2, 3, 4, 5, 6 -> (1+6) (2+5) (3+4) -> 6 * 7 / 2 = 21

        // 1부터 10까지 더하기
        // 1. n(항의 개수)값 저장
        // 2. a(첫 항)값 저장
        // 3. l(마지막 항)값 저장
        // 4. 수식 쓰기

        int n = 10;
        int a = 1;
        int l = 10;
        int s = n * (a + l) / 2;
        System.out.println("합: " + s);
    }
}

package algo;

import java.util.Scanner;

public class Gauss {
    public static void main(String[] args) {
        // 가우스 연산 - 공식 s = n * (a + l) / 2

        Scanner sc = new Scanner(System.in); //5,6,7,8,9,10 직접 계산해서 검증해보기
        
        //샘플링할 때 2000처럼 큰 수가 아니라 작은 수를 통해 테스트
        // 1. 총합 s 필요
        int s = 0;

        // 2. 첫 항 a 필요
        System.out.print("첫 항을 입력하세요: "); 
        int a = sc.nextInt();

        // 3. 마지막 항 l 필요
        System.out.print("마지막 항을 입력하세요: ");
        int l = sc.nextInt();

        // 4. 항의 개수 n 필요
        int n = l - a + 1;

        // 5. 공식 적용해서 더하고
        s = n * (a + l) / 2;

        // 6. s 출력
        System.out.println("s: " + s);
    }
}