1. 정렬이란?


정렬은 이름, 학번, 키 등 핵심 항목의 대소관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업을 말함.

정렬 알고리즘을 이용해 데이터를 정렬하면 검색을 더 쉽게 할수 있음.


키 값이 작은데이터를 앞으로 놓으면 오름차순(ascending order) 정렬

키 값이 큰 데이터를 앞으로 놓으면 내림차순(descending order) 정렬


내부 정렬 : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용하는 알고리즘

외부 정렬 : 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없는 경우에 사용하는 알고리즘


졍렬 알고리즘의 핵심 요소 : 교환, 선택, 삽입



2. 버블정렬


이웃한 두 요소의 대소 관계를 비교하여 교환을 반복한다.


요소의 개수가 n개인 배열에서 n-1회 비교, 교환을 하고 나면 가장 작은 요소가 맨 처음으로 이동함.

이런 일련의 과정(비교, 교환 작업)을 패스(pass)라고 함.


모든 정렬이 끝나면 n-1회의 패스가 수행되어야 함.


1. 버블정렬 방법 1


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
package myTest3;
 
import java.util.Scanner;
 
public class BubbleSort {
    
    // a[idx1]와 a[idx2]의 갑을 바꾼다.
    static void swap(int[] array, int idx1, int idx2){
        for(int i=0; i<array.length; i++){
            if(idx1 == i){
                System.out.print(array[i]+"+");
            }else{
                System.out.print(array[i]);
            }
        }
        System.out.println();        
        int t = array[idx1];
        array[idx1] = array[idx2];
        array[idx2] = t;
 
    }
    
    // 6 4 3 7 1 9 8
    static void bubbleSort(int[] array, int arrayLength){
        for(int i=0; i< arrayLength-1; i++){ 
            System.out.println("패스" + i);
            for(int j=arrayLength-1; j>i; j--){    
                if(array[j-1> array[j]){ // 앞의 요소가 뒤의 요소보다 크다면
                    swap(array, j-1, j);
                }else// 앞의 요소가 뒤의 요소보다 작다면
                    for(int k=0; k<array.length; k++){
                        if(j-1 == k){
                            System.out.print(array[k]+"-");
                        }else{
                            System.out.print(array[k]);
                        }
                    }
                    System.out.println();
                }
            }
            System.out.println("패스"+i+" 정렬결과 ");
            for(int l=0; l<array.length; l++){
                System.out.print(array[l]);
            }
            System.out.println();
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("버블 정렬 방법 1");
        System.out.print("배열의 길이: ");
        int arrayLength = scanner.nextInt();
        int[] array = new int[arrayLength];
        for(int i=0; i<arrayLength; i++){
            System.out.print("array[" + i + "] :");
            array[i] = scanner.nextInt();
        }
        
        bubbleSort(array, arrayLength);        // 배열 x를 버블 정렬 한다.
        System.out.println("오름차순 정렬완료");
        for(int i=0; i<arrayLength; i++){
            System.out.print(array[i]);
        }
        System.out.println();
    }
}
 
cs


결과1


버블 정렬 방법 1
배열의 길이: 7
array[0] :6
array[1] :4
array[2] :3
array[3] :7
array[4] :1
array[5] :9
array[6] :8
패스0
643719+8
64371-89
6437+189
643+1789
64+13789
6+143789
패스0 정렬결과 
1643789
패스1
164378-9
16437-89
1643-789
164+3789
16+34789
패스1 정렬결과 
1364789
패스2
136478-9
13647-89
1364-789
136+4789
패스2 정렬결과 
1346789
패스3
134678-9
13467-89
1346-789
패스3 정렬결과 
1346789
패스4
134678-9
13467-89
패스4 정렬결과 
1346789
패스5
134678-9
패스5 정렬결과 
1346789
오름차순 정렬완료
1346789
cs



2. 정렬 된 상태가 있는 요소가 있을때 교환횟수 기록하는 버블 정렬 방법 2


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
package myTest3;
 
import java.util.Scanner;
 
public class BubbleSort2 {
    
