1. SQL EXPLAIN 정리


1.1 부서 테이블


1
2
3
select * 
  from dbadev.dept
;
cs



부서테이블에는 4개의 행 ( 4rows returned )


1.2 직원 테이블


1
2
3
select * 
  from dbadev.emp
;
cs





직원테이블에는 14개의 행 ( 14rows returned )


1.3 부서와 직원 테이블을 내부조인



1
2
3
4
5
6
7
8
9
10
11
SELECT a.deptno
     , a.dname
     , a.loc
     , b.empno
     , b.ename
     , b.job
  FROM dbadev.dept as a
 INNER JOIN dbadev.emp as b
    ON a.deptno = b.deptno
 WHERE a.deptno= '20'
;
cs




1.4 EXPLAIN을 사용한 부서테이블과 직원테이블 내부조인 쿼리 실행결과


1
2
3
4
5
6
7
8
9
10
11
12
EXPLAIN
SELECT a.deptno
     , a.dname
     , a.loc
     , b.empno
     , b.ename
     , b.job
  FROM dbadev.dept as a
 INNER JOIN dbadev.emp as b
    ON a.deptno = b.deptno
 WHERE a.deptno= '20'
;
cs





MySQL 실행 계획 항목 설명


1. id

쿼리의 실행 순서대로 1부터 순차적으로 값을 부여. 즉 쿼리의 실행 순서라고 봐도 무방함.

다만 join 의 경우엔 하나의 구문에서 두개 이상의 테이블을 참조하기때문에 모든 테이블에 같은 순번이 부여됨.



2. select_type

select 구문의 실행 타입.


 속성값

 내용

 SIMPLE

 단순 select 구문으로 별다른 조인이나 서브쿼리가 없음.

 PRIMARY

 서브쿼리를 이용할 경우 서브쿼리의 부모가 되는 select 쿼리

 union을 사용할 경우 union 의 첫번째 select 쿼리.

 UNION

 union을 사용한 쿼리에서 첫번째를 제외한 나머지 select 쿼리.

 DEPENDENT UNION

 UNION과 기본적으로 동일하나 외부쿼리에 영향을 받음

 UNION RESULT

 UNION 쿼리의 결과

 UNCACHEABLE UNION

 UNION과 기본적으로 동일하나 공급되는 모든 값에 대해 UNION 쿼리를 재처리

 SUBQUERY

 서브쿼리 또는 서브쿼리를 구성하는 첫번째 select 구문

 DEPENDENT SUBQUERY

 SUBQUERY와 기본적으로 동일하나 외부쿼리에 영향을 받음
 UNCACHEABLE SUBQUERY SUBQUERY와 기본적으로 동일하나 입력 값에 의한 캐싱을 이용할 수 없음


3. table


테이블명. 약칭(Alias)을 사용할 경우 약칭이 표시됨


4. type


단일 테이블만 사용된 쿼리일 경우 : 테이블 access 형태

두 개 이상의 테이블이 조인된 SQL 일 경우 : 테이블 간의 조인 형태

아래 목록의 순서는 성능이 좋은 것 부터 나열되어 있음 


 속성값

 내용

 sytem

 테이블에 row가 1건이라 매칭되는 row도 1건인 경우.

 const

 옵티마이저가 unique/primary key를 사용하여 매칭되는 row가 1건인 경우.

 eq_ref

 1:1의 join 관계

 unique/primary key를 사용하여 join을 처리함.

 ref

 1:n의 join 관계

 non-unique 인덱스가 사용되거나, 복합키로 구성된 인덱스 중, 

 일부 컬럼만 이용하여 조인될 경우

 ref_or_null

 ref와 동일하나 null 값에 대한 최적화가 되어있음.

 fulltext

 fulltext 인덱스를 사용

 index_merge

 동일한 테이블에서 두개 이상의 인덱스가 동시에 사용됨.(fulltext 인덱스는 제외)
 unique_subquery 서브쿼리에서 unique한 값이 생성되는 경우
 index lookup function이 사용됨.(서브쿼리 최적화)
 index_subquery unique_subquery와 비슷하나 결과값이 unique하지 않은 경우
 range 주어진 범위내의 row를 스캔함
 범위내의 row가 많으면 많을수록 성능이 저하됨
 index 인덱스를 사용하긴 하나 전체 인덱스 block을 스캔함.
 즉 인덱스를 사용하긴 하나 all 타입과 흡사함
 all 전체 데이터 block을 스캔.(full table scan)


5. possible_keys

옵티마이저가 쿼리 처리를 위해 고려한 인덱스 후보. 즉 사용가능한 인덱스들의 리스트.

possible_keys와 key값은 항상 같지 않다. 즉 옵티마이저가 인덱스를 고려했지만 사용하지 않을수도 있음.


6. key

옵티마이저가 실제로 사용한 인덱스 키.

type값이 index_merge 일때 key값은 사용된 모든 인덱스 키를 출력함.



7. key_len

옵티마이저가 사용한 인덱스 키의 길이값. key컬럼에서 인덱스가 언급되지 않았다면 null값.

key_len값으로 옵티마이저가 실제 복수 컬럼키중 얼마나 많은 부분을 사용할 것인지 알수 있다.


8. ref

행을 추출하는데 키와 함께 사용된 컬럼이나 상수값.



9. rows

쿼리를 수행하기 위해 검색해야 할 row의 개수. 인덱스와 조건을 최적화 해서 row의 개수를 줄이면 줄일수록 퍼포먼스가 향상됨.



10. extra

옵티마이저가 쿼리를 해석한 추가적인 정보를 출력함





