기본 콘텐츠로 건너뛰기

개발 공부 - 다중 반복문과 삽입, 버블, 선택 정렬

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

다중 반복문의 기초로 구구단 알고리즘을 공부한다.
의사 코드는 아래와 같다.


이 의사 코드를 자바로 짜면 아래와 같다.


추적 코드를 붙이면 2 x 2 = 4 이런 식으로 전체를 확인 가능하다.

삽입 정렬

삽입 정렬은 배열을 정렬하는 알고리즘이다.
배열 첫 번째 요소를 이미 존재한다고 가정하고, 나머지 요소를 하나 씩 삽입해 나간다.
삽입할 때 이미 존재하는 요소와 크기를 비교하여 삽입 위치를 결정한다.
마지막 요소를 삽입하면 전체 배열의 정렬이 완료된다.

* 배열 요소를 하나씩 삽입하면서 정렬한다.

의사 코드를 짜면 이렇게 된다.



이걸 자바 코드로 짜면 아래와 같다.


이건 오름차순이고, 내림차순으로 바꾸면 이렇게 된다.


break 대신 반복문에 조건을 걸어도 동작은 똑같다.

맨 마지막에             a[cmp+1] = temp;
를 하는 이유는, 원래 값은 위치가 바뀌어 버리니까 원래 값을 보존하기 위해 사용하는 것이다.

추적 코드를 적으면 아래와 같다.


public class 삽입정렬 {
    public static void main(String[] args) throws Exception {
        int [] a = {90, 34, 78, 12, 56};
        int ins, cmp, temp;
        System.out.println("변경 전 a 값");
       
        for(int i : a){
            System.out.print(i+"\t");
        }

        for(ins = 1; ins < 5; ins++){
            temp = a[ins]; //temp에 삽입할 값을 저장한다.
            System.out.println("\t외부 반복문 " + " ins : " + ins + " a[ins] : " + a[ins]);

            for(cmp = ins - 1; cmp >= 0; cmp--){
               
            System.out.println("\t\t내부 반복문 " + " cmp : " + cmp + " a[ins] : " + a[cmp]);
                //cmp 값은 ins 에서 1씩 감소하므로, 1씩 감소시킨다.
                if(a[cmp] > temp){
                    a[cmp+1 ] = a[cmp]; //뒤쪽으로 하나 이동
                }else{
                    //같거나 temp 값이 더 크면 종료
                    break;
                }
            }
            a[cmp+1] = temp;
        }
        System.out.println("\n\n변경 후 a 값");
       
        for(int i : a){
            System.out.print(i+"\t");
        }
       
               
    }
}



(의외로 vsCode도 복사 붙여넣기 디자인을 제공해서 놀람)


추적 코드 결과는 아래와 같다.


버블 정렬

버블 정렬은 
1. 배열의 끝에서 처음까지 이웃 사이의 요소를 비교하여 작은 값이 앞으로 오도록 요소를 교체한다.
2. 이를 반복하면 배열의 시작 부분에 가장 작은 값을 갖는 요소가 위치한다.
3. 다음으로 나머지 요소에 대해 같은 과정을 거치면 두 번째로 작은 요소가 위치한다.
4. 이같은 절차를 반복하여 배열 전체를 정렬한다.



cmp 값은 1씩 증가하지만, 비교하는 값이 전체크기 - ins값 -1 보다 작아야 하기 떄문에 
ins 값이 증가할 수록 내부 반복문 검색 범위는 줄어든다.
* 앞 부분이 이미 정렬이 되었기 때문에 여러 번 돌리지 않는다.

조건문 안에서는 뒷 요소가 더 작을 경우 현재 것과 위치를 변경해준다.

자바로 구현하면 아래와 같다.


public class 버블정렬 {

    public static void printArr(int [] arr){

        for(int i : arr){
            System.out.print(i+"\t");
        }
        System.out.println("");
    }

