기본 콘텐츠로 건너뛰기

개발 공부 - 재귀 호출과 퀵 정렬

* 공부용의 자유로운 글씨😀
『가장 쉬운 독학 알고리즘 첫걸음 - C&자바편』 공부용이다.

재귀 호출 : 함수 안에서 자기 자신을 호출해서 반복 처리를 실현하는 것!
(반복 호출이라 짜기는 편하지만 계승 문제를 풀 때는 효율성 검사 통과 못 함!)

그리고 퀵 정렬은 재귀 호출을 사용해서 프로그램을 작성하는 대량 데이터 정렬이라 같이 챕터에 포함되었나 보다.

팩토리얼을 보통 재귀호출 예제로 사용하기 때문에 교재에서도 그걸 사용했다.


이러면 5*4*3*2*1이 된다!
이걸 자바로 구현하면 아래와 같다.

public class 팩토리얼 {
    public static int factorial(int n){
        if(n==0){
            System.out.println(n+"값이라 1을 반환");
            return 1; //0의 계승이 1이라 1을 반환하고, 여기서 재귀가 끝남
        }else{
            System.out.println(n+"값!");
            return n * factorial(n-1);
        }
    }

    public static void main(String[] args) {
        int ans;
        ans = factorial(5);

        System.out.println(ans);
    }
}


5값!
4값!
3값!
2값!
1값!
0값이라 1을 반환
120

이렇게 동작한다.

처음에 factorial(5) 호출되고, f(4) f(3) f(2) f(1) f(0) 을 호출시킨다.
그래서 1 -> 1 -> 2 -> 6 -> 24 -> 120이 반환된다.

추적 코드를 추가해 보면 아래와 같다.

public class 팩토리얼 {
    public static int factorial(int n){
        System.out.println("factorial" + n + " 호출");
        if(n==0){
            System.out.println(n+"값이라 1을 반환");
            return 1; //0의 계승이 1이라 1을 반환하고, 여기서 재귀가 끝남
        }else{
            int returnVal = n * factorial(n-1);
            System.out.println(n+"값!  " + returnVal);
            return returnVal;
        }
    }

    public static void main(String[] args) {
        int ans;
        ans = factorial(5);

        System.out.println(ans);
    }
}



factorial5 호출
factorial4 호출
factorial3 호출
factorial2 호출
factorial1 호출
factorial0 호출
0값이라 1을 반환
1값!  1
2값!  2
3값!  6
4값!  24
5값!  120
120

결과는 이렇게 된다.
5 -> 4- > 3 -> 2 ->1 을 호출시키고, 반환 순서대로 sysout이 출력된다.

이걸 공부한 뒤에 나오는 퀵 정렬은 대량 데이터를 효율적으로 정렬하는 것인데,
기준값이 되는 요소를 하나 선택해서 나머지 요소들을 기준값보다 작은 값과 큰 값으로
그룹 나누기를 반복해서 전체를 정렬한다.
그룹으로 나누어진 데이터가 하나일 때 까지 계속한다.

1. 기준값이 되는 요소를 하나 선택한다.
2. 나머지 요소를 기준값보다 작은 값과 큰 값으로 그룹 나누기를 반복한다.
3. 그룹으로 나누아진 데이터가 하나가 될 때까지 1과 2를 반복한다.

1) 그룹 나누기 함수 (divideArray)
2) 1)로 정렬을 수행하는 함수 (sortArray)

sortArray 함수에서 divideArray를 사용할 거고 , sortArray 함수 내에서 재귀 호출을 사용할 것이다.


인수로 지정된 a[start] ~ a[end] 배열을 정렬한다.

배열의 요소 수가 2개 이상이라는 조건에서 배열의 요소 그룹 나누기를 수행한 후,
앞쪽 그룹을 인수로 지정해 sortArray 함수를 호출하는 재귀 호출과,
뒤쪽 그룹을 인수로 지정해 sortArray 함수를 호출하는 재귀 호출을 수행한다.




a[head] ~ a[tail] 범위의 배열을 두 그룹으로 나누어 기준값의 인덱스를 반환한다.
기준값보다 앞쪽에는 기준값보다 작은 요소가 있고,
기준값보다 뒤쪽에는 기준값보다 큰 요소가 있다.

