반응형
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
public class Main {
    public static void printArray(int[] a) {
        for(int i = 0; i < a.length; i++){
            System.out.println(a[i]);
        }
    }
    
    public static int divideArray(int[] a, int head, int tail) {
        int left, right, temp;
        left = head + 1;
        right = tail;
        
        while(true) {
            while(left < tail && a[head] > a[left]) {
                left++;
            }
            
            while(a[head] < a[right]) {
                right--;
            }
            
            if(left >= right) {
                break;
            }
            
            temp = a[left];
            a[left] = a[right];
            a[right] = temp;
            
            left++;
            right--;
            
        }
        temp = a[head];
        a[head] = a[right];
        a[right] = temp;
        
        return right;
        
    }
    
    public static void sortArray(int[] a, int start, int end) {
        int pivot;
        
        if(start < end) {
            pivot = divideArray(a, start, end);
            
            sortArray(a, start, pivot - 1);
            
            sortArray(a, pivot + 1, end);
        }
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        
        int[] a = new int[n];
        
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        //printArray(a);
        
        sortArray(a, 0, a.length - 1);
        
        printArray(a);
        
    }
}
cs

O(nlogn)의 속도가 평균적이고, 최악에는 O(n^2)의 시간복잡도가 나오기도 한다.

반응형
저작자표시 비영리 변경금지

'공부 > Algorithm 이론' 카테고리의 다른 글

LinkedList 예제 java  (0) 2023.01.19
LinkedList 예제  (0) 2023.01.11
정렬 기본 예제 소스 O(N^2)  (0) 2023.01.08
이진 탐색  (0) 2023.01.07
반응형
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
class StationList{
    public String name;
    public int next;
}
 
 
public class LinkedList {
    public static StationList[] list = new StationList[10];
    
    public static int head;
    
    public static void initStationList() {    
        
        for(int i = 0; i < list.length; i++) {
            list[i] = new StationList();
        }
        
        list[0].name = "부산";
        list[0].next = -1;
        list[1].name = "대전";
        list[1].next = 3;
        list[2].name = "서울";
        list[2].next = 4;
        list[3].name = "동대구";
        list[3].next = 0;
        list[4].name = "천안아산";
        list[4].next = 1;
        
        
        head = 2;
    }
    
    public static void printStationList() {
        int idx = head;
        while(idx != -1) {
            System.out.print("[" + list[idx].name + "] -> ");
            idx = list[idx].next;
        }
        System.out.println();    
    }
    
    public static void insertStationList(int insIdx, String insName, int prevIdx) {
        list[insIdx].name = insName;
        list[insIdx].next = list[prevIdx].next;
        list[prevIdx].next = insIdx;
    }
    
    public static void deleteStationList(int delIdx, int prevIdx) {
        list[prevIdx].next = list[delIdx].next;
    }
    
    public static void main(String[] args) {
        initStationList();
        printStationList();
        
        insertStationList(5, "광명", 2);
        printStationList();
        
        deleteStationList(5, 2);
        printStationList();
    }
}
cs

 

반응형
저작자표시 비영리 변경금지

'공부 > Algorithm 이론' 카테고리의 다른 글

퀵정렬 예제소스  (0) 2023.01.25
LinkedList 예제  (0) 2023.01.11
정렬 기본 예제 소스 O(N^2)  (0) 2023.01.08
이진 탐색  (0) 2023.01.07
반응형
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
class StationList{
    public String name;
    public int next;
    
}
 
public class Main {
    
    public static StationList[] list = new StationList[10];
    
    public static int head;
    
    public static void initStationList() {
        
        for(int i = 0; i < list.length; i++) {
            list[i] = new StationList();
        }
        list[0].name = "부산";
        list[0].next = -1;
        list[1].name = "대전";
        list[1].next = 3;
        list[2].name = "서울";
        list[2].next = 4;
        list[3].name = "동대구";
        list[3].next = 0;
        list[4].name = "천안아산";
        list[4].next = 1;
        
        head = 2;
    }
    
    public static void printStationList() {
        int idx = head;
        while(idx != -1) {
            System.out.print("[" + list[idx].name + "] -> ");
            idx = list[idx].next;
        }
        System.out.println();
    }
    
    public static void insertStationList(int insIdx, String insName, int prevIdx) {
        list[insIdx].name = insName;
        list[insIdx].next = list[prevIdx].next;
        list[prevIdx].next = insIdx;
    }
    public static void deleteStationList(int delIdx, int prevIdx) {
        list[prevIdx].next = list[delIdx].next;
    }
    
    public static void main(String[] args) {
        initStationList();
        printStationList();
    
        insertStationList(5, "광명", 2);
        printStationList();
    
        deleteStationList(5,2);
        printStationList();
    }
}
 
cs
반응형
저작자표시 비영리 변경금지

'공부 > Algorithm 이론' 카테고리의 다른 글

퀵정렬 예제소스  (0) 2023.01.25
LinkedList 예제 java  (0) 2023.01.19
정렬 기본 예제 소스 O(N^2)  (0) 2023.01.08
이진 탐색  (0) 2023.01.07
반응형

알고리즘 정렬기법 중 가장 기본적인 정렬 삽입, 버블, 선택 정렬을 정리했다

