728x90
반응형

소수(Prime Number) 

: 1과 자기 자신만으로 나누어 떨어지는 1보다 큰 양의 정수


Contents

첫번째, n 보다 작은 정수를 나누어 보며 소수 구하는 법

두번째, 1번 방법 마법의 코드 한줄을 통해 실행 시간 단축하는 법

세번째, n 보다 작은 소수를 나누어 보며 소수 구하는 법


첫번째, n 보다 작은 정수를 나누어 보며 소수 구하는 법

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
public class prime {
    public static void getPrime(int num){
        boolean flag;    //소수 판별을 위한 true/false
        int cnt = 0;     //소수의 총 개수를 확인하기 위한 변수
        for(int i=2; i<=num; i++){    //i는 2~num 사이에 정수
            flag = true;
            for(int j=2; j<i; j++){   //j는 i보다 작은 정수
                if(i%j ==0){         //i를 j로 나누었을 때, 나누어 떨어지면 소수가 아님
                    flag = false;
                }
            }
            if(flag == true){
                cnt++;
                System.out.println(i); //소수를 따로 배열에 저장하지 않고, 찾을 때 마다 출력
            }        
        }
        System.out.println("소수 개수 : " + cnt);
    }
    
    public static void main(String[] args){
        long start = System.currentTimeMillis();
        getPrime(30000);
        long end = System.currentTimeMillis();
        System.out.println("실행 시간 : " + (double)(end-start)/1000 + "(s)");
    }
}
cs


실행결과

2

3

5

7

...

29959

29983

29989

소수 개수 : 3245

실행 시간 : 2.214(s)


총 30,000개의 정수 중, 소수의 총 개수는 3,245개, 실행 시간은 2.214초




두번째, 1번 방법 마법의 코드 한줄을 통해 실행 시간 단축하는 법

첫번째 코드의 public static void getPrime(int num){ ~ } 함수 안에 for문을 유심히 보자.

for(int i=2; i<=num; i++){ 

   flag = true;
   for(int j=2; j<i; j++){ 
      if(i%j ==0){        
          flag = false;
      }
   }
   if(flag == true){
      cnt++;
      System.out.println(i); 
   }        
}

i=9일 경우,

for(int j=2; j<i; j++){ 

   if(i%j ==0){        
       flag = false;
   }
}

j=3일 때, 이미 flag 값은 false가 된다. 9는 3의 배수 중 하나이기 때문에 소수가 아니다.


하지만 첫번째 방법의 소수 판별문의 경우, 

이미 flag값이 false가 되어 소수가 아닌 숫자를 찾아내도, 지속적으로 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
public class prime {
    public static void getPrime(int num){
        boolean flag;
        int cnt = 0;    
        for(int i=2; i<=num; i++){
            flag = true;
            for(int j=2; j<i; j++){    
                if(i%j ==0){        
                    flag = false;
                    break; //마법의 코드
                }
            }
            if(flag == true){
                cnt++;
                System.out.println(i);
            }        
        }
        System.out.println("소수 개수 : " + cnt);
    }

    public static void main(String[] args){
        long start = System.currentTimeMillis();
        getPrime(30000);
        long end = System.currentTimeMillis();
        System.out.println("실행 시간 : " + (double)(end-start)/1000 + "(s)");
    }
}
cs

10번 줄의 break문을 추가하여, i가 한 번이라도 j값을 통해 나누어 떨어지면, 

i는 이미 소수의 조건을 박탈, break문을 통해 해당 for문에서 빠져나와 새로운 값의 비교 연산을 진행한다.


실행결과

2

3

5

7

...

29959

29983

29989

소수 개수 : 3245

실행 시간 : 0.254(s)


총 30,000개의 정수 중, 소수의 총 개수는 3,245개, 실행 시간은 0.245초

break; 코드 한 줄을 통해 실행시간이 10배 가까이 단축 된 것을 볼 수 있다.




세번째, n 보다 작은 소수를 나누어 보며 소수 구하는 법