만약에 a[0] ~ a[6]을 두 그룹으로 나누어 3이 반환되면 a[3]이 기준값이며,
a[0]~a[2]는 a[3] 보다 작은 요소를 넣고, a[4]~a[6]은 a[3]보다 큰 요소를 넣으면 된다.

break 될 때까지는 무한 반복하는 구조이다.
자바 코드로 구현하면 아래와 같다.

public class 퀵정렬 {
    public static void printArray(int [] a){
        for(int i : a){
            System.out.print("[" + i + "] ");
        }
        System.out.println("배열 인쇄 끝");
    }
    public static void sortArray(int [] a, int start, int end){
        int pivot;

        if(start < end){
            //기준값 대소 관계에 따라 그룹 나누기
            pivot = divideArray(a, start, end);

            sortArray(a, start, pivot-1); //기준값보다 <<<
            sortArray(a, pivot+1, end); // 기준값보다 >>> (끝까지)
        }
    }
    private static int divideArray(int[] a, int head, int tail) {
        int left, right, temp;
        left = head+1; //첫요소 +1부터 뒤까지 >>>
        right = tail; //끝 -> 앞까지 <<<

        //기준값 a[head]보다 작은 요소를 <<< 큰 요소를 >>>
        while(true){
            while(left < tail && a[head] > a[left]){
                //첫요소 +1 부터 >>>> 으로 이동
                left++;
            }

            while(a[head] < a[right]){
                //끝 -> 앞으로 가다가 기준값보다 작은 요소 찾기
                right--;
            }

            if(left >= right){
                //찾다가 확인할 거 없으면 종료
                break;
            }

            temp = a[left];
            a[left] = a[right];
            a[right] = temp;
            //기준값보다 큰 a[left]랑
            //기준값보다 작은 a[right]를 교환함

            left++;
            right--;
        }
           
            temp = a[head];
            a[head] = a[right];
            a[right] = temp;
            //기준값이랑 a[right]를 교환함

        return right; //현재 기준값 위치를 반환함            
   
    }
    public static void main(String[] args) {
        int [] a = {4, 7, 1, 6, 2, 5, 3};

        printArray(a);

        sortArray(a, 0, a.length-1);

        printArray(a);
    }
}



[4] [7] [1] [6] [2] [5] [3] 배열 인쇄 끝
[1] [2] [3] [4] [5] [6] [7] 배열 인쇄 끝

divideArray 함수는 먼저 배열 a, 기준값 인덱스를 뜻하는 head랑 
배열 끝 요소 인덱스를 뜻하는 tail을 인수로 사용한다.
또한 함수 안에는 첫 요소 +1부터 뒷 요소를 훑는 변수 left
뒷 요소부터 앞 요소까지 훑는 right
임시 변수인 temp가 있다.

while(true)안에 while문 2개랑 if문이 있는데,
첫번째 while문은 첫 요소 +1 부터 기준값보다 큰 요소를 찾으므로,
배열 뒷 요소 인덱스가 끝 요소보다 작고, 기준값이 배열 앞 요소값보다 큰 조건을 만족할 때, left 를 1 증가시키는 것이고,
두 번째 while문은 기준값이 배열 끝 요소값보다 작을 때 right를 1 감소시키는 것이다.
if문은 left >= right라는 조건이기 때문에, 반복시마다 기준값보다 큰 a[left]와 기준값보다 작은 a[right]를 교환한다.

sortArray는 배열 a, 정렬 기준 위치, 정렬 끝 요소 end를 사용한다.
또한 기준값 인덱스를 뜻하는 pivot 변수를 사용한다.
sortArray함수의 if문 안에는 (정렬 기준 위치가 정렬할 끝 요소보다 작아야 한다) 
기준값의 대소 관계를 반복해서 판단하려고 재귀를 사용한다.

1) sortArray 함수의 start에 따라 기준값 중심으로 배열 요소를 정렬한 divideArray를 실행한다.
2) 기준값보다 작은 그룹용 sortArray를 실행한다
3) 기준값보다 큰 용 sortArray를 실행한다.

