1강. 알고리즘 소개

1. 알고리즘 소개

---

1.1 알고리즘의 정의와 중요성

알고리즘의 정의
알고리즘(Algorithm)은 문제를 해결하기 위해 정해진 일련의 절차나 규칙의 집합입니다. 쉽게 말해, 알고리즘은 특정 문제를 해결하는 데 필요한 단계별 과정입니다.
알고리즘은 컴퓨터 과학의 핵심 요소로, 문제를 효율적으로 해결하는 방법을 제공합니다. 예를 들어, 데이터 정렬, 검색, 최적화 문제 등을 해결하기 위해 다양한 알고리즘이 사용됩니다.

역사적 배경
알고리즘이라는 용어는 페르시아의 수학자 알-콰리즈미(Al-Khwarizmi)의 이름에서 유래되었습니다. 그는 9세기 초에 산술 연산 방법을 체계화한 책을 썼습니다. 이 책은 유럽에 전파되어 알고리즘이라는 용어의 기초가 되었습니다.
현대 컴퓨터 과학에서 알고리즘의 중요성은 앨런 튜링(Alan Turing)과 클로드 섀넌(Claude Shannon) 등의 연구를 통해 더욱 강조되었습니다. 이들은 컴퓨터와 정보 이론의 기초를 다졌습니다.

알고리즘의 중요성
효율성: 효율적인 알고리즘은 자원을 적게 사용하며 빠르게 동작합니다. 이는 특히 대규모 데이터 처리나 실시간 시스템에서 중요합니다.
예: 퀵 정렬(Quick Sort)은 평균적으로 O(n log n) 시간 복잡도를 가지며, 많은 데이터 정렬 문제에서 효율적입니다.

가독성: 잘 설계된 알고리즘은 다른 사람들이 이해하고 유지 보수하기 쉽습니다. 이는 협업 프로젝트에서 특히 중요합니다.
예: 이진 탐색(Binary Search)은 간결하고 명확한 코드로 구현할 수 있습니다.

