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
package myTest4;
 
import java.util.Scanner;
 
public class ShellSort {
    
    static void shellSort(int[] a, int n){
        for(int h= n/2; h>0; h /= 2){
            for(int i=h; i<n; i++){
                int j;
                int tmp = a[i];
                for(j=i-h; j>= 0 && a[j] > tmp; j-= h){
                    a[j+h] = a[j];
                }
                a[j+h] = tmp;
                for(int k=0; k<n; k++){
                    System.out.print(a[k]);
                }
                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();
        }
        
        shellSort(array, arrayLength);        
        System.out.println("오름차순 정렬완료");
        for(int i=0; i<arrayLength; i++){
            System.out.println("array["+i+"]:" + array[i]);
        }
        System.out.println();
    }
}
cs



쉘 정렬 결과


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
셀 정렬(버전 1)
배열의 길이: 6
array[0]:6
array[1]:5
array[2]:4
array[3]:3
array[4]:2
array[5]:1
354621
324651
321654
231654
123654
123654
123564
123456
오름차순 정렬완료
array[0]:1
array[1]:2
array[2]:3
array[3]:4
array[4]:5
array[5]:6
cs


2. 증분값 h를 변경한 쉘정렬 


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
package myTest4;
 
import java.util.Scanner;
 
public class ShellSortChangeHvalue {
    
    static void shellSort2(int[] a, int n){
        int h;
        for( h = 1; h<n/9; h=h*3+1);
        
        for(;h>0; h/=3){
            for(int i= h; i<n; i++){
                int j;
                int tmp = a[i];
                for(j=i-h; j>=0 && a[j] > tmp; j-=h){
                    a[j+h] = a[j];
                }
                a[j+h] = tmp;
                for(int k=0; k<n; k++){
                    System.out.print(a[k]);
                }
                System.out.println();                        
            }
        }
    }
    
    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();
        }
        
        shellSort2(array, arrayLength);        // 배열 x를 버블 정렬 한다.
        System.out.println("오름차순 정렬완료");
        for(int i=0; i<arrayLength; i++){
            System.out.println("array["+i+"]:" + array[i]);
        }
        System.out.println();
    }
}
cs



증분값 h를 변경한 쉘정렬 결과


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
셀 정렬(버전 2)
배열의 길이: 6
array[0]:6
array[1]:5
array[2]:4
array[3]:3
array[4]:2
array[5]:1
564321
456321
345621
234561
123456
오름차순 정렬완료
array[0]:1
array[1]:2
array[2]:3
array[3]:4
array[4]:5
array[5]:6
cs


'전체 > 알고리즘' 카테고리의 다른 글

병합정렬  (0) 2018.11.03
퀵정렬  (0) 2018.11.03
단순 선택정렬, 단순 삽입정렬  (0) 2018.10.27
버블정렬 여러가지 방법 구현  (0) 2018.10.09
8퀸 문제, 가지뻗기, 분기한정법 사용 구현  (2) 2018.10.07



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
package myTest4;
 
import java.util.Scanner;
 
public class SimpleSelectionSort {
    
    static void selectionSort(int[] a, int n){
        for(int i=0; i<n-1; i++){ 
            int min = i ;    // 아직 정렬되지 않은 부분에서 가장 작은 요소의 인덱스를 기록 min = 0
            for(int j = i+1; j < n; j++){ 
                if(a[j] < a[min]){ 
                    min = j ;
                }
            }
            swap(a, i, min);
        }
    }
    
    static void swap(int[] array, int idx1, int idx2){
        for(int i=0; i<array.length; i++){
            System.out.print(array[i]);
        }
        System.out.println();        
        int t = array[idx1];
        array[idx1] = array[idx2];
        array[idx2] = t;
    }    
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        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();
        }
        
        selectionSort(array, arrayLength);    
        System.out.println("오름차순 정렬완료");
        for(int i=0; i<arrayLength; i++){
            System.out.print(array[i]);
        }
        System.out.println();
    }
}
cs