위의 2가지 방법은 

입력 받은 수보다 작은 수들을 나누어보며 떨어지는지 아닌지 판별을 하고 있다.


잘 생각해보면, 우리는 더 좋은 방법을 찾을 수 있다.


4는 2의 배수다. 2는 소수다.

10은 2의 배수, 5의 배수다. 2와 5는 소수다.

21는 3의 배수, 7의 배수다. 3과 7은 소수다.


입력 받은 수 보다 작은 정수들을 다 나누어 볼 필요없이,

입력받은 수보다 작은 수의 소수들만 나누어보면 되는 것이다.

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
import java.util.ArrayList;
 
public class prime {
    public static void getPrime(ArrayList<Integer> prime , int num){
        int cnt = 0;
        prime.add(2);
        for(int i=2; i <= num; i++){
            for(int j=0; j<prime.size(); j++){
                if(i%prime.get(j)==0){
                    break;
                }
                if(j+1 == prime.size()){
                    prime.add(i);
                }
            }
        }
        for(int i = 0; i<prime.size(); i++){
            cnt++;
            System.out.println(prime.get(i));
        }
        System.out.println("소수 개수 : " + cnt);
    }
    public static void main(String[] args){
        long start = System.currentTimeMillis();
        ArrayList<Integer> prime = new ArrayList<Integer>(); 
        getPrime(prime, 30000);
        long end = System.currentTimeMillis();
        System.out.println("실행 시간 : " + (double)(end-start)/1000 + "(s)");
    }
}
cs


실행결과

2

3

5

7

...

29959

29983

29989

소수 개수 : 3245

실행 시간 : 0.072(s)


총 30,000개의 정수 중, 소수의 총 개수는 3,245개, 실행 시간은 0.072초

첫번째 코드 보다는 30배 가까이,

두번째 코드 보다는 3배 가까이 실행 시간이 단축 된 것을 볼 수 있다.




3가지 방법 정수의 개수에 따른 실행 속도 비교

1000개 까지의 정수 중 소수를 판별하기 위한 실행속도는 방법별로 큰 차이는 보이지 않는다.

하지만 숫자가 커지면서 방법 별 실행속도의 차이는 눈에 띄게 차이가 나는 것을 볼 수 있다.



출처: http://hahahoho5915.tistory.com/14?category=653539 [넌 잘하고 있어]

728x90
반응형
저작자표시 비영리 변경금지 (새창열림)

'Web Programming > java-jsp' 카테고리의 다른 글

신입 자바 개발자 면접 질문  (0) 2018.08.29
Codility 자바 코딩실력 검증  (0) 2018.08.29
java 선형 큐(Linear Queue)  (0) 2018.08.29
java 퀵 정렬(Quick Sort)  (0) 2018.08.29
java 삽입 정렬(Insertion Sort)  (0) 2018.08.29
728x90
반응형

- FIFO - First In First Out(선입선출)

- 인큐(EnQueue)를 통해 자료 입력, 디큐(DeQueue)을 통해 자료 출력


* 매표소, 가장 먼저 줄서있는 사람에게 표를 먼저 제공한다.



* 선형 큐 알고리즘은 Rear가 배열의 끝에 닿아 있으면, 앞에 배열의 빈 부분(Q[0])이 남아 있어도 더이상 삽입연산을 하지 못한다.

메모리를 효율적으로 관리하지 못함. 이러한 문제점을 해결하기 위해 원형 큐가 만들어졌다.


JAVA 소스코드

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
import java.io.InputStream;
import java.util.Scanner;
 
public class Queue {
    
    private int front;
    private int rear;
    private int maxSize;
    private Object[] queueArray;
    
    //Queue 생성
    public Queue(int maxSize){
        this.front = 0;
        this.rear = -1;
        this.maxSize = maxSize;
        this.queueArray = new Object[maxSize];
    }
    
    //Queue 비었는지 확인
    public boolean empty(){
        return (front == rear+1);
    }
    