위쪽에 정리된 표를 바탕으로 EXPLAIN 실행결과



1번째 row를 해석하면


id가 1 (쿼리의 실행 순서가 1번째임)

SIMPLE (단순 select 구문)

테이블명은 dept 테이블을 alias로 명시한 a로 표시

const (옵티마이저가 unique/primary key를 사용하여 매칭되는 row가 1건인 경우 표시됨, a.deptno = 20으로 명시했으므로)

옵티마이저가 쿼리 처리를 위해 고려한 인덱스 후보는 PRIMARY

옵티마이저가 실제로 사용한 인덱스 키 PRIMARY

옵티마이저가 사용한 인덱스 키의 길이값 4

행을 추출하는데 키와 함께 사용된 컬럼이나 상수 4

쿼리를 수행하기 위해 검색해야 할 row의 개수 1


2번째 row를 해석하면


id가 1 (쿼리의 실행 순서가 1번째임)

SIMPLE (단순 select 구문)

테이블명은 emp 테이블을 alias로 명시한 b로 표시

ALL 전체 데이터 block을 스캔.(full table scan)

쿼리를 수행하기 위해 검색해야 할 row의 개수 14

Using where : where절이 다음 조인에 사용될 row나 출력될 row의 개수를 제한하는 경우 나온다.



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

MySQL function 만들기  (3) 2019.07.17
MySQL 계층형 쿼리 구현하기  (13) 2019.07.16
ANSI Syntax and Conventional syntax(non-ANSI) 안시조인 사용 이유  (0) 2018.10.29
group by 이해하기  (0) 2018.10.24
where case문, or문 사용하기  (1) 2018.06.20


1. 힙정렬의 정의


힙이란 무엇인가?  힙은 쌓아놓음. 쌓아놓은 더미의 뜻의 단어이다.


선택정렬을 응용한 알고리즘인 힙정렬은 힙의 특성을 이용해서 정렬을 수행한다.


힙은 부모의값이 자식의 값보다 항상 크다는 조건을 만족하는 완전이진트리이다.

이때 부모의 값이 자식보다 항상 작아도 힙이라고한다.(부모와 자식요소의 관계만 일정하면 된다)


부모와 자식관계는 항상 부모의값 >= 자식의값이다. 

따라서 힙의 가장 위쪽에 있는 루트가 가장 큰값이 된다.


힙에서 부모와 자식 관계는 일정하지만 형제사이의 대소관계는 일정하지 않다.



2. 트리의 개념


트리의 가장 윗부분을 루트(root)라고 한다. 그리고 요소의 상하관계를 부모(parent)와 자식(child)이라고 한다. 자식 간의 관계는 형제(sibling)이라고 한다.

완전이진트리란 트리의 한 종류를 말한다. 사람도 유전적인 특징에 의해 분류하는 것 처럼 트리의 종류도 여러가지다. 완전이진트리의 특징은 '완전이진' 상태라는 것이다. 여기서 '완전' 이라는 말은 부모는 자식을 왼쪽부터 추가하는 모양을 유지한다는 뜻이다. 그리고 '이진'이라는 말은 부모가 가질 수 있는 자식의 개수는 최대 2개다 라는 의미이다.


힙의 요소를 배열에 저장하는 과정은 다음 그림과 같다. 가장 위쪽부터 a[0]에 넣고 한단계 아래요소를 왼쪽부터 오른쪽으로 인덱스의 값을 1씩 늘리면서 배열의 각 요소에 힙의 요소를 대입한다.






이 과정을 거치면 부모와 자식의 인덱스 사이에 관계가 성립한다.


1. 부모는 a[(i-1)/2]

2. 왼쪽 자식은 a[i*2+1]

3. 오른쪽 자식은 a[i*2+2]


a[1] 을 저 공식에 대입해보면 부모는 a[0] 왼쪽 자식은 a[3] 8 , 오른쪽 자식은 a[4] 3 이 된다.



3. 힙정렬의 특징


가장 큰 값이 루트에 위치하는 특징을 이용하는 정렬 알고리즘이다.

힙에서 가장 큰 값인 루트를 꺼내는 작업을 반복하고 그 값을 늘어놓으면 배열은 정렬을 마치게 된다.

힙정렬은 선택정렬을 응용한 알고리즘이며 힙에서 가장 큰 값인 루트를 꺼내고 남은 요소에서 다시 가장 큰값을 구해야 한다.

다시 말해 힙으로 구성된 10개의 요소에서 가장 큰값을 없애면 나머지 9개의 요소 중에서 가장 큰값을 루트로 정해야한다.

따라서 나머지 9개의 요소로 만든 트리도 힙의 형태를 유지할 수 있도록 재구성해야 한다.



힙에서 루트인 10을 꺼낸다. 비어있는 루트 위치로 힙의 마지막 요소(1)을 옮긴다. 이때 1 이외의 요소는 힙 상태를 유지한다.





루트로 이동시킨 1을 올바른 위치로 보내야 한다. 1의 자식은 9와 5인데 힙이 되려면 3개의 값 가운데 가장 큰값이 위쪽에 있어야 한다.

부모의 값>=자식의 값 이라는 힙의 조건을 만족하려면 두 자식을 비교하여 큰 쪽인 9 와 바꾸면 된다.

그러면 1이 왼쪽으로 내려온다.



1의 자식은 8과 3이다. 3개의 값 중 가장 큰 값이 위쪽에 있어야 하므로 8과 위치를 바꾼다.



1의 자식은 6과 7이다. 3개의 값 중 가장 큰 값이 위쪽에 있어야 하므로 7과 위치를 바꾼다.


1. 루트를 꺼낸다.