단순 선택 정렬결과


1
2
3
4
5
6
7
8
9
10
11
12
배열의 길이: 5
array[0] :5
array[1] :4
array[2] :3
array[3] :2
array[4] :1
54321
14325
12345
12345
오름차순 정렬완료
12345
cs



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
package myTest4;
 
import java.util.Scanner;
 
public class SimpleInsertSort {
    
    static void insertionsort(int[] a, int n){
        for(int i=1; i<n; i++){
            int j;
            int tmp = a[i];
            for(j=i; j>0 && a[j-1] > tmp; j--){
                a[j] = a[j-1];
            }
            a[j] = tmp;
            for(int k=0; k<n; k++){
                System.out.print(a[k]);
            }
            System.out.println();
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        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();
        }
        
        insertionsort(array, arrayLength);        // 배열 x를 버블 정렬 한다.
        System.out.println("오름차순 정렬완료");
        for(int i=0; i<arrayLength; i++){
            System.out.print(array[i]);
        }
        System.out.println();
    }
}
cs



단순 삽입 정렬결과


1
2
3
4
5
6
7
8
9
10
11
12
배열의 길이: 5
array[0] :5
array[1] :4
array[2] :3
array[3] :2
array[4] :1
45321
34521
23451
12345
오름차순 정렬완료
12345
cs



'전체 > 알고리즘' 카테고리의 다른 글

퀵정렬  (0) 2018.11.03
쉘 정렬  (0) 2018.10.27
버블정렬 여러가지 방법 구현  (0) 2018.10.09
8퀸 문제, 가지뻗기, 분기한정법 사용 구현  (2) 2018.10.07
재귀를 사용한 팩토리얼, 최대공약수, 하노이탑 구현  (0) 2018.10.07


group by 이해하기


응모자 테이블(pr_evnt_tkpt)에 

한 사람(ec_cust_no)이 같은 이벤트번호(cmpn_no)로 여러번 응모가 가능하다.


ex) pr_evnt_tkpt 전체 데이터가 다음과 같이 들어가 있다.


1
2
3
4
5
6
ptcp_no   cmpn_no   ec_cust_no 
   1         1         E100
   2         1         E100
   3         1         E100
   4         2         E200
   5         2         E300
cs

쿼리 1.

1
2
3
4
select * from pr_evnt_tkpt a
 where a.cmpn_no = '1'
   and a.ec_cust_no = 'E100'
;
cs


결과 1.


1
2
3
4
ptcp_no   cmpn_no   ec_cust_no 
   1         1         E100
   2         1         E100
   3         1         E100
cs

쿼리 2.

1
2
3
4
5
-- 각각의 이벤트에 총 응모한 횟수
select a.cmpn_no, count(*)
  from pr_evnt_tkpt a
  group by a.cmpn_no
;
cs

결과 2.

1
2
3
cmpn_no  count 
   1       3
   2       2
cs

쿼리 3.

1
2
3
4
5
-- 각각의 이벤트에 한 회원이 응모한 횟수
select a.cmpn_no, a.ec_cust_no, count(*) 
  from pr_evnt_tkpt a 
  group by a.cmpn_no, a.ec_cust_no 
;
cs

결과 3.


1
2
3
4
cmpn_no  ec_cust_no  count 
   1        E100       3
   2        E200       1
   2        E300       1
cs



다음과 같이 카운트 값을 확인 할 수 있었다.



'전체 > MySQL' 카테고리의 다른 글

SQL EXPLAIN 정리  (0) 2018.11.19
ANSI Syntax and Conventional syntax(non-ANSI) 안시조인 사용 이유  (0) 2018.10.29
where case문, or문 사용하기  (1) 2018.06.20
쿼리에서 select해서 update하기, 쿼리에서 select한 값을 list로 받아와서 update하기  (0) 2018.06.07
MySQL 부등호 비교, 만 나이 구하는 쿼리  (0) 2018.05.15


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
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
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 == 0) break;        // 교환이 이루어지지 않으면 종료한다.
        }
    }
    
    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
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
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