재사용성: 좋은 알고리즘은 다양한 문제에서 재사용될 수 있습니다.
예: 다익스트라 알고리즘(Dijkstra's Algorithm)은 그래프의 최단 경로 문제에 널리 사용됩니다.

문제 해결 능력: 알고리즘을 통해 문제를 체계적으로 해결할 수 있는 능력을 기를 수 있습니다.

예시
문제: 주어진 배열에서 최대값을 찾는 알고리즘
입력: [3, 5, 2, 7, 1]
출력: 7

알고리즘
1. 배열의 첫 번째 원소를 최대값으로 초기화한다.
2. 배열의 두 번째 원소부터 마지막 원소까지 반복하면서, 현재 최대값보다 큰 원소를 찾으면 최대값을 갱신한다.
3. 반복이 끝나면 최대값을 출력한다.

public class MaxValue {
    public static int findMax(int[] arr) {
        int max = arr[0]; // 첫 번째 원소를 최대값으로 초기화
        for (int i = 1; i < arr.length; i++) { // 두 번째 원소부터 반복
            if (arr[i] > max) {
                max = arr[i]; // 최대값 갱신
            }
        }
        return max; // 최대값 반환
    }

    public static void main(String[] args) {
        int[] arr = {3, 5, 2, 7, 1};
        System.out.println("Maximum value: " + findMax(arr)); // 출력: 7
    }
}

1.2 알고리즘 분석 기초

시간 복잡도(Time Complexity)
알고리즘이 수행되는 데 걸리는 시간을 나타내며, 입력 크기 \(n\)에 대한 함수로 표현됩니다.

빅오 표기법(Big-O Notation): 가장 자주 사용되는 표기법으로, 최악의 경우 수행 시간을 나타냅니다.
예: \(O(1)\), \(O(n)\), \(O(n^2)\), \(O(\log n)\), \(O(n \log n)\)

시간 복잡도 예시:
상수 시간 복잡도 \(O(1)\): 입력 크기에 상관없이 일정한 시간이 소요되는 알고리즘.
예: 배열에서 첫 번째 원소를 반환하는 연산.

선형 시간 복잡도 \(O(n)\): 입력 크기에 비례하여 시간이 증가하는 알고리즘.
예: 배열에서 최대값을 찾는 알고리즘.

이차 시간 복잡도 \(O(n^2)\): 이중 루프를 사용하는 알고리즘.
예: 버블 정렬, 선택 정렬.

로그 시간 복잡도 \(O(\log n)\): 이진 탐색 알고리즘.

선형 로그 시간 복잡도 \(O(n \log n)\): 병합 정렬, 퀵 정렬.

공간 복잡도(Space Complexity)
알고리즘이 사용하는 메모리 공간을 나타냅니다.
입력 데이터와 알고리즘이 필요로 하는 추가 공간을 모두 고려합니다.

공간 복잡도 예시:
상수 공간 복잡도 \(O(1)\): 추가 메모리를 거의 사용하지 않는 알고리즘.

선형 공간 복잡도 \(O(n)\): 입력 크기에 비례하는 추가 메모리를 사용하는 알고리즘.
예: 피보나치 수열을 재귀적으로 계산할 때, 메모이제이션 기법 사용 시.

예시: 버블 정렬의 시간 복잡도 분석
버블 정렬은 인접한 두 원소를 비교하여 정렬하는 알고리즘입니다.
최악의 경우, 배열의 모든 원소를 반복적으로 비교해야 하므로 시간 복잡도는 \(O(n^2)\)입니다.

public class BubbleSort {
    public static void bubbleSort(int[] arr) {
        int n = arr.length;
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Swap arr[j] and arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 34, 25, 12, 22, 11, 90};
        bubbleSort(arr);
        System.out.println("Sorted array: ");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

설명:
버블 정렬: 인접한 원소를 비교하여 정렬하는 알고리즘.
시간 복잡도: 최악의 경우 \(O(n^2)\).
공간 복잡도: 추가적인 메모리 사용 없이 배열 내에서 정렬하므로 \(O(1)\).

1.3 알고리즘 설계 패러다임

분할 정복(Divide and Conquer)
문제를 더 작은 하위 문제로 나누어 해결한 후, 이를 합쳐서 전체 문제를 해결하는 방법입니다.
역사적 배경: 분할 정복 기법은 고대 수학자들에게도 사용되었으며, 현대 컴퓨터 과학에서는 퀵 정렬(Quick Sort)과 병합 정렬(Merge Sort)과 같은 알고리즘에서 널리 사용됩니다.
분할 정복이 필요한 이유: 분할 정복은 문제를 더 작은 부분으로 나누어 해결함으로써 복잡한 문제를 단순화하고, 더 빠르고 효율적인 알고리즘을 설계할 수 있게 합니다.
예시: 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort)

동적 계획법(Dynamic Programming)
문제를 겹치는 하위 문제로 나누고, 각 하위 문제의 해를 저장하여 동일한 계산을 반복하지 않도록 하는 방법입니다.
역사적 배경: 동적 계획법은 1950년대 리처드 벨만(Richard Bellman)이 최적화 문제를 해결하기 위해 개발했습니다.
동적 계획법이 필요한 이유: 동적 계획법은 중복되는 계산을 줄이고, 복잡한 문제를 효율적으로 해결할 수 있게 합니다.
예시: 피보나치 수열, 배낭 문제

그리디 알고리즘(Greedy Algorithm)
매 단계에서 가장 최적의 선택을 하는 방법으로, 전체적으로도 최적의 해를 보장하는 알고리즘입니다.
역사적 배경: 그리디 알고리즘은 1950년대와 1960년대에 다양한 최적화 문제를 해결하는 데 사용되었습니다.
그리디 알고리즘이 필요한 이유: 그리디 알고리즘은 단순하고 빠르게 최적의 해를 찾을 수 있으며, 복잡한 문제를 단계별로 해결할 수 있게 합니다.
예시: 최단 경로 문제(다익스트라 알고리즘), 최소 신장 트리(크루스칼 알고리즘)

백트래킹(Backtracking)
가능한 모든 해를 탐색하는 방법으로, 해가 될 가능성이 없는 경로를 빨리 배제합니다.
역사적 배경: 백트래킹 기법은 1960년대에 조지 다이칵(George Dantzig)과 같은 수학자들에 의해 개발되었습니다.
백트래킹이 필요한 이유: 백트래킹은 모든 가능한 해를 탐색하여 최적의 해를 찾는 데 유용하며, 복잡한 문제를 효율적으로 해결할 수 있게 합니다.
예시: N-Queens 문제, 순열 생성

import java.util.Arrays;

public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            int middle = (left + right) / 2;
            mergeSort(arr, left, middle);
            mergeSort(arr, middle + 1, right);
            merge(arr, left, middle, right);
        }
    }

    public static void merge(int[] arr, int left, int middle, int right) {
        int n1 = middle - left + 1;
        int n2 = right - middle;

        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];

        for (int i = 0; i < n1; i++)
            leftArray[i] = arr[left + i];
        for (int j = 0; j < n2; j++)
            rightArray[j] = arr[middle + 1 + j];

        int i = 0, j = 0;
        int k = left;
        while (i < n1 && j < n2) {
            if (leftArray[i] <= rightArray[j]) {
                arr[k] = leftArray[i];
                i++;
            } else {
                arr[k] = rightArray[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = leftArray[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = rightArray[j];
            j++;
            k++;
        }
    }

    public static void main(String[] args) {
        int[] arr = {12, 11, 13, 5, 6, 7};
        System.out.println("Given Array");
        System.out.println(Arrays.toString(arr));
        
        mergeSort(arr, 0, arr.length - 1);
        
        System.out.println("\nSorted array");
        System.out.println(Arrays.toString(arr));
    }
}

설명:
분할 정복: 문제를 작은 하위 문제로 나누어 해결.
병합 정렬: 배열을 재귀적으로 나누고 병합하여 정렬.
시간 복잡도: \(O(n \log n)\).
공간 복잡도: 추가적인 배열 공간 사용으로 \(O(n)\).

 

public class CoinChange {
    public static int coinChange(int[] coins, int amount) {
        int count = 0;
        for (int i = coins.length - 1; i >= 0; i--) {
            while (amount >= coins[i]) {
                amount -= coins[i];
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[] coins = {1, 5, 10, 25};
        int amount = 63;
        System.out.println("Minimum coins required: " + coinChange(coins, amount)); // 출력: 6
    }
}

설명:
그리디 알고리즘: 매 단계에서 가장 큰 동전을 선택하여 최소한의 동전으로 거스름돈을 제공합니다.
시간 복잡도: \(O(n)\).
공간 복잡도: \(O(1)\).