2. 마지막 요소를 루트로 이동시킨다.

3. 자기보다 큰 값을 가지는 자식요소와 자리를 바꾸며 아래쪽으로 내려가는 작업을 반복한다. 

이때 자식의 값이 작거나 잎에 다다르면 작업이 종료된다.


4. 힙정렬 알고리즘 흐름


1. 힙의 루트 (a[0])에 있는 가장 큰 값(10)을 꺼내 배열 마지막 요소(a[9])와 바꾼다.


2. 가장 큰 값을 a[9]로 옮기면 a[9]는 정렬을 마치게 된다. 

앞에서 살펴본 순서대로 a[0] ~ a[8] 의 요소를 힙으로 만든다. 

그 결과 두번째로 큰 요소인 9가 루트에 위치하게 된다. 

힙의 루트 a[0] 에 있는 가장 큰 값인 9를 꺼내 아직 정렬하지 않은 부분의 마지막 요소인 a[8]과 바꾼다.


3. 두번쨰로 큰 값을 a[8] ~ a[9] 는 정렬을 마치게 된다. 

그런 다음 a[0] ~ a[7] 의 요소를 힙으로 만든다.

그 결과 세번째로 큰 요소인 8이 루트에 위치하게 된다. 

힙의 루트 a[0]에 있는 가장 큰 값인 8을 꺼내 아직 정렬하지 않은 부분의 마지막 요소인 a[7]과 바꾼다.


 

위 설명을 그림으로 표현하면




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
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
176
177
package myTest4;
 
import java.util.Scanner;
 
// GregorianCalendar형의 배열을 정렬하는 프로그램
// 1. 자연정렬이 필요한 배열 - 요소의 대소관계를 비교하여 정렬합니다.
public class HeapSort {
    
    // 출력 space1~9 칸수 정의
    static String sp1 = " ", sp2 = "  ", sp3 = "   ";
    static String sp4 = "    ", sp5 = "     ", sp6 = "      ";
    static String sp7 = "       ", sp8 = "        ";
    static String sp9 = "        ";
    
    static void swap(int[] a, int idx1, int idx2){
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }
    
    static void downHeap(int[] a, int left, int right){
        int temp = a[left];    // 루트
        int child;                    // 큰 값을 가진 노드
        int parent;                // 부모
        
        for(parent = left; parent < (right + 1) / 2; parent = child){
            int cl = parent*2+1;        // 왼쪽 자식
            int cr = cl+1;                // 오른쪽 자식
            child = (cr <= right && a[cr] > a[cl]) ? cr : cl;     // 큰 값을 가진 노드를 자식에 대입
            if(temp >= a[child]){
                break;
            }
            a[parent] = a[child];
        }
        a[parent] = temp;
        
        /* 트리구조 출력하는 소스 시작 */
        int i=0;
        int arrLength  =a.length;
        int k=3;
        int m = 2, n =2;
        int nfloor = 2;
        if(arrLength  > k && arrLength  > 2){
            do{
                // 3,7, 15
                m= m*n; // m=4, m= 8
                k = k+m; // k=7, k= 15
                nfloor++;    // nfloor= 3, nfloor = 4 
            }while(arrLength  > k); // myvalue1 = 10
        }
            
        // if arrLength == 4, 5, 10, 15
        while(i< nfloor-1){ // i=0; nfloor = 4
            String lbranch = "/";
            String rbranch = "\\";
            if(i==0){ // 1층
                System.out.print(sp9+sp9+sp3);
                System.out.println(a[i]);
            }else if(i==1){
                System.out.print(sp9+sp6);
                System.out.print(lbranch);
                System.out.print(sp9+sp3);
                System.out.print(rbranch);
                System.out.println();
                System.out.println(sp9+sp5+a[i]+sp9+sp5+a[i+1]);
            }else{ // 2층, 3층, 4층
                if(nfloor == 3){
                    nfloor3(a, arrLength, lbranch, rbranch, true);
                }else if(nfloor == 4){
                    nfloor3(a, arrLength, lbranch, rbranch, false);
                    int count = arrLength - 8; // 15-7 =8 
                    // 4층 막대기 그리기
                    for(int num=0; num<=count; num++){
                        if(num % 2 == 0){
                            System.out.print(sp6);
                            System.out.print(lbranch);
                        }else{
                            System.out.print(sp3);
                            System.out.print(rbranch);
                        }
                    }
                    System.out.println();
                    
                    // 4층 숫자 출력하기
                    for(int num=8; num<=arrLength; num++){ // 10,9,5,8,3
                        if(num % 2 == 0){
                            System.out.print(sp5);
                            System.out.print(a[num-1]);
                        }else{
                            System.out.print(sp3);
                            System.out.print(a[num-1]);
                        }
                    }
                    System.out.println();
                    System.out.println();
                }
            }
            i++;
        }
        /* 트리구조 출력하는 소스 끝 */
    }
    
    private static void nfloor3(int[] a, int arrLength, String lbranch, String rbranch, boolean flag) {
        // if arrLength 4 4
        int count;
        if(arrLength <= 7){
            count = arrLength - 4;            
        }else{
            count = 3;            
            arrLength = 7;
        }
        // 3층 막대기 출력
        for(int num=0; num<=count; num++){
            if(num % 2 == 0){
                if(num==0){
                    System.out.print(sp7+sp3);
                }else{
                    System.out.print(sp9);
                }
                System.out.print(lbranch);
            }else{
                System.out.print(sp5);
                System.out.print(rbranch);
            }
        }
        System.out.println();
        
        // 3층 숫자 출력
        for(int num=4; num<=arrLength; num++){ // 10,9,5,8,3
            if(num % 2 == 0){
                if(num==4){
                    System.out.print(sp9);
                    System.out.print(a[num-1]);
                }else{
                    System.out.print(sp4);
                    System.out.print(a[num-1]);
                }
            }else{
                System.out.print(sp8);
                System.out.print(a[num-1]);
            }
        }
        if(flag){
            System.out.println();
        }
        System.out.println();
    }
 