    //Queue 꽉 찼는지 확인
    public boolean full(){
        return (rear == maxSize-1);
    }
    
    //Queue에 item 입력
    public boolean enqueue(Object item){
        if(full()){
            System.out.println("Queue is FULL!!");
            return false;
        }
        queueArray[++rear] = item;
        return true;
    }
 
    //Queue 가장 먼저들어온 데이터 출력
    public Object dequeue(){
        if(empty()){
            System.out.println("Queue is EMPTY!!");
            return null;
        }else{
            Object item = queueArray[front];
            queueArray[front] = null;
            front++;
            return item;
        }
    }
    
    //Queue 출력
    public void printQueue(Queue queue){
        if(!empty()){
            for(int i = 0; i<maxSize; i++ ){
                if(queue.queueArray[i] == null){
                    System.out.print("|\t\t");
                }else{
                    System.out.print("|\t"+ queue.queueArray[i]+ "\t");
                }
            }
            System.out.println(" |");
        }else{
            System.out.println("큐 비어있음");
        }    
    }
    
    public static void main(String[] args) {
 
        InputStream a = System.in;
        Scanner sc = new Scanner(a);
        
        System.out.println("큐 SIZE 입력 : ");
        int size = sc.nextInt();
        Queue arrayQueue = new Queue(size); //create queue
        
        boolean flag = true;
        
        while(flag){
            menu();
            String s = sc.next();
            switch(s){
            case "1":
                System.out.print("ENQUEUE : ");
                String data = sc.next();
                arrayQueue.enqueue(data);
                break;
            case "2":
                System.out.println("DEQUEUE : " + arrayQueue.dequeue());
                break;
            case "3":
                arrayQueue.printQueue(arrayQueue);
                break;
            case "q":
            case "Q":
                flag = false;
                break;
            }
        }
    }
    public static void menu(){
        System.out.println("1. enQueue");
        System.out.println("2. deQueue");
        System.out.println("3. QUEUE");
        System.out.println("Q. 종료");
    }
}
cs



출처: http://hahahoho5915.tistory.com/11?category=653539 [넌 잘하고 있어]

728x90
반응형
저작자표시 비영리 변경금지 (새창열림)

'Web Programming > java-jsp' 카테고리의 다른 글

Codility 자바 코딩실력 검증  (0) 2018.08.29
java 소수 구하기 + 실행시간 단축  (0) 2018.08.29
java 퀵 정렬(Quick Sort)  (0) 2018.08.29
java 삽입 정렬(Insertion Sort)  (0) 2018.08.29
java 버블 정렬(Bubble Sort)  (0) 2018.08.29
728x90
반응형

- 리스트 가운데서 하나의 원소를 고름(pivot 선정)

- pivot 앞에는 pivot보다 작은 값이 오고, pivot 뒤에는 pivot보다 큰 값들이 오도록 리스트를 둘로 분할한다.

- 분할된 두 개의 리스트에 대해 재귀함수를 통해 이 과정을 반복한다.

- 시간복잡도 : 최악 O(n^2), 평균 O(nlogn)




JAVA 소스코드
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 Quick {
    
    public void sort(int[] data, int l, int r){
        int left = l;
        int right = r;
        int pivot = data[(l+r)/2];
        
        do{
            while(data[left] < pivot) left++;
            while(data[right] > pivot) right--;
            if(left <= right){    
                int temp = data[left];
                data[left] = data[right];
                data[right] = temp;
                left++;
                right--;
            }
        }while (left <= right);
        
        if(l < right) sort(data, l, right);
        if(r > left) sort(data, left, r);
    }
    
    public static void main(String[] args) {
        
        int data[] = {66, 10, 1, 34, 5, -10};
        
        Quick quick = new Quick();
        quick.sort(data, 0, data.length - 1);
        for(int i=0; i<data.length; i++){
            System.out.println("data["+i+"] : "+data[i]);
        }
    }
}
cs



