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

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


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


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


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

데이터를 꺼내는 쪽을 프런트(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


스택


스택은 데이터를 일시적으로 저장하기 위한 자료구조, 가장 나중에 넣은 데이터를 가장 먼저 꺼낸다.(LIFO last in first out)

스택에 데이터를 넣는 작업을 푸시라 하고 스택에서 데이터를 꺼내는 작업을 팝이라고 한다.

데이터를 스택에 푸시하고 팝하는 과정을 나타냄



1. 스택 알고리즘 구현


push() 데이터 넣는 메서드

pop() 데이터 빼는 메서드

peek() 맨 꼭대기 요소 보는 메서드

dump() 모든 요소 보는 메서드



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
package myTest1;
 
import java.util.Scanner;
 
public class IntStack {
    
    private int max;        // 스택 용량        
    private int ptr;        // 스택 포인터
    private int[] stk;        // 스택 본체
    
    // 실행 시 예외 : 스택이 비어있음
    public class EmptyIntStackException extends RuntimeException{
        public EmptyIntStackException(){
        }
    }
    
    // 실행 시 예외 : 스택이 가득 참
    public class OverflowIntStackException extends RuntimeException{
        public OverflowIntStackException(){
        }
    }
    
    // 생성자
    public IntStack(int capacity){
        ptr = 0;
        max = capacity;
        try{
            stk = new int[max];            // 스택 본체용 배열을 생성
        }catch(OutOfMemoryError e){    // 생성할 수 없음
            max = 0;
        }
    }
 
    // 스택에 데이터를 푸시하는 메서드
    public int push(int x) throws OverflowIntStackException{
        if(ptr >= max){    // 스택이 가득 참
            throw new OverflowIntStackException();
        }
        return stk[ptr++] = x;
    }
    
    // 스택의 꼭대기에 있는 데이터를 제거(팝) 하고 그 값을 반환하는 메서드
    public int pop() throws EmptyIntStackException{
        if(ptr <= 0){
            throw new EmptyIntStackException();
        }
        return stk[--ptr];
    }
    
    // 스택의 꼭대기에 있는 데이터를 몰래 엿보는 메서드(peek 메서드 )
    public int peek() throws EmptyIntStackException{
        if(ptr <= 0){
            throw new EmptyIntStackException();
        }
        return stk[ptr - 1];
    }
    
    // 스택에서 x를 찾아 인덱스를 반환
    public int indexOf(int x){
        for(int i=ptr -1; i>=0; i--){
            if(stk[i] == x){
                return i;
            }
        }
        return -1;
    }
    
    // 스택을 비움
    public void clear(){
        ptr = 0;
    }
    
    // 스택의 용량을 반환
    public int capacity(){
        return max;
    }
    
    // 스택에 쌓여있는 데이터 수를 반환
    public int size(){
        return ptr;
    }
    
    // 스택이 비어있는가?
    public boolean isEmpty(){
        return ptr <= 0;
    }
    
    // 스택이 가득찼는가?
    public boolean isFull(){
        return ptr >= max;
    }
    
    // 스택 안의 모든 데이터를 바닥 -> 꼭대기 순서로 출력
    public void dump(){
        if(ptr <= 0){
            System.out.println("스택이 비어있습니다.");
        }else{
            for(int i=0; i<ptr; i++){
                System.out.print(stk[i] + " ");
            }
            System.out.println();
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        IntStack stack = new IntStack(64);    // 최대 64개를 푸시할 수 있는 스택
        
        while(true){
            System.out.println("현재 데이터 수 : " + stack.size() + " / " + stack.capacity()); 
            System.out.print("(1) 푸시 (2) 팝 (3) 피크 (4) 덤프 (5) 종료 : ");
            int menu = scanner.nextInt();
            if(menu == 0) break;
            
            int x;
            switch(menu){
            
            case 1:
                System.out.print("데이터 : ");
                x = scanner.nextInt();
                try{
                    stack.push(x);
                }catch(IntStack.OverflowIntStackException e){
                    System.out.println("스택이 가득찼습니다.");
                }
                break;
                
            case 2:
                try{
                    x = stack.pop();
                    System.out.println("팝한 데이터는 " + x + "입니다.");
                }catch(IntStack.EmptyIntStackException e){
                    System.out.println("스택이 비어있습니다.");
                }
                break;
 
            case 3:
                try{
                    x = stack.peek();
                    System.out.println("피크한 데이터는 " + x + "입니다.");
                }catch(IntStack.EmptyIntStackException e){
                    System.out.println("스택이 비어있습니다.");
                }
                break;
 
            case 4:
                stack.dump();
                break;
            }
        }
    }
}
cs


결과




소스코드 첨부


myTest1.zip



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

재귀를 사용한 팩토리얼, 최대공약수, 하노이탑 구현  (0) 2018.10.07
배열을 사용한 큐, 링버퍼 큐, 링버퍼 활용 구현  (0) 2018.10.07
이진검색 알고리즘 (구현 메소드 사용, Arrays.binarySearch 라이브러리 사용)  (0) 2018.10.03
선형 검색 while, for, 보초법 사용하여 구현하기 (검색 알고리즘)  (0) 2018.09.30
다차원 배열 사용, 2차원 배열 사용하여 윤년, 평년 일수 구하기  (0) 2018.09.30


이진검색법


이진검색 알고리즘을 적용하는 전제조건은 데이터가 키 값으로 이미 정렬 되어 있다는 것이다.

이진검색은 요소가 오름차순 또는 내림차순으로 정렬된 배열에서 검색하는 알고리즘이다.



1. 이진검색 알고리즘 ( 메소드 구현 방법, Arrays.binarySearch 표준라이브러리 사용방법 ) 



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 myTest1;
 
import java.util.Arrays;
import java.util.Scanner;
 
public class BinarySearch {
 
    // 이진 검색
    static int binarySearch(int[] array, int arrayLength, int searchValue){
        int first = 0;                            // 검색 범위의 첫 인덱스
        int last = arrayLength-1;        // 검색 범위의 끝 인덱스
        
        do{
            int center = (first +  last) /2 ; // 중앙 요소의 인덱스
            if(array[center] == searchValue) 
                return center;    // 검색 성공
            else if(array[center] < searchValue) 
                first = center+1;    // 검색 범위를 뒤쪽 절반으로 좁힘
            else 
                 last = center -1;    // 검색 범위를 앞쪽 절반으로 좁힘
        }while(first <=  last);
        return -1;        // 검색 실패
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("배열 길이 : ");
        int arrayLength = scanner.nextInt();
        int[] array = new int[arrayLength];    // 요솟수가 num인 배열
        System.out.println("오름차순으로 입력");
        
        System.out.print("array[0] : ");
        array[0] = scanner.nextInt();
        
        for(int i=1; i<arrayLength; i++){
            do{
                System.out.print("array[" + i + "] : ");
                array[i] = scanner.nextInt();
            }while(array[i] < array[i-1]);        // 바로 앞의 요소보다 작으면 다시 입력
        }
        
        System.out.println("검색할 값");    // 키 값을 입력
        int searchValue = scanner.nextInt();
        // 구현한 binarySearch 메소드 사용
        int idx = binarySearch(array, arrayLength, searchValue);        
        // Arrays.binarySearch 이진검색 표준라이브러리 사용
        int idx2 = Arrays.binarySearch(array, searchValue);
        
        if(idx == -1){
            System.out.println("구현한 이진검색 메소드 결과 그 값의 요소가 없습니다.");
        }else{
            System.out.println("구현한 이진검색 메소드 결과 "+searchValue+"은(는) array["+idx+"]에 있습니다.");
        }
        
        if(idx2 == -1){
            System.out.println("구현한 이진검색 메소드 결과 그 값의 요소가 없습니다.");
        }else{
            System.out.println("Arrays.binarySearch 표준 라이브러리 사용결과 "+searchValue+"은(는) array["+idx2+"]에 있습니다.");
        }
        
        
    }
}
cs


결과




2.  Arrays.binarySearch 표준라이브러리 사용해 String 검색하기



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
package myTest1;
 
import java.util.Arrays;
import java.util.Scanner;
 
public class StringBinarySearch {
 
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String[] x = {
            "apple", "banana", "cocoa", "duck", "element", "final",
            "grape", "honey", "ice", "jerry", "king", "leaf", "monkey"
        };
        System.out.println("키워드를 입력: ");
        String searchKey = scanner.next();
        
        int idx = Arrays.binarySearch(x, searchKey);    // 배열 x에서 값이 searchKey 요소 검색
        
        if( idx < 0){
            System.out.println("해당 키워드가 없습니다.");
        }else{
            System.out.println("해당 키워드는 x[" + idx + "]에 있습니다.");
        }
    }
}
cs



결과




3. 제네릭과 생성자를 사용하여  Arrays.binarySearch(T[] a, T key, Comparator<? super T>c) 표준라이브러리 메소드 사용하기


 The array must be sorted into ascending orderaccording to the specified comparator

이진검색 알고리즘을 사용할 경우 정렬되어야 한다.



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
package myTest1;
 
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
 
public class ConstructorBinarySearchLibrary {
    // 신체검사 데이터 정의
    static class PhyscData{
        private String name;    // 이름
        private int height;        // 키
        private double vision;    // 시력
        
        // 생성자
        public PhyscData(String name, int height, double vision){
            this.name = name; 
            this.height = height; 
            this.vision = vision;
        }
        
        // 문자열을 반환하는 메서드
        public String toString(){
            return name + " " + height + " " + vision;
        }
        
        public static final Comparator<PhyscData> HEIGHT_ORDER = new HeightOrderComparator();
        public static final Comparator<PhyscData> VISION_ORDER = new VisionOrderComparator();
        
        private static class HeightOrderComparator implements Comparator<PhyscData>{
            public int compare(PhyscData d1, PhyscData d2){
                return (d1.height > d2.height) ? 1:
                            (d1.height < d2.height) ? -1 : 0;
            }
        }
 
        private static class VisionOrderComparator implements Comparator<PhyscData>{
            public int compare(PhyscData d1, PhyscData d2){
                return (d1.vision < d2.vision) ? 1:
                    (d1.vision > d2.vision) ? -1 : 0;
            }
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        
        // 키 오름차순, 시력 내림차순 정렬
        PhyscData[] arrays = {
                new PhyscData("윤아", 160, 1.5),
                new PhyscData("태연", 161, 1.4),
                new PhyscData("티파니", 162, 1.3),
                new PhyscData("제시카", 163, 1.2),
                new PhyscData("유리", 164, 1.1),
                new PhyscData("서현", 165, 1.0),
                new PhyscData("써니", 166, 0.9),
        };
        
        System.out.print("몇 cm인 사람을 찾고 있나요? : ");
        int height = scanner.nextInt();
        int idx = Arrays.binarySearch(arrays, new PhyscData("", height, 0.0), PhyscData.HEIGHT_ORDER);
        if(idx < 0){
            System.out.println("요소가 없습니다.");
        }else{
            System.out.println("arrays[" + idx + "]에 있습니다.");
            System.out.println("찾은 데이터 : " + arrays[idx]);
        }
        
        System.out.println("시력이 몇인 사람을 찾나요?");
        double visionValue = scanner.nextDouble();
        int idx2 = Arrays.binarySearch(arrays, new PhyscData("", 0, visionValue), PhyscData.VISION_ORDER);
        if(idx2 < 0){
            System.out.println("요소가 없습니다.");
        }else{
            System.out.println("arrays[" + idx2 + "]에 있습니다.");
            System.out.println("찾은 데이터 : " + arrays[idx2]);
        }
    }
}
cs


결과




소스코드 첨부


myTest1.zip




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

배열을 사용한 큐, 링버퍼 큐, 링버퍼 활용 구현  (0) 2018.10.07
스택 알고리즘 구현  (0) 2018.10.03
선형 검색 while, for, 보초법 사용하여 구현하기 (검색 알고리즘)  (0) 2018.09.30
다차원 배열 사용, 2차원 배열 사용하여 윤년, 평년 일수 구하기  (0) 2018.09.30
배열사용, 제곱근 이하 소수 판단, 소수 찾기 알고리즘  (0) 2018.09.30


선형검색은 배열에서 검색하는 방법 중 가장 기본적인 알고리즘이다.


요소가 직선모양으로 늘어선 배열에서 

검색은 원하는 키 값을 갖는 요소를 만날때까지 맨앞부터 순서대로 요소를 검색한다.

이 검색을 선형검색(linear search) 또는 순차검색(sequential search) 이라고 한다.


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
74
75
package myTest1;
 
import java.util.Scanner;
 
public class SeqSearch {
 
    static int seqSearch(int[] array, int arrayLength, int key){
        int i=0;
        while(true){
            if(i==arrayLength) return-1;        // 검색 실패 -1을 반환
            if(array[i] == key) return i;        // 검색 성공(인덱스를 반환)
            i++;
        }
    }
 
    static int usingForSeqSearch(int[] array, int arrayLength, int key){
        for(int i=0; i<arrayLength; i++){
            if(array[i] == key){
                return i;
            }
        }
        return -1;
    }
 
    // 보초법
    static int seqSearchSen(int[] array, int arrayLength, int key){
        int i = 0;
        // arrayLength = 3, key = 2
        // array[0] = 1, array[1] = 2, array[2] = 3
        // array[3] = 2
        array[arrayLength] = key;    // 보초를 추가
        while(true){
            if(array[i] == key) break;
            i++;
        }
        // array[3] 에 있다면 못찾은 것 -1 return
        return i == arrayLength? -1 : i ;
    }    
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.print("배열길이: ");
        int arrayLength = scanner.nextInt();
        int[] array = new int[arrayLength+1];
        
        
        for(int i=0; i<arrayLength; i++){
            System.out.print("x[" + i + "] : ");
            array[i] = scanner.nextInt();
        }
        System.out.print("검색할 값: ");
        int key = scanner.nextInt();
        int idx1 = seqSearch(array, arrayLength, key);        // 배열 array에서 키 값이 key인 요소를 검색
        int idx2 = usingForSeqSearch(array, arrayLength, key);
        int idx3 = seqSearchSen(array, arrayLength, key);
        
        if(idx1 == -1){
            System.out.println("그 값의 요소가 없습니다.");
        }else{
            System.out.println(key+"은(는) x[" + idx1 + "]에 있습니다.");
        }
        
        if(idx2 == -1){
            System.out.println("그 값의 요소가 없습니다.");
        }else{
            System.out.println(key+"은(는) x[" + idx2 + "]에 있습니다.");
        }
 
        if(idx3 == -1){
            System.out.println("그 값의 요소가 없습니다.");
        }else{
            System.out.println(key+"은(는) x[" + idx3 + "]에 있습니다.");
        }
    }
}
cs


결과



while문, for문, 보초법을 사용해 해당 배열에서의 키값을 찾아낸다.

보초법은 기존 배열의 길이를 +1 증가시켜

배열의 맨 마지막 길이의 요소에 찾을 키 값을 넣고

찾는 키값이 마지막에 찾게 될 경우 -1을 리턴한다.


소스코드 첨부


myTest1.zip



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

스택 알고리즘 구현  (0) 2018.10.03
이진검색 알고리즘 (구현 메소드 사용, Arrays.binarySearch 라이브러리 사용)  (0) 2018.10.03
다차원 배열 사용, 2차원 배열 사용하여 윤년, 평년 일수 구하기  (0) 2018.09.30
배열사용, 제곱근 이하 소수 판단, 소수 찾기 알고리즘  (0) 2018.09.30
기수 변환, 정수를 입력받아 2진수 ~36진수 변환  (0) 2018.09.30


1. 2차원 배열 사용하기



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
package myTest1;
 
public class Int2DArray {
 
    public static void main(String[] args) {
        int[][] x = new int[2][4];    // 2차원배열 선언
        
        x[0][1] = 37;                
        x[0][3] = 54;
        x[1][2] = 65;
        
        for(int i=0; i<2; i++){
            for(int j=0; j<4; j++){
                System.out.println("x[" + i + "][" + j + "] = " + x[i][j]);
            }
        }
 
    }
}
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
package myTest1;
 
import java.util.Scanner;
 
public class DayOfYear {
 
    // mdays[0][0] = 31, mdays[0][1] = 28, mdays[0][2] = 30
    // mdays[1][0] = 31, mdays[1][1] = 29, mdays[1][2] = 30
    static int[][] mdays = {
            {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}    // 평년
          ,    {31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31} // 윤년
    };
    
    // 해당 year는 윤년인가? (윤년 1 평년 0 )
    static int isLeap(int year){
        // 2018 % 4 false 2018 % 400 false 0
        return (year % 4 == 0 && year % 100 != 0 || year % 400 == 0) ? 1: 0;
    }
    
    static int dayOfYear(int y, int m, int d){
        // 2018, 3, 15
        // days = 15;
        // int i=1 ; i<3; i++ 1,2
        int days = d;
        for(int i=1; i<m; i++){
            // mdays[isLeap(2018)][0], mdays[0][0]
            // mdays[isLeap(2018)][1], mdays[0][1]
            // 15+31+28 = 74
            days += mdays[isLeap(y)][i-1];
        }
        return days;
    }
 
    static int usingWhileDayOfYear(int y, int m, int d){
        int days = 0;
        m -= 2;
        do{
            days += mdays[isLeap(y)][m];
            m--;
        }while(m>-1);
        days += d;
        return days;
    }
    
    public static void main(String[] args) {
        Scanner stdIn = new Scanner(System.in);
        int retry;
        System.out.println("그 해 경과 일수를 구합니다.");
        do{
            System.out.print("년 : "); int year = stdIn.nextInt();    // 년
            System.out.print("월 : "); int month = stdIn.nextInt();    // 년
            System.out.print("일 : "); int day = stdIn.nextInt();    // 년
            System.out.printf("그 해 %d일째입니다.\n", dayOfYear(year,month, day));
            System.out.printf("그 해 %d일째입니다.\n", usingWhileDayOfYear(year,month, day));
            System.out.print("한번 더 할까요? (1.예 / 0. 아니오) : ");
            retry = stdIn.nextInt();
        }while(retry == 1);
    }
}
cs


결과



for문과 do while문을 사용하여 메소드를 다르게 구현하였다.


소스 코드 첨부


myTest1.zip




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

이진검색 알고리즘 (구현 메소드 사용, Arrays.binarySearch 라이브러리 사용)  (0) 2018.10.03
선형 검색 while, for, 보초법 사용하여 구현하기 (검색 알고리즘)  (0) 2018.09.30
배열사용, 제곱근 이하 소수 판단, 소수 찾기 알고리즘  (0) 2018.09.30
기수 변환, 정수를 입력받아 2진수 ~36진수 변환  (0) 2018.09.30
배열 요소 랜덤 생성, 배열 a,b 복사하기, 같은지 확인하기, 역순으로 복사하기  (0) 2018.09.29


1. 알고리즘 개선 없는 1000 이하의 소수 찾기



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
package myTest1;
 
public class PrimeNumber1 {
 
    public static void main(String[] args) {
        int counter = 0;
        // 1000 이하의 소수를 열거함.
        for(int n=2; n<=1000; n++){
            int i;
            for(i=2; i<n; i++){
                counter++;
                if(n%i==0) break;
            }
            if(n==i){
                System.out.println(n);
            }
        }
        System.out.println("나눗셈을 수행한 횟수: " + counter);
    }
    
}
cs


결과




2. 배열을 사용해 3이상의 소수를 이중 for문으로 2씩 증가시켜 1000 이하의 소수 찾기



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 myTest1;
 
public class PrimeNumber2 {
 
    public static void main(String[] args) {
        int counter = 0;    // 나눗셈의 횟수
        int ptr = 0;            // 찾은 소수의 개수
        int[] prime = new int[500];        // 소수를 저장하는 배열
        
        prime[ptr++] = 2;    // 2는 소수임
        // prime[0] = 2
        // prime[1] = null
        for(int n=3; n<=1000; n+=2){    // 대상은 홀수만 3,5,7,9,
            int i;
            // i=1; i<1 false
            // prime[1] = 3
            // n= 5 i=1 i<2 counter = 1; 5 % prime[1] 
            for(i=1; i<ptr; i++){
                counter++;
                if(n%prime[i] == 0) break;
            }
            if(ptr == i){                    // 나누어 떨어지지 않음
                prime[ptr++] = n;    // 소수로 배열로 저장
            }
        }
        
        for(int i=0; i<ptr; i++){    // 찾은 ptr개의 소수를 나타냄
            System.out.println(prime[i]);
        }
        System.out.println("나눗셈을 수행한 횟수: " + counter);
    }
}
cs


결과




3. 배열을 사용해 n의 제곱근 이하의 어떤 소수로도 나누어 떨어지지 않는다. 라는 소수 판단 조건을 가지고

1000 이하의 소수 찾기



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 myTest1;
 
public class PrimeNumber3 {
 
    public static void main(String[] args) {
        int counter = 0;                        // 곱셉과 나눗셈의 횟수
        int ptr = 0;                                // 찾은 소수의 개수
        int[] prime = new int[500];        // 소수를 저장하는 배열
        
        prime[ptr++] = 2;                    // 2는 소수임
        prime[ptr++] = 3;                    // 3은 소수임
 
        for(int n=5; n<=1000; n+=2){    // 홀수만
            boolean flag = false;
            for(int i=1; prime[i] * prime[i] <= n; i++){
                counter += 2;
                if(n % prime[i] == 0){        // 나누어 덜어지면 소수가 아님
                    flag = true;
                    break;
                }
            }
            if(!flag){                                // 나누어 떨어지지 않았다면
                prime[ptr++] = n;            // 소수로 배열에 저장
                counter++;
            }
        }
        for(int i=0; i<ptr; i++){
            System.out.println(prime[i]);
        }
        System.out.println("곱셈과 나눗셈을 수행한 횟수: " + counter);
    }
}
cs





3개의 실행결과

나눗셈을 수행한 횟수는 78022, 14622, 3774 번이다.

알고리즘 개선을 통해 수행한 횟수를 줄일수 있었다.


소스 코드 첨부


myTest1.zip



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

선형 검색 while, for, 보초법 사용하여 구현하기 (검색 알고리즘)  (0) 2018.09.30
다차원 배열 사용, 2차원 배열 사용하여 윤년, 평년 일수 구하기  (0) 2018.09.30
기수 변환, 정수를 입력받아 2진수 ~36진수 변환  (0) 2018.09.30
배열 요소 랜덤 생성, 배열 a,b 복사하기, 같은지 확인하기, 역순으로 복사하기  (0) 2018.09.29
탐욕 알고리즘  (0) 2018.09.01


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
package myTest1;
 
import java.util.Scanner;
 
public class CardinalConverse {
 
    // 정수값 x를 r진수로 변환하여 배열 d에 아랫자리부터 넣어두고 자릿수를 반환한다.
    static int cardConverse(int integerNo, int cardinalNo, char[] charArray){
        int digits = 0;
        String dchar = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        
        do{
            // cardConverse(10, 2, [])
            // 10 % 2 = 0 , charArray[0] = 0, 10/2 = 5
            // 5 % 2 = 1      , charArray[1] = 1, 5/2 = 2
            // 2 % 2 = 0      , charArray[2] = 0, 2/2  = 1
            // 1 % 2 = 1      , charArray[3] = 1, 1/2  = 0
            charArray[digits++] = dchar.charAt(integerNo % cardinalNo);
            integerNo /= cardinalNo;
        }while(integerNo != 0);
        // digits = 4
        return digits;    
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int integerNo;        // 변환하는 정수
        int cardinalNo;        // 기수
        int digitLength;    // 변환 후의 자릿수
        int retry;    // 재시도
        char[] charArray = new char[32];    // 변환 후 각 자리의 숫자를 넣어두는 문자의 배열
        
        System.out.println("10진수를 기수 변환합니다.");
        do{
            do{
                System.out.println("변환하는 음이 아닌 정수: ");
                integerNo = scanner.nextInt();
            }while(integerNo <0);
            
            do{
                System.out.println("어떤 진수로 변환할까요? (2~36) : ");
                cardinalNo = scanner.nextInt();         
            }while(cardinalNo < 2 || cardinalNo > 36);
            // 10, 2, []
            digitLength = cardConverse(integerNo, cardinalNo, charArray);
            System.out.println(cardinalNo + "진수로는 ");
            for(int i= digitLength-1; i >=0; i--){
                System.out.print(charArray[i]);
            }
            System.out.println("입니다.");
            System.out.print("한번 더 할까요? (1.예 / 0.아니오) : ");
            retry = scanner.nextInt();
        }while(retry == 1);
    }
}
cs


결과



소스코드 첨부


myTest1.zip




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

다차원 배열 사용, 2차원 배열 사용하여 윤년, 평년 일수 구하기  (0) 2018.09.30
배열사용, 제곱근 이하 소수 판단, 소수 찾기 알고리즘  (0) 2018.09.30
배열 요소 랜덤 생성, 배열 a,b 복사하기, 같은지 확인하기, 역순으로 복사하기  (0) 2018.09.29
탐욕 알고리즘  (0) 2018.09.01
다익스트라 알고리즘  (0) 2018.08.25


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
package myTest1;
 
import java.util.Random;
import java.util.Scanner;
 
public class RandomReverseArrayValue {
 
    // 배열의 요소값을 역순으로 바꾸기
    static void swap(int[] a, int idx1, int idx2){
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }
    
    public static void main(String[] args) {
        Random rand = new Random();
        Scanner scanner = new Scanner(System.in);
        System.out.println("배열의 길이: ");
        int num = scanner.nextInt();
        
        int[] x = new int[num];
        System.out.println("\n배열길이에 따른 랜덤으로 생성된 배열요소");
        for(int i=0; i<num; i++){
            x[i] = 100 + rand.nextInt(100);
            System.out.println("x[" + i + "] : " + x[i]);
        }
 
        for(int i=0; i< x.length/2; i++){
            int length = x.length-i-1;
            swap(x, i, length);
        }
        
        System.out.println("\n요소를 역순으로 정렬결과");
        for(int i=0; i<num; i++){
            System.out.println("x[" + i + "] = " + x[i]);
        }
        
    }
        
}
cs


결과 값





2. 배열 a,b 복사하기, 같은지 확인하기, 역순으로 복사하기



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
package myTest1;
 
import java.util.Scanner;
 
public class CompareEqualArray {
    
    // 두 배열의 요소값이 모두 같은지 확인하기
    static boolean equals(int[] a, int[] b){
        if(a.length != b.length){
            return false;
        }
        for(int i=0; i< a.length; i++){
            if(a[i] != b[i]){
                return false;
            }
        }
        return true;
    }
    
    // 배열 b의 모든 요소를 배열 a에 복사하기
    static int[] copy(int[] a, int[] b){
        if(a.length != b.length){
            System.out.println("배열 a,b의 길이는 같아야합니다.");
        }else{
            // b.length 3 0 1 2
            for(int i=0; i< b.length; i++){
                a[i] = b[i];
            }
        }
        return a;
    }
    
    // 배열 b의 모든 요소를 배열 a에 역순으로 복사하는 메서드 reverse copy 만들기
    static void reverseCopy(int[] a, int[] b){
        if(a.length != b.length){
            System.out.println("배열 a,b의 길이는 같아야합니다.");
        }else{
            // b요소를 a요소로 복사하기
            copy(a, b);
            // a요소를 reverse하기
            for(int i=0; i< a.length/2; i++){
                int length = a.length-i-1;
                swap(a, i, length);
            }            
        }
    }
    
    // 배열의 요소값을 역순으로 바꾸기
    static void swap(int[] a, int idx1, int idx2){
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }    
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("배열 a의 길이:");
        int na = scanner.nextInt();
        int[] a = new int[na];
        
        for(int i=0; i<na; i++){
            System.out.print("a[" + i + "] : ");
            a[i] = scanner.nextInt();
        }
        
        System.out.println("배열 b의 길이:");
        int nb = scanner.nextInt();
        int[] b = new int[nb];
        
        for(int i=0; i<nb; i++){
            System.out.print("b[" + i + "] : ");
            b[i] = scanner.nextInt();
        }
        
        System.out.println("배열 a,b가 같은가? "+equals(a,b));
        copy(a,b);
        System.out.println("배열 b요소를 a로 복사하기");
        for (int i=0; i<a.length; i++) {
            System.out.println("a[" + i + "] : " + a[i]);
        }
        reverseCopy(a,b);
        System.out.println("배열 b요소를 배열 a로 역순으로 복사하기");
        for (int i=0; i<a.length; i++) {
            System.out.println("a[" + i + "] : " + a[i]);
        }
    }
}
cs


결과 값



소스코드 첨부 :

myTest1.zip




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

배열사용, 제곱근 이하 소수 판단, 소수 찾기 알고리즘  (0) 2018.09.30
기수 변환, 정수를 입력받아 2진수 ~36진수 변환  (0) 2018.09.30
탐욕 알고리즘  (0) 2018.09.01
다익스트라 알고리즘  (0) 2018.08.25
해시함수란? 너비우선탐색 사용하기  (0) 2018.08.25

+ Recent posts

티스토리툴바