    static void heapSort(int[] a, int n){
        for(int i=(n-1)/2; i>=0; i--){    // a[i]~a[n-1]를 힙으로 만들기
            downHeap(a, i, n-1);
        }
        for(int i=n-1; i>0; i--){
            swap(a, 0, i);        // 가장 큰 요소와 아직 정렬되지 않은 부분의 마지막 요소를 교환
            downHeap(a, 0, i-1);        // a[0] ~ a[i-1]을 힙으로 만듭니다.
        }
    }
    
    public static void main(String[] args){
        Scanner stdIn = new Scanner(System.in);
        System.out.println("힙 정렬");
        System.out.println("요솟수: ");
        int nx = stdIn.nextInt();
        int[] x = new int[nx];
        
        for(int i=0; i<nx; i++){
            System.out.print("x["+i+"]: ");
            x[i] = stdIn.nextInt();
        }
        
        heapSort(x,nx);    // 배열 x를 힙 정렬합니다.
        System.out.println("오름차순으로 정렬했습니다.");
        for(int i=0; i<nx; i++){
            System.out.println("x[" + i + "]=" + x[i]);
        }
    }
}
cs


결과


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
힙 정렬
요솟수: 
10
x[0]: 10
x[1]: 9
x[2]: 5
x[3]: 8
x[4]: 3
x[5]: 2
x[6]: 4
x[7]: 6
x[8]: 7
x[9]: 1
                   10
              /           \
             9             5
          /     \        /     \
        8        3     2        4
      /   \      /
     6    7     1
 
                   10
              /           \
             9             5
          /     \        /     \
        8        3     2        4
      /   \      /
     6    7     1
 
                   10
              /           \
             9             5
          /     \        /     \
        8        3     2        4
      /   \      /
     6    7     1
 
                   10
              /           \
             9             5
          /     \        /     \
        8        3     2        4
      /   \      /
     6    7     1
 
                   10
              /           \
             9             5
          /     \        /     \
        8        3     2        4
      /   \      /
     6    7     1
 
                    9
              /           \
             8             5
          /     \        /     \
        7        3    2        4
      /   \      /
     6    1     10
 
                    8
              /           \
             7             5
          /     \        /     \
        6        3     2        4
      /   \      /
     1    9     10
 
                    7
              /           \
             6             5
          /     \        /     \
        1        3     2        4
      /   \      /
     8    9     10
 
                    6
              /           \
             4             5
          /     \        /     \
        1        3     2        7
      /   \      /
     8    9     10
 
                    5
              /           \
             4             2
          /     \        /     \
        1        3     6        7
      /   \      /
     8    9     10
 
                    4
              /           \
             3             2
          /     \        /     \
        1        5    6        7
      /   \      /
     8    9     10
 
                    3
              /           \
             1             2
          /     \        /     \
        4        5     6        7
      /   \      /
     8    9     10
 
                    2
              /           \
             1             3
          /     \        /     \
        4        5     6        7
      /   \      /
     8    9     10
 
                    1
              /           \
             2             3
          /     \        /     \
        4        5     6        7
      /   \      /
     8    9     10
 
오름차순으로 정렬했습니다.
x[0]=1
x[1]=2
x[2]=3
x[3]=4
x[4]=5
x[5]=6
x[6]=7
x[7]=8
x[8]=9
x[9]=10
cs


소스코드와 작업파일 첨부


myTest4.zip

181103 작업파일.pptx



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

병합정렬  (0) 2018.11.03
퀵정렬  (0) 2018.11.03
쉘 정렬  (0) 2018.10.27
단순 선택정렬, 단순 삽입정렬  (0) 2018.10.27
버블정렬 여러가지 방법 구현  (0) 2018.10.09


1. 병합정렬


병합정렬은 배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬을 수행하는 알고리즘이다.




배열 a,와 b를 비교하여 작은 값을 꺼내 c에 넣는다.



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
package myTest4;
 
import java.util.Scanner;
 
public class MergeArray {
    
    // 배열 요소 a[idx1]과 a[idx2]의 값을 바꿉니다.
    static void swap(int[] a, int idx1, int idx2){
        int t = a[idx1]; 
        a[idx1] = a[idx2];
        a[idx2] = t;
    }
    
    // 정렬을 마친 배열 a,b를 병합하여 배열 c에 저장합니다.
    static void merge(int[] a, int na, int[] b, int nb, int[] c){
        int pa = 0;
        int pb = 0;
        int pc = 0;
        
        while(pa < na && pb < nb){        // 작은 값을 저장합니다.
            c[pc++] = (a[pa] <= b[pb]) ? a[pa++] : b[pb++];
        }
        while(pa < na){            // a에 남아있는 요소를 복사합니다.
            c[pc++] = a[pa++];
        }
        
        while(pb < nb){
            c[pc++] = b[pb++];
        }
    }
    
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int[] a = {2,4,6,8,11,13};
        int[] b = {1,2,3,4,9,16,21};
        int[] c = new int[13];
        
