정보처리산업기사 실기/알고리즘

응용 알고리즘 - 자료 구조

미웡할꺼야 2020. 11. 17. 16:55

석차 구하기

문제 : A회사는 25개 대리점을 가지고 있다. 이들 대리점의 전년도 매출액을 순서대로 읽어 들여 매출액을 토대로 대리점의 석차를 구한 후, 25개 대리점에 대하여 매출액과 석차를 함께 순서대로 출력하는 알고리즘을 제시하라.

(단, i번째 대리점에 대하여, A(i)는 매출액을 나타내고 R(i)는 석차를 나타낸다. 만일 매출액이 동일한 대리점이 존재할 경우 자신보다 상위자로 보지 않고 석차를 낮추지 않도록 한다.)

 

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
public class 석차구하기 {
 
    public static void main(String[] args) {
        int a[] = new int[25]; // 매출액 배열.
        int r[] = new int[25]; // 석차용 배열.
        
        // 매출액 및 석차용 배열 초기화 반복문.
        for(int i = 0 ; i < 25 ; i++) {
            a[i] = (int) (Math.random() * 100+ 1;
            r[i] = 1// 석차용 배열 초기화.
        }
        
        // 석차구하기 반복문.
        for(int i = 0 ; i < 25 ; i++) {
            for(int j = 0 ; j < 25 ; j++) {
                /*
                 * 현 매출액보다 큰 매출액이 있을 경우
                 * 해당 매출액 석차 증가.
                 */
                if(a[i] < a[j])
                    r[i] = r[i] + 1;
            }    
        }
        
        for(int i = 0 ; i < 25 ; i++)
            System.out.println(a[i] + " : " + r[i]);
    }
}
cs

 


선택 정렬

정의 : 배열에 9, 6, 7, 3, 5가 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자.

 

문제 : 학생 100명의 영어 성적을 오름차순으로 선택 정렬(Selection Sort)하는 알고리즘을 제시하라.

 

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
public class SelectionSort {
 
    public static void main(String[] args) {
        int e[] = { 95758510050 };
        int i = 0// n회전 인덱스 변수.
        int temp; // 임시 변수.
 
        // n회전 반복문.
        do {
            // 탐색용 인덱스 변수.
            // 한 회전이 끝날 때마다 초기화.
            int j = i + 1;
 
            // 선택정렬 반복문.
            do {
                // ex) e[0]이 e[1] 보다 클 경우
                // e[0] <=> e[1] 후 e[0]과 e[2,3,4] 비교
                if (e[i] > e[j]) {
                    temp = e[i];
                    e[i] = e[j];
                    e[j] = temp;
                }
                j = j + 1// 탐색용 인덱스 증가.
            } while (j < 5); // j ~ 배열 마지막까지 반복.
 
            i = i + 1// n회전용 인덱스 변수.
        } while (i < 4); // 모든 회전 끝날 때까지 반복.
 
        for (int a = 0; a < 5; a++)
            System.out.print(e[a] + " ");
        // 50 75 85 95 100
    }
}
cs

 

 


버블 정렬

정의

 

문제 : 학생 100명의 영어 성정을 오름차순으로 버블 정렬(Bubble Sort)하는 알고리즘을 제시하라.

 

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
public class BubbleSort {
 
    public static void main(String[] args) {
        int e[] = { 95758510050 };
        int i = 0// 배열 e 인덱스 변수.
        int temp; // 임시 변수.
 
        // n회전 반복문.
        do {
            // 비교용 인덱스 변수.
            // 한 회전이 끝날 때마다 0으로 초기화.
            int j = 0;
 
            // 버블정렬 반복문.
            do {
                // 이전값이 다음값보다 클 경우 e[j] <=> e[j+1]
                if (e[j] > e[j + 1]) {
                    temp = e[j];
                    e[j] = e[j + 1];
                    e[j + 1= temp;
                }
                j = j + 1// 다음 비교를 위해 비교용 인덱스 1증가.
            } while (j < 4 - i); // i++마다 비교범위가 좁아짐.
            i = i + 1// 한 회전이 완료되면 n회전 반복문 시작값 증가.
        } while (i < 4); // 모든 회전이 완료될 때까지 진행.
 
        for (int a = 0; a < 5; a++)
            System.out.print(e[a] + " ");
        // 50 75 85 95 100
    }
}
cs

 

 

 


삽입 정렬

정의

 

문제 : 학생 100명의 영어 성적을 오름차순으로 삽입 정렬(Insertion Sort)하는 알고리즘을 제시하라.

 

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
public class InsertionSort {
 
