그리디 알고리즘

그리디 알고리즘은 '탐욕법'이라고도 불리는데 여기에선 그리디 알고리즘으로 사용하겠습니다.

그리디 알고리즘은 해를 구하는 과정에서 각 단계마다 '가장 최선'의 최적해를 선택해 나가면서 결과적으로 전체적인 최적의 해를 구하려는 알고리즘입니다.

하지만 각 단계마다 최적의 해를 구한다고해서 전체의 최적해를 만들지 못할 수도 있습니다. 즉 전체적인 최적의 해를 보장하지 않는다는 말입니다.

예를들어, S에서 시작해서 E에 도착할때까지의 수의 합이 가장 높은 노선을 구해봅시다.

S에서 시작해서 E까지의 노선중에서 수의 합이 가장 높은 노선은 S - 3 - 8 - E 이고 합은 11이라는것을 바로 알 수 있을 것입니다.

하지만 그리디 알고리즘을 적용해보면

S - 5 - 3 - E 라는 결과가 나왔습니다. 각 노선을 선택할 때마다 가장 높은 수를 선택했지만 최적해인 11에 미치지 못하는 8이 되었습니다. 따라서 그리디 알고리즘은 현재에서 가장 최선의 값을 선택하지만 그것이 항상 최적의 값을 보장하지 않는 알고리즘입니다.

그리디 알고리즘 예제

대표적인 문제로는 거스름돈 문제가 있습니다. 거스름돈에 사용되는 동전의 개수를 최소로 하는 문제입니다.

    public static void main(String[] args) {

        Integer[] coins = {100, 50, 10, 500}; // 동전
        int money = 780; // 거스름돈
        int count = 0; // 동전 사용 개수

        // 사용할 동전을 액수가 큰 순서대로 정렬
        Arrays.sort(coins, Comparator.reverseOrder());

        // 차례대로 거스름돈에서 차감
        for (int coin : coins) {
            count += money / coin;
            money %= coin;
        }

        // 결과 출력
        if (money == 0) {
            System.out.println("결과 count = " + count);
        }

    }

버블정렬

특징

• 안정정렬 (stable sort) 이다 
• 추가적인 공간이 필요하지 않은 제자리 정렬( in-place sort ) 이다

시간복잡도

장점

1. 구현이 매우 쉽다.
2. 추가적인 메모리 소비가 적다.
3. 안정정렬이다.

단점

1. 정렬하는데 오랜시간이 걸린다. (시간복잡도가 높다)

정렬방법

1. 현재 원소와 다음 원소를 비교한다.
2. 현재 원소 > 다음 원소 이면 둘의 위치를 바꾼다.
3. 다음 원소로 이동한다.

유튜브 영상으로도 버블정렬을 확인할 수 있습니다.

자바로 구현

기본 버블정렬

public class Bubble_Sort {

    public static void main(String[] args) {
        int[] array = {5, 3, 1, 4, 2};
        System.out.printf("초기배열 : {%d, %d, %d, %d, %d} \n", array[0], array[1], array[2], array[3], array[4]);
        bubble_sort(array);
        System.out.printf("정렬된배열 : {%d, %d, %d, %d, %d} \n", array[0], array[1], array[2], array[3], array[4]);
    }

    private static void bubble_sort(int[] array) {
        // i 는 위 그림의 Round와 같음
        for (int i = 1; i < array.length; i++) {

            // Round별 비교횟수는 Round가 증가함에 따라 횟수가 줄어듬
            for (int j = 0; j < array.length - i; j++) {

                // 현재원소가 다음원소보다 크다면 두개의 값을 변경한다.
                if (array[j] > array[j + 1]) {
                    swap(array, j);
                }
            }
        }
    }

    private static void swap(int[] array, int index) {
        int temp = array[index];
        array[index] = array[index + 1];
        array[index + 1] = temp;
    }
}

최적화된 버블정렬

public class Bubble_Sort {

    public static void main(String[] args) {
        int[] array = {5, 3, 1, 4, 2};
        System.out.printf("초기배열 : {%d, %d, %d, %d, %d} \n", array[0], array[1], array[2], array[3], array[4]);
        bubble_sort(array);
        System.out.printf("정렬된배열 : {%d, %d, %d, %d, %d} \n", array[0], array[1], array[2], array[3], array[4]);
    }

    private static void bubble_sort(int[] array) {
        // i == 위 그림의 Round와 같음
        for (int i = 1; i < array.length; i++) {

            boolean isSwapped = false;

            // Round별 비교횟수는 Round가 증가함에 따라 횟수가 줄어듬
            for (int j = 0; j < array.length - i; j++) {

                // 현재원소가 다음원소보다 크다면 두개의 값을 변경한다.
                if (array[j] > array[j + 1]) {
                    swap(array, j);
                    isSwapped = true;
                }
            }

            // 비교과정에서 한번도 교환이 이루어지지않았다면 반복문 종료
            if (!isSwapped) {
                break;
            }

        }
    }

    private static void swap(int[] array, int index) {
        int temp = array[index];
        array[index] = array[index + 1];
        array[index + 1] = temp;
    }
}