항해99 11/11(목) 알고리즘

기본적인 지식은 이미 있기에 메모할만한 것만 정리해놓으려고 한다.

 

 

이진 탐색(binary search)

- 시간복잡도는O(logN). 매우 빠르다.

- 하지만 반드시 데이터가 정렬된 상태에서만 사용할 수 있다.

public static boolean binarySearch(int[] arr, int target){
        boolean result = false;
        int min_idx = 0;
        int max_idx = arr.length-1;

        while(min_idx <= max_idx){
            // 항상 중간지점을 idx로 지정
            int idx = (min_idx + max_idx)/2;
            // 찾으면 true 반환
            if(arr[idx] == target){
                result = true;
                break;
            }else if(arr[idx] > target){
                // target보다 크면 max_idx가 내려옴
                max_idx = idx-1;
            }else if(arr[idx] < target){
                // target보다 작으면 min_idx가 올라옴
                min_idx = idx+1;
            }
        }

        return result;
    }

 

 

버블 정렬(Bubble Sort)

- 시간복잡도는 O(n^2)

- 바로 옆 값과 비교해 좌측의 값이 더 클 경우 값을 교체하는 식으로 정렬한다.

- 내림차순으로 정렬하고싶은경우 좌측의 값이 더 작으면 교체하도록 하면 된다.

public static int[] bubble_sort(int[] arr){
        for(int i = 0; i < arr.length; i++){
            // 버블 정렬은 매 순서의 마지막 회차에 가장 높은 수가 오기 때문에 마지막 위치를 순차적으로 -1 해주면 효율이 올라감.
            for(int k = 0; k < arr.length - i - 1; k++){
                if(arr[k] > arr[k+1]){
                    int temp = arr[k];
                    arr[k] = arr[k+1];
                    arr[k+1] = temp;
                }
            }
        }

        return arr;
    }

 

 

선택 정렬(Selection Sort)

- 버블 정렬과 원리는 다르지만 시간복잡도는 같다.

- 내림차순 하고싶을때는 끝 인덱스부터 시작해서 비슷한 원리로 구현하면 된다.

- 효율성을 높이고 싶으면 매번 교체하는게 아니라 anchor 변수를 하나 달아서 내부 for문이 끝날 때마다 한 번만 교체해주도록 하면 된다.

public static int[] selection_sort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int k = i + 1; k < arr.length; k++) {
                // i보다 k가 작으면 arr[i]와 arr[k]를 교체
                if(arr[i] > arr[k]){
                    int temp = arr[i];
                    arr[i] = arr[k];
                    arr[k] = temp;
                }
            }
        }

        return arr;
    }

 

 

삽입 정렬(Insertion Sort)

- 시간복잡도 역시 똑같다

- 앞의 인덱스와 비교해 뒤로 밀어냄으로써 정렬된 상태를 고정시키면서 정렬을 시행하는 정렬이다.

- 효율 증가를 원한다면 적절한 위치에 break 조건을 걸어주면 될 것이다.

- 내가 보기엔 코드가 쓰잘데기없이 복잡하다.....

public static int[] insertion_sort(int[] arr) {
        // 앞 인덱스와 비교할 것이기 때문에 1부터 시작
        for (int i = 1; i < arr.length; i++) {
            for (int k = i; k < i; k++) {
                // arr[i-k-1]보다 arr[i-k]가 작으면 교체
                if(arr[i-k-1] > arr[i-k]){
                    int temp = arr[i-k-1];
                    arr[i-k-1] = arr[i-k];
                    arr[i-k] = temp;
                }
            }
        }

        return arr;
    }

 

 

합병 정렬(Merge Sort)

- 시간복잡도가 낮다

- 하지만 이미 정렬되어있는 배열을 합쳐야 한다는 전제조건이 있다

- 크기가 같은 배열로 비교한 걸로 예를 들었지만, 사실 크기가 같지 않아도 문제 없다.

public static int[] merge_sort(int[] arr1, int[] arr2) {
        // arr1과 arr2는 이미 정렬된 상태
        // 빈 배열 list에 arr1, arr2 값을 비교해가며 삽입
        // 1. arr1[0] < arr2[0] => list.add(arr1[0]), arr1 index++;
        // 2. arr1[1] > arr2[0] => list.add(arr2[0]), arr2 index++;
        // ...
        // n. arr1[END] < arr2[REMAINDER] => list.add(arr1[END]), list.add(arr2[REMAINDER]);

        ArrayList<Integer> list = new ArrayList<>();

        int arr1_idx = 0;
        int arr2_idx = 0;
        while(true){
            // 둘 중 하나의 배열이 마지막에 도달했을 때 다른 쪽의 값을 다 털어내기 위함
            if(arr1_idx >= arr1.length){
                if(arr2_idx < arr2.length){
                    list.add(arr2[arr2_idx++]);
                    continue;
                }else{
                    break;
                }
            }else if(arr2_idx >= arr2.length){
                if(arr1_idx < arr1.length){
                    list.add(arr1[arr1_idx++]);
                    continue;
                }else{
                    break;
                }
            }
            //    [1 3 4 8] [2 6 9 10] []
            // -> [3 4 8] [2 6 9 10] [1]
            // -> [3 4 8] [6 9 10] [1 2]
            // -> [4 8] [6 9 10] [1 2 3]
            // -> [8] [6 9 10] [1 2 3 4]
            // -> [8] [9 10] [1 2 3 4 6]
            // -> [] [9 10] [1 2 3 4 6 8]
            // -> [] [] [1 2 3 4 6 8 9 10]

            if(arr1[arr1_idx] < arr2[arr2_idx]){
                list.add(arr1[arr1_idx++]);
            }else{
                list.add(arr2[arr2_idx++]);
            }
        }

        return list.stream().mapToInt(i->i).toArray();
    }

 

 

 

분할 정복(Divide and Conquer)

- 하나의 문제를 분할해 각자 처리하는 방식

- 예를 들어, 위의 합병 정렬을 수행하기 위해 하나의 배열을 반으로 쪼개고 쪼개고 쪼개서 하나씩만 남겨 정렬된(것으로 정의하는) 상태로 만들어주고 이걸 다시 합병정렬 해주고 해주고 해주는 것.

       -   [1 3 4 7 6 2 5 8]

분할 -> [1 3 4 7] [6 2 5 8]

분할 -> [1 3] [4 7] [6 2] [5 8]

분할 -> [1] [3] [4] [7] [6] [2] [5] [8]

합병 -> [1 3] [4 7] [2 6] [5 8]

합병 -> [1 3 4 7] [2 5 6 8]

합병 -> [1 2 3 4 5 6 7 8]

 

재귀함수를 이용하면 이런 모양새를 만들 수 있을 것이다.

public int[] divide_merge_sort(int[] arr) {
        if(arr.length <= 1){
            return arr;
        }

        int mid = arr.length / 2;
        // 나누어지지 않을 때까지 절반으로 나눠서 분할
        int[] arr1 = divide_merge_sort(Arrays.copyOfRange(arr, 0, mid));
        int[] arr2 = divide_merge_sort(Arrays.copyOfRange(arr, mid, arr.length));

        // 정복
        int[] res = MergeSort.merge_sort(arr1, arr2);

        return res;
    }

위에 있는 MergeSort와 함께 연계해서 구현해본 합병정렬이다. 이젠 큰 배열 하나만 들어가도 된다.