        System.out.println("두 배열의 병합");
        merge(a, a.length, b, b.length, c);        // 배열 a와 b를 병합하여 c에 저장
        System.out.println("배열 a와 b를 병합하여 배열 c에 저장했습니다.");
        System.out.println("배열 a:");
        for(int i=0; i< a.length; i++){
            System.out.println("a["+i+"]=" + a[i]);
        }
        System.out.println("배열 b:");
        for(int i=0; i< b.length; i++){
            System.out.println("b["+i+"]=" + b[i]);
        }
        System.out.println("배열 c:");
        for(int i=0; i< c.length; i++){
            System.out.println("c["+i+"]=" + c[i]);
        }
    }
}
cs


결과


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
두 배열의 병합
배열 a와 b를 병합하여 배열 c에 저장했습니다.
 
배열 a:
a[0]=2
a[1]=4
a[2]=6
a[3]=8
a[4]=11
a[5]=13
 
배열 b:
b[0]=1
b[1]=2
b[2]=3
b[3]=4
b[4]=9
b[5]=16
b[6]=21
 
배열 c:
c[0]=1
c[1]=2
c[2]=2
c[3]=3
c[4]=4
c[5]=4
c[6]=6
c[7]=8
c[8]=9
c[9]=11
c[10]=13
c[11]=16
c[12]=21
cs



정렬을 마친 배열의 병합을 응용하여 분할 정복법에 따라 정렬하는 알고리즘을 병합 정렬(merge sort)라고 한다.

먼저 배열을 앞부분과 뒷부분으로 나눈다.  배열의 요소 갯수가 12개 이므로 6개의 배열로 각각 나눈다.

두 배열을 각각 정렬하고 병합하면 배열 모두를 정렬 할 수 있다.




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
package myTest4;
 
import java.util.Scanner;
 
public class MergeSort {
    
    static int[] buff;        // 작업용 배열
    
    // a[left] ~ a[right] 를 재귀적으로 병합 정렬
    static void __mergeSort(int[] a, int left, int right){
        if(left<right){
            int i;
            int center = (left+right) / 2;
            int p = 0;
            int j = 0;
            int k = left;
            
            __mergeSort(a, left, center);        // 배열의 앞부분을 병합 정렬합니다.
            __mergeSort(a, center+1, right); // 배열의 뒷부분을 병합 정렬합니다.
            
            for(i= left; i<=center; i++){
                buff[p++] = a[i];
            }
            
            while(i<=right && j < p){
                a[k++] = (buff[j] <= a[i])? buff[j++] : a[i++];
            }
            
            while(j<p){
                a[k++] = buff[j++];
            }
        }
    }
    
    // 병합 정렬
    static void mergeSort(int[] a, int n){
        buff = new int[n];        // 작업용 배열을 생성합니다.
        __mergeSort(a,0,n-1);    // 배열 전체를 병합 정렬합니다.
        buff = null;                    // 작업용 배열을 해제합니다.
    }
    
    public static void main(String[] args){
        Scanner stdIn = new Scanner(System.in);
        
        System.out.println("병합 정렬");
        System.out.print("배열의 길이 : ");
        int nx = stdIn.nextInt();
        int[] x = new int[nx];
        for(int i=0; i< nx; i++){
            System.out.print("x[" + i + "] : ");
            x[i] = stdIn.nextInt();
        }
        
        mergeSort(x,nx);        // 배열 x를 병합 정렬합니다.
        System.out.println("오름차순으로 정렬했습니다.");
        for(int i=0; i<nx; i++){
            System.out.println("X[" + i + "]= " + x[i]);
        }
    }    
}
 
cs



결과


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
병합 정렬
배열의 길이 : 10
x[0] : 10
x[1] : 9
x[2] : 8
x[3] : 7
x[4] : 6
x[5] : 5
x[6] : 4
x[7] : 3
x[8] : 2
x[9] : 1
오름차순으로 정렬했습니다.
X[0]= 1
X[1]= 2
X[2]= 3
X[3]= 4
X[4]= 5
X[5]= 6
X[6]= 7
X[7]= 8
X[8]= 9
X[9]= 10
cs



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

힙정렬, 완전이진트리  (2) 2018.11.04
퀵정렬  (0) 2018.11.03
쉘 정렬  (0) 2018.10.27
단순 선택정렬, 단순 삽입정렬  (0) 2018.10.27
버블정렬 여러가지 방법 구현  (0) 2018.10.09


1. 퀵정렬


퀵정렬은 일반적으로 사용되고 있는 아주 빠른 정렬 알고리즘이다.

퀵정렬은 각 그룹에 대해 피벗 설정과 그룹 나눔을 반복하며 모든 그룹 1명이 되면 정렬을 마친다.



2. 배열을 두 그룹으로 나누기 (피벗을 구하고 그룹을 나누는 과정)




그룹을 나누려면 피벗 이하의 요소를 배열 왼쪽으로, 피벗 이상의요소를 오른쪽으로 옮겨야 한다.


1. a[pl] >= x 가 성립하는 요소를 찾을때까지 pl을 오른쪽으로 스캔한다.

2. a[pr] <= x가 성립하는 요소를 찾을떄까지 pr을 오른쪽으로 스캔한다.


이 과정을 통해 pl과 pr이 멈추게 되고 pl이 위치한 지점은 피벗값 이상의 요소가 있는 지점이고

pr이 위치한 지점은 피벗값 이하의 요소가 있는 지점이다.


왼쪽(pl)과 오른쪽(pr) 커서가 가리키는 요소 a[pl]과 a[pr]의 값을 교환한다.

그러면 피하이하의 값은 왼쪽으로 이동하고 피벗이상의 값은 오른쪽으로 이동한다.



교환 후 다시 스캔하면 같이 멈추게된다.


교환 후 다시 스캔하면 두 커서가 교차하게 된다.