추적 코드를 삽입하면 아래와 같다.

public class 퀵정렬 {
    public static void printArray(int [] a){
        for(int i : a){
            System.out.print("[" + i + "] ");
        }
        System.out.println("배열 인쇄 끝");
    }
    public static void sortArray(int [] a, int start, int end){
        System.out.println("sortArray 호출 head 값 : " + start + " end 값 : " + end);
        printArray(a);
        int pivot;

        if(start < end){
            //기준값 대소 관계에 따라 그룹 나누기
            pivot = divideArray(a, start, end);
            System.out.println(pivot + " 기준값 ");

            sortArray(a, start, pivot-1); //기준값보다 <<<
            sortArray(a, pivot+1, end); // 기준값보다 >>> (끝까지)
        }
    }
    private static int divideArray(int[] a, int head, int tail) {
        System.out.println("divideArray 호출 head 값 : " + head + " tail 값 : " + tail);
        int left, right, temp;
        left = head+1; //첫요소 +1부터 뒤까지 >>>
        right = tail; //끝 -> 앞까지 <<<

        //기준값 a[head]보다 작은 요소를 <<< 큰 요소를 >>>
        while(true){
            while(left < tail && a[head] > a[left]){
                //첫요소 +1 부터 >>>> 으로 이동
                left++;
            }

            while(a[head] < a[right]){
                //끝 -> 앞으로 가다가 기준값보다 작은 요소 찾기
                right--;
            }

            if(left >= right){
                //찾다가 확인할 거 없으면 종료
                break;
            }

            temp = a[left];
            a[left] = a[right];
            a[right] = temp;
            //기준값보다 큰 a[left]랑
            //기준값보다 작은 a[right]를 교환함

            left++;
            right--;
        }
           
            temp = a[head];
            a[head] = a[right];
            a[right] = temp;
            //기준값이랑 a[right]를 교환함

        System.out.println(right + " 현재 기준값 위치");

        return right; //현재 기준값 위치를 반환함            
   
    }
    public static void main(String[] args) {
        int [] a = {4, 7, 1, 6, 2, 5, 3};


        sortArray(a, 0, a.length-1);

    }
}



sortArray 호출 head 값 : 0 end 값 : 6
[4] [7] [1] [6] [2] [5] [3] 배열 인쇄 끝 //처음 호출 시 배열 상태

divideArray 호출 head 값 : 0 tail 값 : 6
3 현재 기준값 위치 //divideArray 한 번 돌렸을 때 기준값 상태

3 기준값 // 처음 divideArray 돌리고 난 기준값 
sortArray 호출 head 값 : 0 end 값 : 2 
[2] [3] [1] [4] [6] [5] [7] 배열 인쇄 끝  

divideArray 호출 head 값 : 0 tail 값 : 2
1 현재 기준값 위치 //앞 부분 정렬이 끝난 상태임

1 기준값
sortArray 호출 head 값 : 0 end 값 : 0
[1] [2] [3] [4] [6] [5] [7] 배열 인쇄 끝

sortArray 호출 head 값 : 2 end 값 : 2
[1] [2] [3] [4] [6] [5] [7] 배열 인쇄 끝

sortArray 호출 head 값 : 4 end 값 : 6
[1] [2] [3] [4] [6] [5] [7] 배열 인쇄 끝

divideArray 호출 head 값 : 4 tail 값 : 6
5 현재 기준값 위치// 뒷 부분 정렬이 끝난 상태

5 기준값
sortArray 호출 head 값 : 4 end 값 : 4
[1] [2] [3] [4] [5] [6] [7] 배열 인쇄 끝 
sortArray 호출 head 값 : 6 end 값 : 6
[1] [2] [3] [4] [5] [6] [7] 배열 인쇄 끝

이런 식으로 동작한다.

이거 사실 Arrays.sort() 쓰고 싶은데 
요즘 프로그래머스에서 굳이 이런 식으로 짜는 것을 원해서? 공부해 보았다...
시간복잡도의 세계






댓글

이 블로그의 인기 게시물

Ebook - 전자책 drm 상관 없이 pdf로 만들기