'전체 > 알고리즘' 카테고리의 다른 글

쉘 정렬  (0) 2018.10.27
단순 선택정렬, 단순 삽입정렬  (0) 2018.10.27
8퀸 문제, 가지뻗기, 분기한정법 사용 구현  (2) 2018.10.07
재귀를 사용한 팩토리얼, 최대공약수, 하노이탑 구현  (0) 2018.10.07
배열을 사용한 큐, 링버퍼 큐, 링버퍼 활용 구현  (0) 2018.10.07


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


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
<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
// 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' 카테고리의 다른 글

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개의 퀸을 배치하는 조합을 나열


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
package myTest2;
 
public class QuuenB {
    // 가지뻗기
    // 규칙 1. 각 열에 퀸을 1개만 배치한다.
    // 각 열에 1개의 퀸을 배치하는 조합을 재귀적으로 나열
    static int[] pos = new int[8];    // 각 열의 퀸의 위치
    
    // 각 열의 퀸의 위치를 출력한다.
    static void print(){
        for(int i=0; i<8; i++){
            System.out.printf("%2d",pos[i]);
        }
        System.out.println();
    }
    
    static void set(int i){
        for(int j=0; j<8; j++){
            // pos[0] = 0
            pos[i] = j;        // 퀸을 j행에 배치한다.
            if(i==7){        // 모든 열에 배치한다.
                print();
            }else{
                set(i+1);    // 다음 열에 퀸을 배치한다.
            }
        }
    }
    
    public static void main(String[] args) {
        set(0);        // 0열에 퀸을 배치한다.
    }
}
cs



결과



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



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


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


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


규칙 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
package myTest2;
 
public class QuuenBB {
    // 분기 한정법
    // 규칙 1. 각 열에 퀸을 1개만 배치한다.
    // 규칙 2. 각 행에 퀸을 1개만 배치한다.
    static boolean[] flag = new boolean[8];    // 각 행에 퀸을 배치했는지 체크
    static int[] pos = new int[8];                        // 각 열의 퀸의 위치
    
    // 각 열의 퀸의 위치를 출력함.
    static void print(){
        for(int i=0; i<8; i++){
            System.out.printf("%2d", pos[i]);
        }
        System.out.println();
    }
    
    // i열에 알맞은 위치에 퀸을 배치한다.
    static void set(int i){
        for(int j = 0; j < 8; j++){
            if(flag[j] == false){    // j행에는 퀸을 아직 배치하지 않았다면
                pos[i] = j;                // 퀸을 j행에 배치한다.
                if( i== 7){            // 모든 열에 배치한 경우
                    print();
                }else{
                    flag[j] = true;
                    set(i+1);
                    flag[j] = false;
                }
            }
        }
    }
    
    public static void main(String[] args) {
        set(0);        // 0열에 퀸을 배치한다.
    }
}
cs



결과



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

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


3. 8퀸 문제 구현


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

퀸은 대각선 방향으로도 이동할 수 있기 때문에 어떤 대각선에서 보더라도 퀸을 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
69
70
71
72
73
package myTest2;
 
public class EightQueen {
 
    static boolean[] flag_a = new boolean[8];    // 각 행에 퀸을 배치했는지 체크
    static boolean[] flag_b = new boolean[15];    //  ↗ 대각선 방향으로 퀸을 배치했는지 체크
    static boolean[] flag_c = new boolean[15];    //  ↘ 대각선 방향으로 퀸을 배치했는지 체크
    static int[] pos = new int[8];
    