pl 과 pr이 교차하면 그룹을 나누는 과정이 끝나고 배열은 두그룹으로 나눠진다.



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
65
package myTest4;
 
import java.util.Scanner;
 
public class Partition {
    
    // 배열 요소 a[idx1] 과 a[idx2] 의 값을 바꾼다.
    static void swap(int[] a, int idx1, int idx2){
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }
    
    // 배열을 나눈다.
    static void partitionArray(int[] a, int n){
        int pl = 0;            // 왼쪽커서
        int pr = n-1;         // 오른쪽커서
        int x = a[n/2]; // 피벗(가운데 위치 값)
        // x = a[5]
        // a[0] 
        do{
            while(a[pl] < x) pl++;
            while(a[pr] > x) pr--;
            if(pl <= pr){
                swap(a, pl++, pr--);
            }
        }while(pl <= pr);
        
        System.out.println("피벗의 값은 " + x + "입니다.");
        
        System.out.println("피벗 이하의 그룹");
        for(int i=0; i<= pl-1; i++){
            System.out.print(a[i] + " ");        // a[0] ~ a[pl-1]
        }
        System.out.println();
        
        if(pl > pr+ 1){
            System.out.println("피벗과 일치하는 그룹");
            for(int i= pr+1; i<=pl-1; i++){    // a[pr+1] ~ a[pl-1]
                System.out.print(a[i] + " ");
            }
            System.out.println();
        }
        
        System.out.println("피벗 이상의 그룹");
        for(int i=pr+1; i<n; i++){        // a[pr+1] ~ a[n-1]
            System.out.print(a[i] + " ");
        }
        System.out.println();
    }
    
    public static void main(String[] args){
        Scanner stdIn = new Scanner(System.in);
        System.out.println("배열을 나눕니다.");
        System.out.print("배열의 길이 : ");
        int nx = stdIn.nextInt();
        int[] x = new int[nx];
        
        for(int i=0; i<nx; i++){
            System.out.print("x["+i+"] : ");
            x[i] = stdIn.nextInt();
        }
        partitionArray(x, nx);            // 배열 x를 나눕니다.
    }
}
cs


결과


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
배열을 나눕니다.
배열의 길이 : 9
x[0] : 5
x[1] : 7
x[2] : 1
x[3] : 4
x[4] : 6
x[5] : 2
x[6] : 3
x[7] : 9
x[8] : 8
피벗의 값은 6입니다.
피벗 이하의 그룹
5 3 1 4 2 
피벗 이상의 그룹
6 7 9 8 
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
90
91
92
package myTest4;
 
import java.util.Scanner;
 
import myTest1.IntStack;
 
public class QuickSort {
    
    // 배열 요소 a[idx1]과 a[idx2]의 값을 바꿉니다.
    static void swap(int[] a, int idx1, int idx2){
        int t = a[idx1]; 
        a[idx1] = a[idx2];
        a[idx2] = t;
    }
    
    // 재귀 사용 퀵정렬
    static void quickSort(int[] a, int left, int right){
        int pl = left;                    // 왼쪽 커서
        int pr = right;                // 오른쪽 커서
        int x = a[(pl+pr ) /2];    //피벗
        
        System.out.printf("a[%d]~a[%d] : {",left, right);
        for(int i = left; i<right; i++){
            System.out.printf("%d, ", a[i]);
        }
        System.out.printf("%d}\n", a[right]);
        
        do{
            while(a[pl] < x) pl++;
            while(a[pr] > x) pr--;
            if(pl <= pr){
                swap(a, pl++, pr--);
            }
        }while(pl <= pr);
        
        if(left < pr) quickSort(a, left, pr);
        if( pl< right) quickSort(a, pl, right);
        
    }
    
    // 비재귀 사용 퀵정렬
    static void notRecurQuickSort(int[] a, int left, int right){
        IntStack lstack = new IntStack(right - left + 1);
        IntStack rstack = new IntStack(right - left + 1);
        
        lstack.push(left);
        rstack.push(right);
        
        while(lstack.isEmpty() != true){
            int pl = left = lstack.pop();        // 왼쪽 커서
            int pr = right = rstack.pop();     // 오른쪽 커서
            int x = a[(left + right) / 2];        // 피벗
            
            do{
                while(a[pl] < x) pl++;
                while(a[pr] > x) pr--;
                if(pl <= pr){
                    swap(a, pl++, pr--);
                }
            }while(pl <= pr);
            
            if(left < pr){
                lstack.push(left);        // 왼쪽 그룹 범위의
                rstack.push(pr);        // 인덱스를 푸시합니다.
            }
            if(pl < right){
                lstack.push(pl);            // 오른쪽 그룹 범위의
                rstack.push(right);    // 인덱스를 푸시합니다.
            }    
        }
    }
    
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        System.out.println("퀵정렬");
        System.out.print("배열의 길이 : ");
        int nx = scanner.nextInt();
        int[] x = new int[nx];
        
        for(int i=0; i<nx; i++){
            System.out.print("x["+i+"] : ");
            x[i] = scanner.nextInt();
        }
        
        quickSort(x, 0, nx-1);            
//        notRecurQuickSort(x, 0, nx-1);
        System.out.println("오름차순으로 정렬했습니다.");
        for(int i=0; i<nx; i++){
            System.out.println("x["+i+"]=" + x[i]);
        }
    }
}
cs