시간복잡도는 O(N^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
import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tmp;
        int j;
        
        int n = sc.nextInt();
        int[] a = new int[n];
        
        
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        
        for(int i = 1; i < n; i++) {
            tmp = a[i];
            for(j = i - 1; j >= 0 && a[j] > tmp; j--) {
                a[j+1] = a[j];
            }
            a[j+1] = tmp;
        }
        
        for(int array : a) {
            System.out.println(array);
        }
    }
}
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
import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tmp;
        int j;
        
        int n = sc.nextInt();
        int[] a = new int[n];
        
        
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        
        for(int i = 0; i < n-1; i++) {
            for(j = 0; j < n-i-1; j++) {
                if(a[j] > a[j+1]) {
                    tmp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = tmp;
                }
            }
        }
        
        for(int array : a) {
            System.out.println(array);
        }
        
    }
}
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
import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tmp = 0;
        int j;
        int index;
        
        
        int n = sc.nextInt();
        int[] a = new int[n];
        
        
        for(int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        
        
        for(int i = 0; i < n-1; i++) {
            index = i;
            for(j = i + 1; j < n; j++) {
                if(a[j] < a[i]) {
                    index = j;
                    tmp = a[i];
                    a[i] = a[index];
                    a[index] = tmp;
                }
            }
        }
        
        for(int array : a) {
            System.out.println(array);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

'공부 > Algorithm 이론' 카테고리의 다른 글

퀵정렬 예제소스  (0) 2023.01.25
LinkedList 예제 java  (0) 2023.01.19
LinkedList 예제  (0) 2023.01.11
이진 탐색  (0) 2023.01.07
반응형

순차적으로 정렬되어있을 때 검색하는 가장 기본적인 검색방식이다.

 

방법은 중간값을 원하는 검색 값과 비교해서 검색하는 방식인데, 작을 땐 범위 아래로 내려서 O(logN) 의 시간복잡도를

갖고있다. 모든 자료를 순차로 탐색하는 것보다 효율이 좋아 자주쓰일 듯 하다.

구현도 쉬운편이고, 효율도 어느정도는 나오기에 구현 방식을 잘 기억해둬야겠다.

간단한 그림 예제와 소스코드 예제를 통해 익혀두기.

그림 예제

이 방식의 핵심은 제일 낮은 인덱스, 제일 큰 인덱스, 중간값 이 세 값을 구하는게 중요한데 중간 값(A[Center])비교를 기준으로 설명하자면

Max : 검색 값이 낮을 때 - Center대입

          검색 값이 높을 때 - 그대로

Min : 검색 값이 낮을 때 - 그대로

         검색 값이 높을 때 - Center대입

Center : 항상 (Min + Max) / 2를 해주면 중간값을 정할 수 있다.

첫번째 구역 나누기
두번째 구역 나누기

 

세번째 구역 나누기
네번째 구역 나누기

마지막 A[0]의 값이 찾는 값과 같다면 "값을 찾았습니다!"

아니라면 "찾는 값이 없어요"가 출력된다.

 

 

소스코드 예제

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
import java.util.Scanner;
 
public class Main {
    
    public static void main(String[] args) {
        int[] a = {39, 41, 53, 55, 68, 72, 84, 88, 92, 97, 102};
        
        Scanner sc = new Scanner(System.in);
        
        int b = sc.nextInt();
        int center = 0;
        
        int max = a.length;
        int min = 0;
        
        center = a.length/2;
        
        while(true) {
            if(b == a[center]) {
                System.out.println("값을 찾았습니다!");
                break;
            }
            else if(center == 0) {
                System.out.println("찾는 값이 없어요");
                break;
            }
            else if(b < a[center]) {
                //min 안건드림
                max = center;
                center = (min + max) / 2;
                
                System.out.println("b가 작아 min : " + min + "| max : " + max + "| center : " + center);
            }
            else if(b > a[center]) {
                min = center;
                //max 안건드림
                center = (min + max) / 2;
                
                System.out.println("b가 커 min : " + min + "| max : " + max + "| center : " + center);
            }
        }
    }
}
 
cs

-------------

위에 있는 소스는 23.01.14 다른 문제를 풀다 알게된건데 틀린 예제입니다.

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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
    
    public static void main(String[] args) throws NumberFormatException, IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long[] a = new long[n];
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(a);
        
        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        
        int left;
        int right;
        int center;
        
        long key = 0;
        int isTrue = 0;
        
        for(int i = 0; i < m; i++) {
            key = Integer.parseInt(st.nextToken());
            left = 0;
            right = a.length - 1;
            center = right / 2;
            isTrue = 0;
            while(left <= right) {
                if(a[center] == key) {
                    System.out.println("1");
                    isTrue = 1;
                    break;
                }
                else if(a[center] > key) {
                    right = center - 1;
                    center = (left + right) / 2;
                }
                else if(a[center] <key) {
                    left = center + 1;
                    center = (left + right) / 2;
                }
                
            }
            if(isTrue == 0) {
                System.out.println("0");
            }
        }
    }
}
cs

일단 간단한 예제를 올리기 전에 고쳐놓기....

요건 제 기준 어려운 예제임당...

반응형
저작자표시 비영리 변경금지

'공부 > Algorithm 이론' 카테고리의 다른 글

퀵정렬 예제소스  (0) 2023.01.25
LinkedList 예제 java  (0) 2023.01.19
LinkedList 예제  (0) 2023.01.11
정렬 기본 예제 소스 O(N^2)  (0) 2023.01.08

+ Recent posts

티스토리툴바