    // 각 열의 퀸의 위치를 출력
    static void print(){
        StringBuilder oneLine0 = new StringBuilder("□□□□□□□□");
        StringBuilder oneLine1 = new StringBuilder("□□□□□□□□");
        StringBuilder oneLine2 = new StringBuilder("□□□□□□□□");
        StringBuilder oneLine3 = new StringBuilder("□□□□□□□□");
        StringBuilder oneLine4 = new StringBuilder("□□□□□□□□");
        StringBuilder oneLine5 = new StringBuilder("□□□□□□□□");
        StringBuilder oneLine6 = new StringBuilder("□□□□□□□□");
        StringBuilder oneLine7 = new StringBuilder("□□□□□□□□");
        
        for(int i=0; i<8; i++){
            
            System.out.printf("%2d", pos[i]);
            int value1 = pos[i]; // 4 
            if(value1 == 0){
                oneLine0.setCharAt(i, '■');
            }else if(value1 == 1){
                oneLine1.setCharAt(i, '■');
            }else if(value1 == 2){
                oneLine2.setCharAt(i, '■');
            }else if(value1 == 3){
                oneLine3.setCharAt(i, '■');
            }else if(value1 == 4){
                oneLine4.setCharAt(i, '■');
            }else if(value1 == 5){
                oneLine5.setCharAt(i, '■');
            }else if(value1 == 6){
                oneLine6.setCharAt(i, '■');
            }else if(value1 == 7){
                oneLine7.setCharAt(i, '■');
            }
        }
        System.out.println();
        String whole = oneLine0 +"\n" + oneLine1 +"\n" + 
                               oneLine2 +"\n" + oneLine3 +"\n" + 
                               oneLine4 +"\n" + oneLine5 +"\n" + 
                               oneLine6 +"\n" + oneLine7 +"\n"; 
        System.out.println(whole);
        System.out.println();
    }
    
    // i열에 알맞은 위치에 퀸을 배치
    static void set(int i){
        for(int j=0; j<8; j++){
            if(flag_a[j] == false                     // 가로(j행)에 아직 배치하지 않았습니다.
                    && flag_b[i+j] == false         // 대각선 ↗에 아직 배치하지 않았습니다.
                    && flag_c[i-j+7] == false){    // 대각선 ↘에 아직 배치하지 않았습니다.
                pos[i] = j;
                if(i == 7){
                    print();
                }else{
                    flag_a[j] = flag_b[i+j] = flag_c[i-j+7] = true;
                    set(i+1);
                    flag_a[j] = flag_b[i+j] = flag_c[i-j+7] = false;
                }
            }
        }
    }
    
    public static void main(String[] args) {
        set(0);
    }
}
cs



결과



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

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



소스코드 첨부


myTest1.zip






'전체 > 알고리즘' 카테고리의 다른 글

단순 선택정렬, 단순 삽입정렬  (0) 2018.10.27
버블정렬 여러가지 방법 구현  (0) 2018.10.09
재귀를 사용한 팩토리얼, 최대공약수, 하노이탑 구현  (0) 2018.10.07
배열을 사용한 큐, 링버퍼 큐, 링버퍼 활용 구현  (0) 2018.10.07
스택 알고리즘 구현  (0) 2018.10.03


재귀


어떤 사건이 자기 자신을 포함하고 다시 자기 자신을 사용하여 정의될때 재귀적(recursive)이라고 한다.


1은 자연수, 

자연수 n의 바로 다음수도 자연수


재귀적 정의에 의해 무한으로 존재하는 자연수를 위의 두 문장으로 정의할수 있다.

재귀를 효과적으로 사용하면 이런 정의뿐만 아니라 프로그램도 간결하게 할 수 있다.



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
package myTest2;
 
import java.util.Scanner;
 
public class Factorial {
    // 팩토리얼을 재귀적으로 구현
    // 재귀 메서드를 사용하여 양의 정수 n의 팩토리얼을 반환한다.
    static int factorial(int n){
        if(n>0) return n * factorial(n-1);
        else return 1;
    }
    