결과


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
퀵정렬
배열의 길이 : 9
x[0] : 5
x[1] : 8
x[2] : 4
x[3] : 2
x[4] : 6
x[5] : 1
x[6] : 3
x[7] : 9
x[8] : 7
a[0]~a[8] : {5, 8, 4, 2, 6, 1, 3, 9, 7}
a[0]~a[4] : {5, 3, 4, 2, 1}
a[0]~a[2] : {1, 3, 2}
a[0]~a[1] : {1, 2}
a[3]~a[4] : {4, 5}
a[5]~a[8] : {6, 8, 9, 7}
a[5]~a[6] : {6, 7}
a[7]~a[8] : {9, 8}
오름차순으로 정렬했습니다.
x[0]=1
x[1]=2
x[2]=3
x[3]=4
x[4]=5
x[5]=6
x[6]=7
x[7]=8
x[8]=9
cs


퀵정렬에서 분할과정 출력을 통해 어떻게 분할 되는지 확인 할 수 있었다.




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

힙정렬, 완전이진트리  (2) 2018.11.04
병합정렬  (0) 2018.11.03
쉘 정렬  (0) 2018.10.27
단순 선택정렬, 단순 삽입정렬  (0) 2018.10.27
버블정렬 여러가지 방법 구현  (0) 2018.10.09


1. ajax 요청 공통 메소드


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
var myCommon = {};
myCommon.util = {
     // method : get/post , url : call url 
     // params    : json 형식 요청 데이터, callbackFunction : callback 함수명
    callAjax : function(method, url, type,params, callbackFunction ){
        if(method=="" || url==""){
            console.log("method or url empty");
            return false;
        }
 
        $.ajax({
             type : method
            , url : url
            , data : JSON.stringify(params)
            , contentType:'application/json; charset=utf-8'
            , dataType: type
            , success : function(response) {
                if (type == "html") {
                        $(document.getElementById(callbackFunction)).html(response);
                } else {
                    // Callback 함수 호출
                    if (typeof(callbackFunction) == "function")
                        callbackFunction(params, response);
                }
            }
            , error : function(jqXHR, error) {
                console.log(error);
            }
        });
    }
};  
cs



2. 버튼 클릭하여 json 형태 데이터를 ajax 공통 메소드에 태워 보내기


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
$(document).ready(function() {
    var processScript = true;
    var sendData = {};
 
    $("#ptcp").click(function(){
        // 버튼 여러번 클릭되지 않게 막기
        if(!processScript){
            alert("처리중입니다.");
            return;
        }
        
        var userName = $("#userName").val();
        var phoneNumber = $("#phoneNumber").val();
        var birthDt = $("#birthDt").val();
        var age = $("#age").val();
 
        sendData.userName = userName;
        sendData.phoneNumber = phoneNumber;
        sendData.birthDt = birthDt;
        sendData.age = age;
 
        if(!confirm("응모하시겠습니까?")){
            return;
        }
        ptcpEvent(sendData);
    });
 
    function ptcpEvent(sendData){
        var url = "@RequestMapping될 url 명시";
        var type   = "json";
        var requestData = sendData;
        console.log(JSON.stringify(requestData));
        processScript = false;
        myCommon.util.callAjax("POST", url, null,requestData, returnData.myResult);
    };
    
    var returnData = {
        myResult : function(request, response){
            console.log(request);    
            console.log(response);    
        }
    }
});
cs



'전체 > JS & Jquery' 카테고리의 다른 글

js primitive type  (0) 2019.03.10
자바스크립트 콜스택(call stack)  (0) 2019.03.09
시작페이지 설정, 즐겨찾기 설정 JS 소스  (0) 2018.10.31
JS Function Definitions Variable 자바스크립트 함수 선언방법  (0) 2018.10.28
게시판 페이징 ajax 스크립트  (2) 2018.08.17


1. 시작페이지, 즐겨찾기 JS


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
// 시작페이지 설정
$('#startPage').on('click', function() {
    var agent = navigator.userAgent.toLowerCase();
    if ((navigator.appName == 'Netscape' && agent.indexOf('trident') != -1) 
        || (agent.indexOf("msie") != -1)) {
        // ie일 경우
        if (agent.indexOf("msie") != -1) {
            document.body.style.behavior = 'url(#default#homepage)';
            document.body.setHomePage('http://www.naver.com');
        } else {
            alert("internet explorer(10버전 이하) 에서만 지원하는 기능입니다.");
        }
    } else {
        // ie가 아닐 경우
        alert("지원되지 않는 브라우저입니다.");
    }
});
 
// 즐겨찾기 설정
$('#favorite').on('click', function(e) {
    var bookmarkURL = "http://www.naver.com";
    var bookmarkTitle = document.title;
    var triggerDefault = false;
 
    if (window.sidebar && window.sidebar.addPanel) {
        // Firefox version < 23
        window.sidebar.addPanel(bookmarkTitle, bookmarkURL, '');
    } else if ((window.sidebar && (navigator.userAgent.toLowerCase().indexOf('firefox') > -1)) 
                || (window.opera && window.print)) { // Firefox version >= 23 and Opera Hotlist
        var $this = $(this);
        $this.attr('href', bookmarkURL);
        $this.attr('title', bookmarkTitle);
        $this.attr('rel', 'sidebar');
        $this.off(e); triggerDefault = true;
    } else if (window.external && ('AddFavorite' in window.external)) { // IE Favorite
        window.external.AddFavorite(bookmarkURL, bookmarkTitle);
    } else { // WebKit - Safari/Chrome
        alert((navigator.userAgent.toLowerCase().indexOf('mac') != -1 ? 'Cmd' : 'Ctrl') 
                + '+D 키를 눌러 즐겨찾기에 등록하실 수 있습니다.');
    }
    return triggerDefault;
});
cs