    // a[idx1]와 a[idx2]의 갑을 바꾼다.
    static void swap(int[] array, int idx1, int idx2){
        for(int i=0; i<array.length; i++){
            if(idx1 == i){
                System.out.print(array[i]+"+");
            }else{
                System.out.print(array[i]);
            }
        }
        System.out.println();        
        int t = array[idx1];
        array[idx1] = array[idx2];
        array[idx2] = t;
        if(idx1 == 0){
            for(int i=0; i<array.length; i++){
                System.out.print(array[i]);
            }
            System.out.println();
        }
    }
    
    // 정렬된 상태에서 교환횟수 기록
    static void bubbleSort2(int[] array, int arrayLength){
        for(int i=0; i<arrayLength-1; i++){
            int exchg = 0;                    // 패스의 교환 횟수를 기록합니다.
            System.out.println("패스" + i);
            for(int j=arrayLength-1; j>i; j--){
                if(array[j-1> array[j]){
                    swap(array, j-1, j);
                    exchg++;
                }else// 앞의 요소가 뒤의 요소보다 작다면
                    for(int k=0; k<array.length; k++){
                        if(j-1 == k){
                            System.out.print(array[k]+"-");
                        }else{
                            System.out.print(array[k]);
                        }
                    }
                    System.out.println();
                }
            }
            System.out.println("교환횟수: "+exchg);
            if(exchg == 0break;        // 교환이 이루어지지 않으면 종료한다.
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("버블 정렬 방법 2");
        System.out.print("배열의 길이: ");
        int arrayLength = scanner.nextInt();
        int[] array = new int[arrayLength];
        for(int i=0; i<arrayLength; i++){
            System.out.print("array[" + i + "] :");
            array[i] = scanner.nextInt();
        }
        
        bubbleSort2(array, arrayLength);        // 배열 x를 버블 정렬 한다.
        System.out.println("오름차순 정렬완료");
        for(int i=0; i<arrayLength; i++){
            System.out.print(array[i]);
        }
        System.out.println();
    }
}
 
cs


결과2


버블 정렬 방법 2
배열의 길이: 7
array[0] :1
array[1] :3
array[2] :9
array[3] :4
array[4] :7
array[5] :8
array[6] :6
패스0
139478+6
13947+68
1394-678
139+4678
13-49678
1-349678
교환횟수: 3
패스1
134967-8
13496-78
1349+678
134-6978
13-46978
교환횟수: 1
패스2
134697-8
13469+78
1346-798
134-6798
교환횟수: 1
패스3
134679+8
13467-89
1346-789
교환횟수: 1
패스4
134678-9
13467-89
교환횟수: 0
오름차순 정렬완료
1346789
cs


3. 정렬된 요소를 제외하고 정렬해야 하는 위치를 last로 저장하는 버블정렬 방법 3


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
package myTest3;
 
import java.util.Scanner;
 
public class BubbleSort3 {
    
    // a[idx1]와 a[idx2]의 갑을 바꾼다.
    static void swap(int[] array, int idx1, int idx2){
        for(int i=0; i<array.length; i++){
            if(idx1 == i){
                System.out.print(array[i]+"+");
            }else{
                System.out.print(array[i]);
            }
        }
        System.out.println();        
        int t = array[idx1];
        array[idx1] = array[idx2];
        array[idx2] = t;
        if(idx1 == 0){
            for(int i=0; i<array.length; i++){
                System.out.print(array[i]);
            }
            System.out.println();
        }
    }
    
    // 앞에 3개의 요소가 정렬된 1 3 9 4 7 8 6 인 배열이 있다고 하면
    // 3개의 요소를 제외한 4개의 요소에 대해 비교 교환을 수행해야 한다.
    // 교환을 수행할 때마다 오른족 요소의 인덱스 값을 last에 저장함.
    static void bubbleSort3(int[] array, int arrayLength){
        int k=0;
        while(k<arrayLength-1){ // 0<6 , 3<6, 4<6
            int last = arrayLength-1// last = 6
            for(int j= arrayLength-1; j>k; j--){ // j=6, 6>0 // j=6, 6>3
                if(array[j-1> array[j]){ // array[5] > array[6]
                    swap(array, j-1, j);
                    last = j; // last = 3 // last = 4 // last = 5 // last = 6
                }
            }
            k = last; // k=3 // k= 4 // k=5 // k=6
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("버블 정렬 방법 3");
        System.out.print("배열의 길이: ");
        int arrayLength = scanner.nextInt();
        int[] array = new int[arrayLength];
        for(int i=0; i<arrayLength; i++){
            System.out.print("array[" + i + "] :");
            array[i] = scanner.nextInt();
        }
        
        bubbleSort3(array, arrayLength);        // 배열 x를 버블 정렬 한다.
        System.out.println("오름차순 정렬완료");
        for(int i=0; i<arrayLength; i++){
            System.out.print(array[i]);
        }
        System.out.println();
    }
}
 
cs


결과3


버블 정렬 방법 3
배열의 길이: 7
array[0] :1
array[1] :3
array[2] :4
array[3] :9
array[4] :6
array[5] :7
array[6] :8
1349+678
13469+78
134679+8
오름차순 정렬완료
1346789
cs


4.  홀수번째 패스는 가장 작은 요소를 맨 앞으로 옮기고 

짝수번째 패스는 가장 큰 요소를 맨 뒤로 옮기는 방식 사용한 버블정렬


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
package myTest3;
 
import java.util.Scanner;
 
public class BubbleSort4 {
    
    static void swap1(int[] array, int idx1, int idx2){ // j, j+1
        for(int i=0; i<array.length; i++){
            if(idx1 == i){
                System.out.print(array[i]+"+");
            }else{
                System.out.print(array[i]);
            }
        }
        System.out.println();        
        int t = array[idx2];
        array[idx2] = array[idx1];
        array[idx1] = t;        
    }
 
    // a[idx1]와 a[idx2]의 갑을 바꾼다.
    static void swap2(int[] array, int idx1, int idx2){
        for(int i=0; i<array.length; i++){
            if(idx1 == i){
                System.out.print(array[i]+"+");
            }else{
                System.out.print(array[i]);
            }
        }
        System.out.println();        
        int t = array[idx1];
        array[idx1] = array[idx2];
        array[idx2] = t;
    }
    // 8 9 1 3 4 5 6
    // 1 3 4 8 7 9 2
    // 9 1 3 4 6 7 8 배열이 있다면
    // 두번째 요소부터 정렬되어있지만 bubbleSort3 메소드 사용시 빠른시간안에 정렬작업을 할수 없음.
    // 맨 앞에 있는 요소의 값(9)는 1회의 패스를 거쳐도 한칸씩만 뒤로 옮겨지기 때문
    // 홀수 번째 패스는 가장 작은 요소를 맨 앞으로 옮기고 짝수번째 패스는 가장 큰 요소를 맨 뒤로 옮기는 방식 사용
    // 칵테일 정렬, 쉐이커 정렬
    static void bubbleSort4(int[] array, int arrayLength){
        int k=0;
        int pathCount = 0;
        while(k<arrayLength-1){ // 0<6 , 3<6, 4<6
            int last = arrayLength-1// last = 6W
            if(k%2 == 0){ // 짝수
                pathCount++;
                System.out.println("짝수패스" + pathCount);
                for(int j= 0; j<arrayLength-1; j++){ // 5 6
                    if(array[j] > array[j+1]){ // array[0] > array[1]
                        swap1(array, j, j+1);
                        last = 1;
                    }
                }
            }else{    // 홀수
                pathCount++;
                System.out.println("홀수패스" + pathCount);
                for(int j= arrayLength-1; j>=k; j--){ // j=6, 6>1; j--;
                    if(array[j-1> array[j]){ // array[5] > array[6]
                        swap2(array, j-1, j);
                        last = 0
                    }
                }
            }            
            k = last; // k=3 // k= 4 // k=5 // k=6
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("버블 정렬 방법 4");
        System.out.print("배열의 길이: ");
        int arrayLength = scanner.nextInt();
        int[] array = new int[arrayLength];
        for(int i=0; i<arrayLength; i++){
            System.out.print("array[" + i + "] :");
            array[i] = scanner.nextInt();
        }
        
        bubbleSort4(array, arrayLength);        // 배열 x를 버블 정렬 한다.
        System.out.println("오름차순 정렬완료");
        for(int i=0; i<arrayLength; i++){
            System.out.print(array[i]);
        }
        System.out.println();
    }
}
 
cs


결과4


버블 정렬 방법 4
배열의 길이: 7
array[0] :8
array[1] :9
array[2] :1
array[3] :3
array[4] :4
array[5] :5
array[6] :6
짝수패스1
89+13456
819+3456
8139+456
81349+56
813459+6
홀수패스2
8+134569
짝수패스3
18+34569
138+4569
1348+569
13458+69
홀수패스4
오름차순 정렬완료
1345689
cs





타임리프 문법 및 표현방법 정리


th:text


th:text는 태그 안에 들어가는 텍스트 값이다.


1
<span th:text="${eventFvrDtl.winRnkg}"></span>
cs



th:if, th:unless, th:value 


th:if는 if, th:unless는 else 표현이다.

th:value는 태그 안의 value이다.


1
2
3
4
5
6
<th:block th:if="${eventPtcpPsbOrdData != null && #lists.size(eventPtcpPsbOrdData.eventPtcpOrdInfoList) > 0}">
    <input type="hidden" id="ibx_TotalPurAplAmt" th:value="${totalPurAplAmt}"/>
</th:block>
<th:block th:unless="${eventPtcpPsbOrdData != null && #lists.size(eventPtcpPsbOrdData.eventPtcpOrdInfoList) > 0}">
    <input type="hidden" id="ibx_TotalPurAplAmt" value="0"/>
</th:block>    
cs




th:utext (unescaped text)


th:utext는 <div></div>같은 태그형식의 코드를 삽입하고 싶을때 사용한다.

태그형식의 텍스트 들어올시 태그로 인식함.


1
2
<!-- HTML 컨텐츠 영역 -->
<th:block th:utext="${#campaignUtils.unescapeHtml(eventDispTempleteInfo.htmlContents)}"></th:block>
cs




th:with


th:with는 변수형태의 값을 재정의한 것이다.

stnmZipNo의 변수를 값이 있다면 정의하고 없다면 공백으로 정의한다.


1
2
<th:block th:with="stnmZipNo=${#strings.defaultString(ecCustInfo.stnmZipNo, '')}">
</th:block>
cs


th:switch , th:case


switch case 문과 같다.

fvrDvsCd값이 이럴때 case1, case2 빠지고 

그 외에 것은 th:case=* 로 빠지게 된다. 


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
<div th:switch="${eventFvrDtl.fvrDvsCd}" class="coupon_gift">
    <p th:case="${#foConstants.FVR_DVS_CD_DISCOUNT}" class="cp cptype02">
        <th:block th:switch="${fvrKnd2Cd}">
            <span th:case="${#foConstants.FVR_KND2_CD_FREE_DLV_CPN}" th:text="${fvrKnd2CdNm}" class="tx"></span>
            <span th:case="*" class="tx">
                <th:block th:text="${fvrKnd2CdNm}"></th:block>
            </span>
        </th:block>
    </p>
    <p th:case="${#foConstants.FVR_DVS_CD_ACCUMULATION}" class="cp cptype02">
        <span class="ty" th:text="${fvrKnd2CdNm}"></span>
        <span class="tx" th:text="${#numbers.formatInteger(eventFvrDtl.fvrDtlCnts, 3, 'COMMA')}"></span>
    </p>
    <p th:case="*" class="cp cptype02">
        <span class="tx" th:text="${eventFvrDtl.fvrDtlCnts}"></span>
    </p>
</div>
cs


th:fagment


include와 비슷하다. 

특정 영역을 가져와서 나타낼 수 있다.


예를 들어 페이지마다 각각의 게시판을 가지고 싶은 경우


포함하는 곳.
ex) eventPage1.html


1
2
3
4
<th:block th:if="${#lists.size(eventDispTemplateCornerList)} > 0" th:each="eventDispTemplateCorner : ${eventDispTemplateCornerList}">
    <!-- 이벤트 템플릿 코너 -->
    <th:block th:include="${eventDispTemplateCorner.cmpnTmplFileUrl} :: corner (${eventDispTemplateCorner.cmpnNo}, ${eventData.eventBaseInfo.eventPtcpPsbYn})"></th:block>
</th:block>
cs


받는 곳.

ex) board.html


1
2
3
4
5
6
<th:block th:fragment="corner (cmpnNo, eventPtcpPsbYn)">
    <div class="content_title noline">
        <p class="title">게시판</p>
    </div>
</th:block>
cs



controller를 거쳐 화면으로 가져온 데이터를 스크립트로 제어할때


1
2
3
4
// controller
ModelAndView mv;
mv.addObject("eventData", eventData);
return mv
cs


1
2
3
4
// controller를 거쳐 화면으로 가져온 데이터를 스크립트로 제어할때
var data1 = [[${eventData}]];
var eventPtcpPsbYn = [[${#strings.defaultString(eventData.eventBaseInfo.eventPtcpPsbYn, 'Y')}]];
 
cs


태그 안의 attribute를 타임리프로 정의할때 


1
2
3
4
5
6
7
// 태그 안의 attribute를 타임리프로 정의할때
<div id="myDiv1" th:attr="usemap=|#E_${eventData.eventBaseInfo.cmpnNo}|">
</div>
 
// 정의된 결과
<div id="myDiv1" usemap="#E_21082">
</div>
cs


'전체 > Thymeleaf, JSTL' 카테고리의 다른 글

Thymeleaf 문법 정리  (0) 2018.10.08
JSTL 기초  (0) 2017.05.30


8퀸 문제란?


- 서로 공격하여 잡을 수 없도록 8개의 퀸을 8x8 체스판에 놓아라.


퀸 배치하기


8개의 퀸을 배치하는 조합은 

체스판은 64칸(8x8)이므로 처음에 퀸을 1개 배치할 떄는 64칸 중 아무 곳이나 선택할 수 있다.

다음 퀸을 배치할 때는 나머지 63칸에서 임의로 선택한다.


마찬가지로 8번째까지 생각하면 다음과 같이


64x63x62x61x60x59x58x57 = 178,462,987,637,760 가지 조합이 만들어짐.


8퀸문제의 조건을 만족하는지 조사 불가..


퀸은 자신과 같은 열에 있는 다른 퀸을 공격할 수 있으므로 아래와 같은 규칙을 세울수 있다.


규칙 1. 각 열에 퀸을 1개만 배치한다.


퀸을 배치하는 조합의 수는 많이 줄어든다.

8*8*8*8*8*8*8*8 = 16,777,216 이다.


같은행에 퀸이 2개 이상 배치되면 안된다.


규칙 2. 각 행에 퀸을 1개만 배치한다.


이렇게 하면 조합의 개수가 줄어든다.



1. 가지뻗기를 하며 재귀적으로 각 열에 1개의 퀸을 배치하는 조합을 나열



결과



가장 마지막에 7 7 7 7 7 7 7 7 모든 퀸이 7행에 배치된 것을 확인할 수 있다.



2. 분기한정법을 사용하여 각 행, 열에 1개의 퀸을 배치하는 조합을 재귀적으로 나열


가지뻗기로 퀸을 배치하는 조합을 나열할 수 있지만 8퀸 문제 답을 얻을 수 없다.


규칙 2. 각 행에 퀸을 1개만 배치한다.


규칙 2를 적용해 다시 구현



결과



flag를 사용하여 같은행에 중복하여 퀸이 배치되는 것을 방지한다.

j행에 퀸을 배치하면 true 배치되지 않는 다면 false이다.


3. 8퀸 문제 구현


퀸이 행방향과 열방향으로 서로 겹치지지 않는 조합을 나열했지만

퀸은 대각선 방향으로도 이동할 수 있기 때문에 어떤 대각선에서 보더라도 퀸을 1개만 배치하는 한정조작을 추가해야한다.



결과



flag_b, flag_c 로 방향대각선을 체크하는 배열로 

각각의 대각선 방향에 대해 퀸이 배치되었을 때 체크 하는 배열 인덱스는 flag_b[ i+j ] flag_c[ i-j+7 ] 이다.



소스코드 첨부


myTest1.zip






+ Recent posts

티스토리 툴바