    // 자기 자신을 부르지 않고 구현한 메서드
    static int notUsingRecursive(int n){
        if(n>0){
            int value = 1;
            for(int i=n; i>0; i--){ 
                value = value * i; 
            }
            return value;
        }else{
            return 1;
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("정수를 입력하세요: ");
        int x = scanner.nextInt();
        System.out.println(x+ "의 팩토리얼은 " + factorial(x) + "입니다.");
        System.out.println(x+ "의 재귀메서드 사용안한 메서드는 " + notUsingRecursive(x) + "입니다.");
    }
}
cs


결과



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
package myTest2;
 
import java.util.Scanner;
 
public class EuclidGCD {
    // 재귀를 사용하여 정수 x,y 의 최대공약수 반환
    static int gcd(int x, int y){ 
        if(y == 0) return x;
        else return gcd(y, x%y);
    }
    
    // 재귀를 사용하지 않고 정수 x,y 의 최대공약수 반환
    static int notUsingRecursive(int x, int y){
        if(y == 0) {
            return x;
        }else { 
            int value1 = y; 
            int value2 = y ;
            y = x % y;    
            while(y!=0){
                value2 = y; 
                y = value1 % value2; 
                value1 = value2;
            }
            return value2;
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("두 정수의 최대공약수를 구합니다.");
        System.out.print("정수를 입력하세요 : ");    int x = scanner.nextInt();
        System.out.print("정수를 입력하세요 : ");    int y = scanner.nextInt();
 
        System.out.println("최대공약수는" + gcd(x,y) + "입니다.");
        System.out.println("최대공약수는" + notUsingRecursive(x,y) + "입니다.");
    }
}
cs


재귀를 사용하지 않고 정수 x,y 의 최대공약수 반환메소드, 재귀를 사용한 메소드를 구현하였다.


결과



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
package myTest2;
 
import java.util.Scanner;
 
public class Hanoi {
    
    // 재귀함수
    static void move(int no, int x, int y){
        
        if(no > 1){
            move(no-1, x, 6-x-y);
        }
        
        String stringX = "";
        String stringY = "";
        if(x==1) stringX = "A";
        if(y==1) stringY = "A";
        if(x==2) stringX = "B";
        if(y==2) stringY = "B";
        if(x==3) stringX = "C";
        if(y==3) stringY = "C";
        
        System.out.println("원반[" + no + "]을" + stringX + "기둥에서 " + stringY + "기둥으로 옮김");
        if(no > 1){
            move(no-1, 6- x-y, y);
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("하노이의 탑");
        System.out.println("원반 개수 : ");
        int n = scanner.nextInt();
        move(n, 1, 3);    // 1번 기둥의 n개의 원반을 3번 기둥으로 옮김
    }
}
cs


결과




소스 코드


myTest1.zip




'전체 > 알고리즘' 카테고리의 다른 글

버블정렬 여러가지 방법 구현  (0) 2018.10.09
8퀸 문제, 가지뻗기, 분기한정법 사용 구현  (2) 2018.10.07
배열을 사용한 큐, 링버퍼 큐, 링버퍼 활용 구현  (0) 2018.10.07
스택 알고리즘 구현  (0) 2018.10.03
이진검색 알고리즘 (구현 메소드 사용, Arrays.binarySearch 라이브러리 사용)  (0) 2018.10.03


큐는 데이터를 일시적으로 쌓아놓은 자료구조이다.

가장 먼저 넣은 데이터를 가장 먼저 꺼내는 선입선출인 점이 스택과 다름.


가장먼저 넣은 데티러르 가장 먼저 꺼내는 선입선출 구조로 되어있다.


큐의 예는 은행 창구에서 차례를 기다리는 대기열이나 마트에서 계산을 기다리는 대기열을 들 수 있다.


큐에 데이터를 넣는 작업을 인큐라 하고 데이터를 꺼내는 작업을 디큐라고 한다.

데이터를 꺼내는 쪽을 프런트(front)라 하고 데이터를 넣는 쪽을 리어(rear)라고 한다.


배열을 사용해 디큐를 하면서 모든 요소를 하나씩 앞쪽으로(shift)  옮기는 큐는 

데이터를 꺼낼때 마다 O(n) 복잡도 이므로 이런 처리를 하면 효율이 떨어짐


1. 배열을 사용해 디큐를 하면서 모든 요소를 하나씩 앞쪽으로(shift)  옮기는 큐 구현



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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
package myTest1;
 
import java.util.Scanner;
 
public class IntAryQueue {
    