출처: http://hahahoho5915.tistory.com/9?category=653519 [넌 잘하고 있어]

728x90
반응형
저작자표시 비영리 변경금지 (새창열림)

'Web Programming > java-jsp' 카테고리의 다른 글

java 소수 구하기 + 실행시간 단축  (0) 2018.08.29
java 선형 큐(Linear Queue)  (0) 2018.08.29
java 삽입 정렬(Insertion Sort)  (0) 2018.08.29
java 버블 정렬(Bubble Sort)  (0) 2018.08.29
java 선택 정렬(Selection Sort)  (0) 2018.08.29
728x90
반응형

배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함.

- 배열의 두 번째 데이터 부터 연산을 시작함.

- 시간복잡도 : O(n^2)



[1회전]


[2회전]


[3회전]


[4회전]


JAVA 소스코드

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
public class Insertion {
 
    public void sort(int[] A){
        int size = A.length;
        int temp = 0;
        int j = 0;
        for(int i = 1; i < size; i++){
            temp = A[i];
            for(j=i-1; j>=0 && temp<A[j]; j--){
                A[j+1] = A[j];
            }
            A[j+1] = temp;
        }
    }
    
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Insertion insertion = new Insertion();
        
        int A[] = {66, 10, 1, 34, 5};
        
        insertion.sort(A);
        for(int i = 0; i < A.length; i++){
            System.out.println("A["+i+"] : " + A[i]);
        }
    }
}
cs




출처: http://hahahoho5915.tistory.com/8?category=653519 [넌 잘하고 있어]

728x90
반응형
저작자표시 비영리 변경금지 (새창열림)

'Web Programming > java-jsp' 카테고리의 다른 글

java 선형 큐(Linear Queue)  (0) 2018.08.29
java 퀵 정렬(Quick Sort)  (0) 2018.08.29
java 버블 정렬(Bubble Sort)  (0) 2018.08.29
java 선택 정렬(Selection Sort)  (0) 2018.08.29
java 면접 예상 질문  (0) 2018.08.29
728x90
반응형

두 인접한 원소를 검사하여 정렬하는 방법

- 시간복잡도 : O(n^2)

- 세번의 회전에 걸쳐 정렬은 완료되었지만 프로그램은 남은 데이터의 비교연산을 계속 처리함.

- 정렬은 비교연산을 통해 가장 큰 데이터 부터 끝에 정렬됨.


버블 정렬의 장점

- 구현이 쉽다.

- 이미 정렬된 데이터를 정렬할때 가장 빠르다.


버블 정렬의 단점

- 다른 정렬에 비해 정렬 속도가 느리다.

- 역순배열을 정렬할때 가장 느리다.


JAVA 소스코드

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
public class Bubble {
    public void sort(int [] data){
        int temp = 0;
        for(int i=data.length-1; i>=0; i--){
            for(int j=0; j<i; j++){
                if(data[j] > data[j+1]){
                    temp = data[j];
                    data[j] = data[j+1];
                    data[j+1] = temp;
                }                
            }
        }
    }
    public static void main(String[] args) {
 
        Bubble bubble = new Bubble();
        
        int data[] = {66, 10, 1, 34, 5};
        
        bubble.sort(data);
        
        for(int i=0; i<data.length; i++){
            System.out.println("data["+i+"] : " + data[i]);
        }
    }
}
cs



출처: http://hahahoho5915.tistory.com/6?category=653519 [넌 잘하고 있어]

728x90
반응형
저작자표시 비영리 변경금지 (새창열림)

'Web Programming > java-jsp' 카테고리의 다른 글

java 퀵 정렬(Quick Sort)  (0) 2018.08.29
java 삽입 정렬(Insertion Sort)  (0) 2018.08.29
java 선택 정렬(Selection Sort)  (0) 2018.08.29
java 면접 예상 질문  (0) 2018.08.29
java 동기화, synchronized, wait()-notify() 메서드  (0) 2018.08.29

+ Recent posts

티스토리툴바