[Java] 26. 알고리즘이 필요한 이유

백하림

Feb 06, 2025

Contents

1. 전체 탐색 2. 가우스 연산

1. 전체 탐색

❗

BruteForce (무작정 더하기(for문을 돌며) ) BruteForce란? 조합 가능한 모든 문자열을 하나씩 대입해 보는 방식으로 암호를 해독하는 방법 (무식)


package algo;

public class BruteForce {
    public static void main(String[] args) {
        // O(n) 시간 복잡도
        int n = 1000000;
        int sum = 0;
        for (int i = 1; i <= n; i++) { // 모든 숫자를 더함.
            sum = sum + i; // 누적 식
        }
        System.out.println("합 : " + sum);
    }
}

2. 가우스 연산

❗

sum : 총합

n : 항의 개수 (10개)

a : 첫 번째 항 (1)

l : 마지막 항 (10)


package algo;

public class Gauss {
    public static void main(String[] args) {
        //가우스 연산 - 공식 sum = n * (a+l) / 2
        
        // 1. 총값 저장
        int sum = 0;

        // 2. n값 저장(항의 개수)
        int n = 10;

        // 3. a값 저장(첫번째 항)
        int a = 1;

        // 4. l값 저장(마지막 항)
        int l = 10;

        // 5. 가우스 연산
        sum = (n * (a + l)) / 2;

        // 6. 총값 출력
        System.out.println("합계 : " + sum);
    }
}

🔍 BruteForce vs 가우스 소거법 (Gaussian Elimination) 🤖

항목	BruteForce (완전 탐색) 🧠	가우스 소거법 (Gaussian Elimination) 📊
알고리즘 설명	가능한 모든 해를 탐색하여 답을 찾는 방법 🔎	선형 방정식을 풀기 위한 연립방정식의 가우스 소거법 사용 🔢
시간 복잡도	O(n!)O(n!)O(n!) 또는 O(2n)O(2^n)O(2n), 문제에 따라 다름 ⏳	O(n3)O(n^3)O(n3), 연립방정식의 차원에 비례 📈
공간 복잡도	매우 높은 공간 복잡도를 가질 수 있음 🧳	상대적으로 적은 공간 복잡도를 가짐 📦
정확성	정확한 해를 찾지만 계산 비용이 매우 높음 ⚖️	정확한 해를 제공 ✅
적합한 문제 유형	해의 탐색을 반복적으로 해야 하는 문제에 적합 🧩	선형 방정식이 주어졌을 때, 특히 행렬이 주어졌을 때 적합 🏗️
장점	- 모든 가능한 해를 탐색하여 정확한 결과를 얻을 수 있음 🌟	- 비교적 효율적으로 선형 방정식을 풀 수 있음 ⚙️
단점	- 시간과 공간의 제약으로 인해 큰 문제에서는 매우 비효율적 😓	- 계산이 복잡하고, 대형 행렬을 다룰 때 수치적으로 불안정할 수 있음 ⚠️
상황에 따른 선택	작은 문제에서 정확한 해를 찾을 때 유리 📏	중대형 크기의 선형 방정식을 풀 때 더 효율적 🔧

package algo; public class BruteForce { public static void main(String[] args) { // O(n) 시간 복잡도 int n = 1000000; int sum = 0; for (int i = 1; i <= n; i++) { // 모든 숫자를 더함. sum = sum + i; // 누적 식 } System.out.println("합 : " + sum); } }

package algo; public class Gauss { public static void main(String[] args) { //가우스 연산 - 공식 sum = n * (a+l) / 2 // 1. 총값 저장 int sum = 0; // 2. n값 저장(항의 개수) int n = 10; // 3. a값 저장(첫번째 항) int a = 1; // 4. l값 저장(마지막 항) int l = 10; // 5. 가우스 연산 sum = (n * (a + l)) / 2; // 6. 총값 출력 System.out.println("합계 : " + sum); } }