    private int max;        // 큐 용량        
    private int num;        // 현재 데이터 수
    private int[] que;        // 큐 본체
    
    // 실행 시 예외 : 큐이 비어있음
    public class EmptyIntAryQueueException extends RuntimeException{
        public EmptyIntAryQueueException(){
        }
    }
    
    // 실행 시 예외 : 큐이 가득 참
    public class OverflowIntAryQueueException extends RuntimeException{
        public OverflowIntAryQueueException(){
        }
    }
    
    // 생성자
    public IntAryQueue(int capacity){
        num = 0;
        max = capacity;
        try{
            que = new int[max];            // 큐 본체용 배열을 생성
        }catch(OutOfMemoryError e){    // 생성할 수 없음
            max = 0;
        }
    }
 
    // 큐에 데이터를 인큐하는 메서드
    public int inQueue(int x) throws OverflowIntAryQueueException{
        if(num >= max){    // 큐이 가득 참
            throw new OverflowIntAryQueueException();
        }
        return que[num++] = x;
    }
    
    // 큐의 맨 첫번째에 있는 데이터를 제거(디큐) 하고 그 값을 반환하는 메서드
    public int deQueue() throws EmptyIntAryQueueException{
        if(num <= 0){
            throw new EmptyIntAryQueueException();
        }
        int data = que[0];
        for(int i=0; i<num-1; i++){ // 0 < 2 // 0 1 2
            que[i] = que[i+1]; // que[0] = que[1] , que[1] = que[2],  que[2] = que[3]
        }
        --num;
        return data;
    }
    
    // 큐의 가장 먼저 빠질 데이터를 몰래 엿보는 메서드(peek 메서드 )
    public int peek() throws EmptyIntAryQueueException{
        if(num <= 0){
            throw new EmptyIntAryQueueException();
        }
        return que[0];
    }
    
    // 큐에서 x를 찾아 인덱스를 반환
    public int indexOf(int x){
        for(int i=num -1; i>=0; i--){
            if(que[i] == x){
                return i;
            }
        }
        return -1;
    }
    
    // 큐을 비움
    public void clear(){
        num = 0;
    }
    
    // 큐의 용량을 반환
    public int capacity(){
        return max;
    }
    
    // 큐에 쌓여있는 데이터 수를 반환
    public int size(){
        return num;
    }
    
    // 큐이 비어있는가?
    public boolean isEmpty(){
        return num <= 0;
    }
    
    // 큐이 가득찼는가?
    public boolean isFull(){
        return num >= max;
    }
    