    public static void main(String[] args) {
        int e[] = { 95758510050 };
        int i, j; // 회전 인덱스, 삽입정렬 인덱스.
        int key; // 비교할 핵심값.
 
        // n회전 반복문.
        for (i = 1; i < 5; i++) {
            key = e[i]; // 처음 두번째 값으로 시작.
 
            // 삽입정렬 반복문.
            for (j = i - 1; j >= 0; j--) {
                // key값이 이전값보다 크거나 같을 경우
                // 삽입정렬 반복문 종료.
                if (e[j] <= key)
                    break;
 
                // 이전값이 key값보다 클 경우
                // 이전값을 key값 자리로 이동.
                e[j + 1= e[j];
            }
 
            // 이전값이 key값보다 클 경우
            // 이전값자리로 key값 삽입.
            // 반대의 경우 현 상태 유지.
            e[j + 1= key;
        }
 
        for (i = 0; i < 5; i++)
            System.out.print(e[i] + " ");
        // 50 75 85 95 100
    }
}
cs

 


병합 정렬

정의

 

문제 : 오름차순으로 정렬된 배열 A(M)과 내림차순으로 정렬된 배열 B(N)을 병합 정렬(Merge Sort)하여 오름차순의 배열 C(M+N)을 생성하는 알고리즘을 제시하라(단, 배열 A(M)과 배열 B(N)에는 900000 이하의 정수가 저장되어 있으며, 모든 배열의 첨자는 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
public class 병합정렬 {
 
    public static void main(String[] args) {
        int a[] = { 25101720 };
        int b[] = { 11987 };
        int m = 5;
        int n = 4;
        int c[] = new int[9];
        int ia = 0, ib = n - 1, ic = 0;
        int done = 0;
        for (;;) {
            if (a[ia] < b[ib]) {
                c[ic] = a[ia];
                ia = ia + 1;
                ic = ic + 1;
                if (ia > m - 1) {
                    if (done == 0) {
                        a[m - 1= 999999;
                        ia = m - 1;
                        done = 1;
                    } else
                        break;
                }
            } else {
                c[ic] = b[ib];
                ib = ib - 1;
                ic = ic + 1;
                if (ib < 0) {
                    if (done == 0) {
                        b[0= 999999;
                        ib = 0;
                        done = 1;
                    } else
                        break;
                }
            }
        }
 
        for (int i = 0; i < m + n; i++)
            System.out.print(c[i] + " ");
        // 2 5 7 8 9 10 11 17 20
    }
}
cs

 


퀵 정렬

정의

 

문제 : 학생 100명의 영어 성적을 다음과 같이 오름차순으로 퀵 정렬(Quick Sort)하는 알고리즘을 제시하라.

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
public class 퀵정렬 {
    public static void qsort(int[] e, int l, int r) {
        int temp;
        if(l >= r) return;
        int p = e[l];
        int i = l + 1;
        int j = r;
        
        do {
            while(p > e[i] && i < r) i = i + 1;
            while(p < e[i] && j > l) j = j - 1;
            if(i >= j) break;
            temp = e[i];
            e[i] = e[j];
            e[j] = temp;
        } while(i <= j);
        
        temp = e[j];
        e[j] = e[l];
        e[l] = temp;
        
        qsort(e, l, j - 1);
        qsort(e, j + 1, r);
    }
    
    public static void main(String[] args) {
        int e[] = { 26141009522,
            1748205090 };
        // qsort() 전 배열 출력.
        for(int i = 0 ; i < 10 ; i++)
            System.out.print(e[i] + " ");
        
        System.out.println();
        qsort(e, 09);
        
        // qsort() 후 배열 출력.
        for(int i = 0 ; i < 10 ; i++)
            System.out.print(e[i] + " ");
        // 26 14 90 20 22 17 48 50 95 100
    }
}
cs