Java ch11-2 Recursion Programming

바로 한 가지 CountDown코드를 보겠습니다.

import java.util.Scanner;
public class CountDown
{
    private int count;
    public static void main(String[] args)
    {
        CountDown countDowner = new CountDown();
        countDowner.getCount( );
        countDowner.showCountDown( );
    }
    public void getCount( )
    {
        System.out.println("Enter a positive integer:");
        Scanner keyboard = new Scanner(System.in);
        count = keyboard.nextInt( );
        if (count <= 0)
        {
            System.out.println("Input must be positive.");
            System.out.println("Try again.");
            getCount( );//start over
        }
    }
    public void showCountDown( )
    {
        System.out.println("Counting down:");
        for (int left = count; left >= 0; left--)
        System.out.print(left + ", ");
        System.out.println("Blast Off!");
    }
}

그냥 보여드리고 싶었습니다.

그리고 이전 챕터에서 보았던 전화번호부 알고리즘에서 사용된 이진 알고리즘, binary search algorithm에 대해 얘기해봅시다.

• 리스트에서 특정 값 찾기는 매우 흔한 문제입니다. 검색은 철저히 연구된 주제이며, 순차 검색(sequential search)과 이진 검색(binary search)이 두 가지 일반적인 검색 알고리즘입니다.

• 순차 검색은 비효율적이지만 이해하고 프로그래밍하기 쉽습니다. 리스트를 처음부터 끝까지 차례로 검색하여 원하는 값을 찾습니다.

• 이진 검색은 순차 검색보다 효율적입니다. 하지만 리스트가 먼저 정렬되어 있어야만 작동합니다. 이진 검색 알고리즘의 의사코드는 "전화번호부에서 이름 찾기" 문제의 예시입니다. 전화번호부의 이름은 이미 정렬되어 있으므로 이진 검색 알고리즘을 사용할 수 있습니다.

sequential 과 binary

• 순차 검색(Sequential search): 리스트에서 값이 읽힐 때마다 그 값이 "목표(target)" 값이 아닌 경우, 리스트에서는 한 항목만 제외됩니다.

• 이진 검색(Binary search): 리스트에서 값이 읽힐 때마다 그 값이 "목표(target)" 값이 아닌 경우, 리스트의 절반을 제외합니다! 이것이 이진 검색이라 불리는 이유입니다. 목표 값에 대한 각 실패적인 테스트마다 검색할 남은 리스트가 절반으로 줄어듭니다.

• 이로써 이진 검색은 순차 검색보다 훨씬 더 빠른 검색 속도를 가질 수 있는 이유입니다. 검색할 대상을 절반씩 줄여가기 때문에 많은 항목들을 한 번에 제거할 수 있습니다.

private int search(int target, int first, int last)    
{        
    int result = -1;
    //to keep the compiler happy.        
    int mid;        
    if (first > last)            
    result = -1;        
    else        
    {            
        mid = (first + last)/2;            
        if (target == a[mid])                
        result = mid;            
        else if (target < a[mid])                
        result = search(target, first, mid - 1);            
        else //(target > a[mid])                
        result = search(target, mid + 1, last);        
    }        
    return result;    
}
/*binary algorithm의 골격*/

Merge sort

• 병합 정렬(Merge Sort)은 배열을 정렬하기 위한 재귀적인 방법 중 하나입니다. 이 알고리즘은 "분할 정복(Divide and Conquer)"이라고 불리는 접근 방식을 사용합니다.

• 병합 정렬의 동작 방식은 다음과 같습니다. 먼저, 정렬하고자 하는 배열을 두 부분으로 나눕니다. 그리고 각각의 부분 배열을 재귀적으로 다시 정렬합니다. 이후 정렬된 두 부분 배열을 병합하여 최종적으로 정렬된 배열을 얻게 됩니다.

• 구체적인 알고리즘은 다음과 같습니다.

1. 만약 정렬하려는 배열이 하나의 요소만을 가지고 있다면, 아무런 작업을 수행하지 않고 그대로 반환합니다. 이것을 종료 조건으로 삼습니다.
2. 그렇지 않다면, 배열을 두 부분으로 나눕니다. 첫 번째 절반을 작은 배열인 "front"에 복사하고, 나머지 절반을 작은 배열인 "tail"에 복사합니다.
3. "front" 배열과 "tail" 배열을 각각 재귀 호출을 사용하여 정렬합니다. 이 단계에서는 위의 과정을 반복하여 더 이상 나눌 수 없을 때까지 계속해서 부분 배열을 정렬합니다.
4. 마지막으로, 정렬된 "front" 배열과 "tail" 배열을 병합하여 최종적으로 정렬된 배열을 얻습니다.

• 이렇게 병합 정렬을 사용하면 배열을 효과적으로 정렬할 수 있습니다. 이 알고리즘은 재귀적인 방법을 사용하므로 코드가 간결하고 이해하기 쉬우며, 정확한 정렬 결과를 얻을 수 있습니다. 하지만 큰 규모의 배열에 대해서는 약간의 추가적인 메모리 공간과 실행 시간이 필요할 수 있습니다. 따라서 효율성이 중요한 상황에서는 다른 정렬 알고리즘을 고려해야 할 수도 있습니다.

public class MergeSortDemo {
    public static void main(String[] args) {
        int[] anArray = {7, 5, 11, 2, 16, 4, 18, 14, 12, 30};
        System.out.println("Array values before sorting:");
        for (int i = 0; i < anArray.length; i++)
            System.out.print(anArray[i] + " ");
        System.out.println();
        MergeSort.sort(anArray);
        System.out.println("Array values after sorting:");
        for (int i = 0; i < anArray.length; i++)
            System.out.print(anArray[i] + " ");
        System.out.println();
    }
}

public class MergeSort {
    public static void sort(int[] a) {
        if (a.length >= 2) {
            int halfLength = a.length / 2;
            int[] firstHalf = new int[halfLength];
            int[] lastHalf = new int[a.length - halfLength];
            divide(a, firstHalf, lastHalf);
            sort(firstHalf);
            sort(lastHalf);
            merge(a, firstHalf, lastHalf);
        }
    }

    private static void divide(int[] a, int[] firstHalf, int[] lastHalf) {
        for (int i = 0; i < firstHalf.length; i++)
            firstHalf[i] = a[i];
        for (int i = 0; i < lastHalf.length; i++)
            lastHalf[i] = a[firstHalf.length + i];
    }

    private static void merge(int[] a, int[] firstHalf, int[] lastHalf) {
        int firstHalfIndex = 0, lastHalfIndex = 0, aIndex = 0;
        while ((firstHalfIndex < firstHalf.length) && (lastHalfIndex < lastHalf.length)) {
            if (firstHalf[firstHalfIndex] < lastHalf[lastHalfIndex]) {
                a[aIndex] = firstHalf[firstHalfIndex];
                firstHalfIndex++;
            } else {
                a[aIndex] = lastHalf[lastHalfIndex];
                lastHalfIndex++;
            }
            aIndex++;
        }

        while (firstHalfIndex < firstHalf.length) {
            a[aIndex] = firstHalf[firstHalfIndex];
            aIndex++;
            firstHalfIndex++;
        }

        while (lastHalfIndex < lastHalf.length) {
            a[aIndex] = lastHalf[lastHalfIndex];
            aIndex++;
            lastHalfIndex++;
        }
    }
}