    // 큐 안의 모든 데이터를 바닥 -> 꼭대기 순서로 출력
    public void dump(){
        if(num <= 0){
            System.out.println("큐이 비어있습니다.");
        }else{
            for(int i=0; i<num; i++){
                System.out.print(que[i] + " ");
            }
            System.out.println();
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        IntAryQueue queue = new IntAryQueue(64);    // 최대 64개를 푸시할 수 있는 큐
        
        while(true){
            System.out.println("현재 데이터 수 : " + queue.size() + " / " + queue.capacity()); 
            System.out.print("(1) 인큐 (2) 디큐 (3) 피크 (4) 덤프 (0) 종료 : ");
            int menu = scanner.nextInt();
            if(menu == 0) break;
            
            int x;
            switch(menu){
            
            case 1:
                System.out.print("데이터 : ");
                x = scanner.nextInt();
                try{
                    queue.inQueue(x);
                }catch(IntAryQueue.OverflowIntAryQueueException e){
                    System.out.println("큐가 가득찼습니다.");
                }
                break;
                
            case 2:
                try{
                    x = queue.deQueue();
                    System.out.println("디큐한 데이터는 " + x + "입니다.");
                }catch(IntAryQueue.EmptyIntAryQueueException e){
                    System.out.println("큐가 비어있습니다.");
                }
                break;
 
            case 3:
                try{
                    x = queue.peek();
                    System.out.println("피크한 데이터는 " + x + "입니다.");
                }catch(IntAryQueue.EmptyIntAryQueueException e){
                    System.out.println("큐가 비어있습니다.");
                }
                break;
 
            case 4:
                queue.dump();
                break;
            }
        }
    }
}
cs


결과




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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
package myTest1;
 
import java.util.Scanner;
 
public class IntQueue {
    
    private int max;        // 큐 용량        
    private int front;        // 첫번째 요소 커서
    private int rear;    // 마지막 요소 커서
    private int num;        // 현재 데이터 수
    private int[] que;    // 큐 본체
    
    // 실행 시 예외 : 큐이 비어있음
    public class EmptyIntQueueException extends RuntimeException{
        public EmptyIntQueueException(){
        }
    }
    
    // 실행 시 예외 : 큐이 가득 참
    public class OverflowIntQueueException extends RuntimeException{
        public OverflowIntQueueException(){
        }
    }
    
    // 생성자
    public IntQueue(int capacity){
        num = front = rear = 0;
        max = capacity;
        try{
            que = new int[max];            // 큐 본체용 배열을 생성
        }catch(OutOfMemoryError e){    // 생성할 수 없음
            max = 0;
        }
    }
 
    // 큐에 데이터를 인큐하는 메서드
    public int enque(int x) throws OverflowIntQueueException{
        if(num >= max){    // 큐이 가득 참
            throw new OverflowIntQueueException();
        }
        // que[0] 10 que[1] 9 que[2] 8
        // num = 3
        que[rear++] = x;
        num++;
        if(rear == max){
            rear = 0;
        }
        return x;
    }
    
    // 큐의 맨 첫번째에 있는 데이터를 제거(디큐) 하고 그 값을 반환하는 메서드
    public int deque() throws EmptyIntQueueException{
        if(num <= 0){
            throw new EmptyIntQueueException();    // 큐가 비어있음.
        }
        // que[0] 10 que[1] 9 que[2] 8
        // num = 3
        // int x = 10, num = 2 , front = 1
        int x = que[front++];
        num--;
        if(front == max){
            front = 0;
        }
        return x;
    }
    
    // 큐의 가장 먼저 빠질 데이터를 몰래 엿보는 메서드(peek 메서드 )
    public int peek() throws EmptyIntQueueException{
        if(num <= 0){
            throw new EmptyIntQueueException();
        }
        return que[front];
    }
    
    // 큐에서 x를 찾아 인덱스를 반환
    public int indexOf(int x){
        for(int i=0; i<num; i++){
            int idx = (i+front) % max;
            if(que[idx] == x){    // 검색 성공
                return idx;
            }
        }
        return -1;                    // 검색 실패
    }
    
    // 큐을 비움
    public void clear(){
        num = front = rear = 0;
    }
    
    // 큐의 용량을 반환
    public int capacity(){
        return max;
    }
    
    // 큐에 쌓여있는 데이터 수를 반환
    public int size(){
        return num;
    }
    
    // 큐이 비어있는가?
    public boolean isEmpty(){
        return num <= 0;
    }
    
    // 큐이 가득찼는가?
    public boolean isFull(){
        return num >= max;
    }
    
