'분류 전체보기'에 해당되는 글 20건

문제: 두개의 트리를 하나의 트리로 병합할것

조건: 같은 레벨에 있는 노드의 값은 더하여 하나로 만든다. 

주의: 병합의 시작점은 두 트리의 root 부터 시작한다. 

2개의 트리를 모두 확인해야하기 때문에 재귀를 이용하거나 스택을 이용할 수 있다. 

재귀는 아래와 같이 구현한다. 

public class MergeTwoBinaryTrees {

    public static TreeNode mergeTrees(TreeNode t1, TreeNode t2) {
    	// 두개의 노드중 하나에 값이 없는 경우 체크
        if (t1 == null)
            return t2;
        if (t2 == null) {
            return t1;
        }
        
        // 둘다 값이 있는 경우 첫번째 노드에 값을 더한다.
        t1.val += t2.val;
        // 재귀를 통해서 좌측 및 우측 노드에 값을 할당한다.
        t1.left = mergeTrees(t1.left, t2.left);
        t1.right = mergeTrees(t1.right, t2.right);
        return t1;
    }
}

퀵 정렬

 퀵 정렬은 평균적으로 가장 좋은 성능을 가져 현장에서 가장 많이 쓰는 정렬 알고리즘이다. 

정렬 방식

 정렬할 배열에서 "기준원소"를 하나 고른다. 아무 원소나 임의로 골라도 되나 여기서는 맨 뒤의 원소를 기준원소로 삼기로 한다. 이 기준원소를 중심으로 더 작거나 같은 수는 왼쪽으로, 큰 수는 오른쪽으로 재배치한다. 기준원소는 이렇게 분할된 양쪽 부분 배열 사이에 자리하게 된다. 이렇게 분할된 왼쪽 부분 배열을 따로 정렬한다. 마찬가지로 오른쪽 부분 배열도 따로 정렬한다. 기준원소는 손대지 말고 제자리에 그대로 둔다. 기준원소의 왼쪽에 기준원소보다 작은 원소들이 정렬되어 있고, 오른쪽에 기준원소보다 큰 원소들이 정렬되어 있으면 전체 배열은 정렬된 것이다. 여기서 왼쪽과 오른쪽 부분 배열을 정렬할 때 퀵 정렬을 재귀적으로 사용한다. 

퀵 정렬 구현

public class QuickSort {

	private static void quickSort(int[] arr) {
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int start, int end) {
        int part2 = partition(arr, start, end);
        if (start < part2 - 1) {
            quickSort(arr, start, part2 - 1);
        }
        if (part2 < end) {
            quickSort(arr, part2, end);
        }
    }

    private static int partition(int[] arr, int start, int end) {
        int pivot = arr[(start + end) / 2]; // 중간값으로 pivot 설정하는 경우
        while (start <= end) {
            while (arr[start] < pivot) start++;
            while (arr[end] > pivot) end--;
            if (start <= end) {
                swap(arr, start, end);
                start++;
                end--;
            }
        }
        return start;
    }

    private static void swap(int[] arr, int start, int end) {
        int tmp = arr[start];
        arr[start] = arr[end];
        arr[end] = tmp;
    }
}

병합 정렬

  병합 정렬은 먼저 입력을 반으로 나눈다. 이렇게 나눈 전반부와 후반부를 각각 독립적으로 정렬한다. 마지막으로 정렬된 두 부분을 합쳐서, 즉 병합하여 정렬된 배열을 얻는다. 여기서 전반부를 정렬할 때도 역시 반으로 나눈 다음 정렬해서 병합한다. 즉, 원래의 정렬 문제와 성격이 똑같고 단지 크기만 반으로 줄었을 뿐이다. 후반부에 대한 정렬도 마찬가지다. 병합 정렬은 자신에 비해 크기가 반인 문제를 두 개 푼 다음, 이들을 병합하는 일을 재귀적으로 반복한다. 

병합 정렬 구현

public class MergeSort {

    public static void main(String[] args) {
        int[] arrays = {6, 3, 1, 21};
        mergeSort(arrays, 0, arrays.length - 1);
    }

    private static void mergeSort(int[] arrays, int p, int r) {
        if (p < r) {
            int mid = (p + r) / 2;
            mergeSort(arrays, p, mid);
            mergeSort(arrays, mid + 1, r);
            merge(arrays, p, mid, r);
        }
    }

    private static void merge(int[] arrays, int p, int mid, int r) {
        int i = p;
        int j = mid + 1;
        int k = p;
        int[] temp = new int[arrays.length];
        while (i <= mid && j <= r) {
            if (arrays[i] < arrays[j]) {
                temp[k++] = arrays[i++];
            } else {
                temp[k++] = arrays[j++];
            }
        }
        while (i <= mid)
            temp[k++] = arrays[i++];
        while (j <= r)
            temp[k++] = arrays[j++];
        for (int index = p; index < k; index++) {
            arrays[index] = temp[index];
        }
    }
}

삽입 정렬

  삽입 정렬은 이미 정렬되어 있는 i개짜리 배열에 하나의 원소를 더 더하여 정렬된 i+1 개짜리 배열을 만드는 과정을 반복한다.

O(n제곱) 시간이 드는 비효율적인 정렬 알고리즘군에 속하지만 배열이 거의 정렬되어 있는 상태로 입력되는 경우에는 가장 매력적인 알고리즘이 된다. 이유는  현재 값이 이전 값보다 작을 경우를 찾는 반복문이 거의 실행되지 않기 때문이다. 

삽입 정렬 구현

public class InsertionSort {

    public static void main(String[] args) {
        int[] arrays = {5, 3, 4, 7, 6, 2, 1};

        int newItem;
        int loc;

        for (int i = 1; i < arrays.length; i++) {
            newItem = arrays[i];
            loc = i;
            while (loc > 0 && newItem < arrays[loc - 1]) {
                arrays[loc] = arrays[loc - 1];
                loc--;
            }
            arrays[loc] = newItem;
        }
    }
}