    public static void main(String[] args) throws Exception {
        int [] a = {90, 34, 78, 12, 56};
        int ins, cmp, temp;
        System.out.println("정렬 전");
        printArr(a);


        for(ins = 0; ins <a.length -1; ins++){
            for(cmp = 0; cmp < a.length - ins - 1; cmp++){
                if(a[cmp] > a[cmp+1]){
                    //다음 요소가 더 작으면 위치 변경
                    System.out.println("\t위치 변경 : " + a[cmp] + " 와 " + a[cmp+1]);

                    temp = a[cmp];
                    a[cmp] = a[cmp+1];
                    a[cmp+1] = temp;
                }
            }
        }  
        System.err.println("정렬 후 ");
        printArr(a);
               
    }
}




추적 코드는 아래와 같다.


선택 정렬

선택 정렬은 자연스러운 알고리즘이다.
1. 배열의 처음부터 끝까지 하나씩 값을 확인해서 전체 최소값을 선택한다.
2. 최소값과 선두 요소를 교환한다. 
3. 작은 요소가 확정된다.
4. 또 다시 두번째 요소에서 끝까지 같은 과정을 거치면 두 번쨰로 작은 요소가 확정된다.
5개가 있으면
5- > 4 -> 3- > 2 - > 1개를 다 찾아보는 정렬이다.

의사 코드는 아래와 같다.


배열의 왼쪽 요소부터 최소값을 배열하므로 min <- ins 를 사용한다.

자바 코드로 짜면 아래와 같다.


public class 선택정렬 {
    public static void printArr(int [] arr){

        for(int i : arr){
            System.out.print(i+"\t");
        }
        System.out.println("");
    }
    public static void main(String[] args) throws Exception {
        int [] a = {90, 34, 78, 12, 56};
        int ins, cmp, min, temp;

        System.out.println("정렬 전 ");
        printArr(a);

        for(ins = 0; ins <a.length-1; ins++){
            for(cmp = ins+1; cmp < a.length; cmp++){
                if(a[cmp] < a[ins]){
                    //왼쪽 요소보다  다음 것이 크면
                    min = cmp;
                    temp = a[ins];
                    a[ins] = a[min];
                    a[min] = temp;
                    System.out.println("\t" + ins + "번째에 더 작은 값 " + a[ins] + " 현재 작았던 값 : " + a[min]);

                }

            }
        }
               
        System.out.println("정렬 후 ");
        printArr(a);

    }
}




추적 코드를 삽입하면 위와 같다.
실행 횟수를 확인하려면 아래와 같이 코드를 변경해 본다.


public class 선택정렬 {
    public static void printArr(int [] arr){

        for(int i : arr){
            System.out.print(i+"\t");
        }
        System.out.println("");
    }
    public static void main(String[] args) throws Exception {
        int [] a = {90, 34, 78, 12, 56};
        int ins, cmp, min, temp;

        System.out.println("정렬 전 ");
        printArr(a);

        for(ins = 0; ins <a.length-1; ins++){
            int cnt = 1;
            for(cmp = ins+1; cmp < a.length; cmp++){
               
                System.out.print("\t\t" + ins + "번째 " + cnt + "번 실행");
                if(a[cmp] < a[ins]){
                    //왼쪽 요소보다  다음 것이 크면
                    min = cmp;
                    temp = a[ins];
                    a[ins] = a[min];
                    a[min] = temp;
               
                    System.out.print("에 더 작은 값 " + a[ins] + " 현재 작았던 값 : " + a[min]+"\n");

                }else{
                    System.out.print("\n");
                }
                cnt++;
            }
        }
               
        System.out.println("정렬 후 ");
        printArr(a);

    }
}





첫번째 실행 : 전체 = 4번
두번째 실행 : 전체-1 = 3번
세번째 실행 : 전체-2 = 2번
네번째 실행 : 전체-3 = 1번

이렇게 반복해서 정렬 확정을 하는 것이 선택 정렬의 특징이다.





댓글

이 블로그의 인기 게시물

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/ * https://joker1209.tistory.co

개발 공부 - 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 이런 걸 보면 오라클은 앙칼진 시골 아가씨야