IE 10 버전 이하에서 시작페이지와 즐겨찾기 설정이 가능하다.

IE가 아닌 다른 브라우저로 클릭 이벤트를 발생시키면 지원하지 않는다는 alert창이 뜬다.





'전체 > JS & Jquery' 카테고리의 다른 글

자바스크립트 콜스택(call stack)  (0) 2019.03.09
버튼 클릭하여 json 형태 데이터 ajax 보내는 스크립트  (0) 2018.10.31
JS Function Definitions Variable 자바스크립트 함수 선언방법  (0) 2018.10.28
게시판 페이징 ajax 스크립트  (2) 2018.08.17
JS 문자열 막는 스크립트, 키보드 입력 글자 카운트 스크립트, 화면에서 여러번 클릭 막는 스크립트  (2) 2018.08.17


1.. Compare ANSI and Conventional(non-ANSI)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
-- Compare ANSI and Conventional
-- 1. ANSI Syntax
SELECT COUNT(*)
  FROM t1 a
 INNER JOIN t2 b
    ON a.cmpn_no = b.cmpn_no
 INNER JOIN t3 c
    ON b.cmpn_no = c.cmpn_no
 WHERE b.rgstr_id = 'abc'
   AND c.pimg_file_nm IS NOT NULL
;
-- 2. Conventional syntax
SELECT COUNT(*) 
  FROM t1 a
     , t2 b
     , t3 c
 WHERE a.cmpn_no = b.cmpn_no
   AND b.cmpn_no = c.cmpn_no
   AND b.rgstr_id = 'abc'
   AND c.pimg_file_nm IS NOT NULL
;
-- returns same results
cs



2. ANSI inner join 안 조건, 밖 조건


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
-- 조건의 위치가 달라질때
-- 1. inner join 안 조건
SELECT COUNT(*)
  FROM t1 a
 INNER JOIN t2 b
    ON a.cmpn_no = b.cmpn_no
   AND b.rgstr_id = 'abc'       -- a,b inner join 다음 조건1
 INNER JOIN t3 c
    ON b.cmpn_no = c.cmpn_no  -- b,c inner join 다음 조건2
   AND c.pimg_file_nm IS NOT NULL
;
-- 2. inner join 밖 조건
SELECT COUNT(*)
  FROM t1 a
 INNER JOIN t2 b
    ON a.cmpn_no = b.cmpn_no
 INNER JOIN t3 c
    ON b.cmpn_no = c.cmpn_no
 WHERE b.rgstr_id = 'abc'          -- a,b b,c inner join 다음 조건1
   AND c.pimg_file_nm IS NOT NULL -- 다음 조건2
;
-- returns same results
cs



ANSI 조인과 non-ANSI 조인의 결과는 같았다.


ANSI조인을 사용하는 이유는 


1. JOIN 절을 사용하면 관계 논리가 필터 논리 (WHERE)와 분리되므로 더 명확하고 이해하기 쉽다.

2. 외부 조인 구문 (+ 사용)이 모호하고 쿼리 결과가 구현에 따라 달라 지거나 쿼리를 전혀 해석 할 수없는 경우가 있다.

3. 우발적 인 교차 결합을 피할 수 있다.


ANSI JOIN 사용하는 것이 그렇지 않은 syntax를 사용하는 것 보다 안전하다.



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

MySQL 계층형 쿼리 구현하기  (13) 2019.07.16
SQL EXPLAIN 정리  (0) 2018.11.19
group by 이해하기  (0) 2018.10.24
where case문, or문 사용하기  (1) 2018.06.20
쿼리에서 select해서 update하기, 쿼리에서 select한 값을 list로 받아와서 update하기  (0) 2018.06.07


1. js function variable


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
// 화살표 함수
var arrowfunction = (a, b) => {
    if(a==1 && b==3){
        alert("Arrow function Execute");
    }else{
        alert("wrong");
    }
    return a;
}
 
// 함수명을 앞으로 뺀 함수 정의
var jsFunction = function(a, b) {
    if(a==1 && b==3){
        alert("jsFunction Execute");
    }else{
        alert("wrong");
    }
    return a;
}
 
// 일반적인 함수 정의
function nomalFunction(a, b){
    if(a==1 && b==3){
        alert("nomalFunction Execute");
    }else{
        alert("wrong");
    }
    return a;    
}
 
// 익명 함수 선언 및 바로실행
(function () {
    var x = "invokeSelf Function Execute"; 
    alert(x);
})();
 
// 각각의 결과값을 담기
var a1 = arrowfunction(1,3);
var b1 = jsFunction(1,3);
var c1 = nomalFunction(1,3);
 
alert(a1);
alert(b1);
alert(c1);
cs



자바스크립트 함수 선언을 function 함수명(인자) 가 아닌 여러가지 방법으로 표현할 수 있음을 확인했다.

또한 return 값이 있어도 되고 없어도 된다는 것과 함수선언과 동시에 호출이 가능한 함수 또한 알 수 있었다.



'전체 > JS & Jquery' 카테고리의 다른 글

버튼 클릭하여 json 형태 데이터 ajax 보내는 스크립트  (0) 2018.10.31
시작페이지 설정, 즐겨찾기 설정 JS 소스  (0) 2018.10.31
게시판 페이징 ajax 스크립트  (2) 2018.08.17
JS 문자열 막는 스크립트, 키보드 입력 글자 카운트 스크립트, 화면에서 여러번 클릭 막는 스크립트  (2) 2018.08.17
자바스크립트의 중괄호{} 대괄호[] key, value 배열 json 형식 구조 만들기  (2) 2018.08.16

+ Recent posts

티스토리툴바