    // 큐 안의 모든 데이터를 프런트 -> 리어 순으로 출력
    public void dump(){
        // que[0] 10 que[1] 9 que[2] 8
        // num = 3
        // int x = 10, num = 2,    front = 1
        if(num <= 0){
            System.out.println("큐이 비어있습니다.");
        }else{
            // i=0 i<2 que[(0+1)%64 que[(1+1)
            // 2%64
            for(int i=0; i<num; i++){
                System.out.print(que[(i+front) % max] + " ");
            }
            System.out.println();
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        IntQueue queue = new IntQueue(64);    // 최대 64개를 푸시할 수 있는 큐
        
        while(true){
            System.out.println("현재 데이터 수 : " + queue.size() + " / " + queue.capacity()); 
            System.out.print("(1) 인큐 (2) 디큐 (3) 피크 (4) 덤프 (0) 종료 : ");
            int menu = scanner.nextInt();
            if(menu == 0) break;
            
            int x;
            switch(menu){
            
            case 1:
                System.out.print("데이터 : ");
                x = scanner.nextInt();
                try{
                    queue.enque(x);
                }catch(IntQueue.OverflowIntQueueException e){
                    System.out.println("큐가 가득찼습니다.");
                }
                break;
                
            case 2:
                try{
                    x = queue.deque();
                    System.out.println("디큐한 데이터는 " + x + "입니다.");
                }catch(IntQueue.OverflowIntQueueException e){
                    System.out.println("큐가 비어있습니다.");
                }
                break;
 
            case 3:
                try{
                    x = queue.peek();
                    System.out.println("피크한 데이터는 " + x + "입니다.");
                }catch(IntQueue.OverflowIntQueueException e){
                    System.out.println("큐가 비어있습니다.");
                }
                break;
 
            case 4:
                queue.dump();
                break;
            }
        }
    }
}
cs


결과




3. 링 버퍼의 활용


링 버퍼는 오래된 데이터를 버리는 용도로 사용할 수 있다.

예를 들면 요소의 개수가 n인 배열에 계속 데이터가 입력되면 

가장 최근에 들어온 데이터 n개만 저장하고 오래된 데이터는 버리는 용도이다.


배열의 길이는 10인데 정수입력이 12개가 들어온다면

정수 입력은 가장 최근에 입력한 10개의 데이터만 링 버퍼에 남아있다.

예전 데이터는 버리는 것이다.


 

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
package myTest1;
 
import java.util.Scanner;
 
public class LastElements {
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        final int N = 10;
        int[] a = new int[N];            // 입력 받은 값을 저장
        int cnt = 0;                            // 입력 받은 개수
        int retry;                                // 다시 한 번?
        
        System.out.println("정수를 입력하세요.");
        
        do{
            System.out.printf("%d번째 정수: ", cnt+1);
            a[cnt++ % N] = scanner.nextInt();
            System.out.print("계속 할까요? (예. 1 / 아니오. 0) : ");
            retry = scanner.nextInt();
        }while(retry == 1);
        
        int i = cnt - N;
        if(i <0) i = 0;
        
        for(;i<cnt;i++){
            System.out.printf("%2d번째 정수=%d\n", i+1, a[i%N]);
        }
        
    }
}
cs


결과




소스코드 첨부


myTest1.zip




'전체 > 알고리즘' 카테고리의 다른 글

8퀸 문제, 가지뻗기, 분기한정법 사용 구현  (2) 2018.10.07
재귀를 사용한 팩토리얼, 최대공약수, 하노이탑 구현  (0) 2018.10.07
스택 알고리즘 구현  (0) 2018.10.03
이진검색 알고리즘 (구현 메소드 사용, Arrays.binarySearch 라이브러리 사용)  (0) 2018.10.03
선형 검색 while, for, 보초법 사용하여 구현하기 (검색 알고리즘)  (0) 2018.09.30

+ Recent posts

티스토리툴바