yes24와 교보문고에서 ebook을 구매 해야 했는데 너무 불편하고, 필기가 매우 화날 정도로 안 좋아서 원시적으로 사용하기로 했다. 1. 목적 : ebook에서 필기 및 사용이 불편하여 pdf로 변환  2. 용도 : 개인 사용 목적이며 화질이 다소 저하되어도 필기만 용이하면 상관 없음 3. 방법 1) 휴대폰 및 카메라로 동영상을 촬영했다. DRM 때문에 프로그램으로는 촬영이 안 되는 것을 확인했다. (사실 개인 사용 목적이면 기본 화면 캡쳐를 사용해도 된다...) 2) 마우스 클릭 해주는 매크로를 사용했다. (1) key_macro.exe > https://blog.daum.net/pg365/250 듀얼 모니터에서 위치 이탈 현상이 있긴 해도 괜찮았다. (2) AutoClick.exe > http://bestsoftwarecenter.blogspot.com/2011/02/autoclick-22.html 이 걸로 잘 사용했다. 3초마다 한 번 클릭하도록 사용했다. 3) 동영상을 이미지로 변경해주는 프로그램을 사용했다. Free Video to JPG Converter > https://www.dvdvideosoft.com/products/dvd/Free-Video-to-JPG-Converter.htm (240826: 다운로드 시 정상적으로 되지 않아서 URL 수정) 일 하면서 듀얼 모니터에 켜 놨는데 속도가 괜찮았다. * Every frame 으로 사용해야 한다. 4) 중복 사진 제거해주는 프로그램을 사용했다. VlsiPics  > http://www.visipics.info/index.php?title=Main_Page 생각보다 느리니 퇴근시에 걸어놓고 가면 된다. 한번 play가 끝나면 Auto-select 하고 Delete 하면 된다. 5) 이미지를 일괄 Crop 작업 해주는 프로그램을 사용했다. JPEGCrops > https://jpegcrops.softonic.kr/ *...

개발 공부 - json JSONObject 사용 시 백슬래시(\), 원화 표시(\) 제거 및 치환

import org.json.simple.JSONObject; String dataString = new String(authData.toJSONString()); dataString = dataString.replaceAll("\\\\", ""); String 으로 안 바뀌는 가 싶어서 String 으로 변환 해 주고 작업 하였다. 사실 toJSONString 해도 정상 동작 해야 하는데 이유를 잘 모르겠음. 그리고 나서 다시 이클립스 구동 하니 toString 도 먹은 걸로 봐서 이상하다고 생각! String dataString = authData.toString(); dataString = dataString.replaceAll("\\\\", ""); 어쨌든 백 슬래시 제거를 해줘야 하는데 \\ 도 아니고 \\\\를 해야 변환이 가능했다는 결말이었습니다. 참고 : https://stackoverflow.com/questions/15450519/why-does-string-replace-not-work/15450539 test =test.replace("KP", "");  replace 후에 담아 주지 않으면 적용이 안 됩니다!

개발 공부 - OracleXETNSListener 서비스가 로컬 컴퓨터에서 시작했다가 중지되었습니다.

여러 가지 요인이 있지만 PC 이름 변경시 OracleXETNSListener 서비스 시작이 불가능합니다. 고치는 법은 C:\oraclexe\app\oracle\product\11.2.0\server\network\ADMIN 와 같은 설치 경로에서 listener.ora와 tnsnames.ora 의 pc명을 바꾼 PC명으로 바꿔주면 됩니다. 그래도 안 된다면 cmd 창에서 services.msc 를 입력 후 OracleXETNSListener 서비스를 시작 시키면 됩니다. 오류명: OracleXETNSListener 서비스가 로컬 컴퓨터에서 시작했다가 중지되었습니다. 일부 서비스는 다른 서비스 또는 프로그램에서 사용되지 않으면 자동으로 중지됩니다. 참고한 사이트들 1. http://blog.naver.com/visioner7/120165951652 2. http://database.sarang.net/?inc=read&aid=6819&criteria=oracle&subcrit=&id=&limit=20&keyword=ora-12560&page=5 이런 걸 보면 오라클은 앙칼진 시골 아가씨야