이번 시간에는 참조형 자료형중 하나인 배열에 대해서 알아 보겠습니다. 배열은 여러방면에서 유용하게 사용되는 자료형입니다.
1. 배열이란?
- 동일한 자료형으로 구성된 연속된 자료의 집합
- 자바의 배열은 힙 메모리(레퍼런스 타입)를 할당
- 첨자는 0부터 시작
- 간단한 예시
- 배열 선언 : int[] data;
- 메모리 할당 : data = new int[10];
- 배열 요소의 이용 : data[0] = 10
- 배열의 데이터 개수는 length라는 속성으로 제공 = 배열명.length
- 일반 배열(정적 배열)의 장점 : 접근 방법이 쉽다.
- 일반 배열(정적 배열)의 단점 : ① 생성 시 크기를 결정하면 변경X
② 연속된 메모리 공간을 사용하므로 연속된 빈 공간이 없으면 생성X
③ 데이터를 정렬해두지 않으면 검색 속도가 느리다.
④ 데이터의 삽입과 삭제가 어렵다.
<예제 소스코드 - OneArray.class>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | public class OneArray { public static void main(String[] args) { // 배열 선언 및 초기화 int [] ar = {10,20,30}; for(int i=0; i<ar.length; i++) { System.out.println("ar[" + i + "]=" + ar[i]); } } } | cs |
<결과>
2. 다차원 배열
- 2차원 배열
- 배열의 크기 : 행과 열로 구분해서 표현
- 배열의 선언 : 자료형 [][] 배열명; OR 자료형 배열명 [][];
- 배열의 생성(배열의 메모리 할당)
- 배열명 = new 자료형[행][열];
- Ex) int [][] a = new int[2][3]; // 2행 3열의 배열(2x3행열)
<예제 소스코드 - DoubleArray.class>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 | public class DoubleArray { public static void main(String[] args) { // 2차원배열 선언과 동시에 초기화 int[][] ar = { { 10, 20 }, { 30, 40 } }; int i, j; // 행과 열을 출력하기위해 반복문 2 for (i = 0; i < ar.length; i++) { for (j = 0; j < ar[i].length; j++) System.out.print(" " + ar[i][j]); System.out.println(); } } } | cs |
<결과>
3. 가변 배열
- 자바는 배열을 참조형으로 처리하므로 가변 배열 선인이 가능
- 가변(可變) : 사물의 모양이나 성질이 바뀌거나 달라질 수 있음. 또는 사물의 모양이나 성질을 바꾸거나 달라지게 할 수 있음.
- Ex) int [][] var = new int[3][]
var[0] = new int[1]
var[1] = new int[2]
var[2] = new int[3]
<예제 소스코드 - VarialbeArray.class>
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 | public class VariableArray { public static void main(String args) { // 가변 배열 선언 int[][]ar = new int[3][]; int i, j = 0; // 가변 배열 메모리 할당 ar[0] = new int[1]; ar[1] = new int[2]; ar[2] = new int[3]; // 배열 ar[0][0] = 10; ar[1][0] = 20; ar[1][1] = 30; ar[2][0] = 40; for(i = 0 ; i < ar.length ; i++) { for(j = 0 ; j < ar[i].length ; j++) { System.out.print("ar[" + i + "]" + "[" + j + "]=" + ar[i][j] + " "); } System.out.println(); } } } | cs |
<결과>
4. 정렬
- 정렬은 데이터를 순서대로 나열하는 것을 의미합니다.
⑴ 선택정렬(Selection Sort)
- 선택정렬은 첫 번째 자리부터 마지막에서 두 번째 자리까지 자신보다 뒤에 있는 모든 자리들과 비교해서 다음 자료가 작으면 2개의 요소의 자리를 변경해줍니다.
<초기상태>
5 |
4 |
1 |
2 |
3 |
↓1번째 자리를 기준으로 2,3,4,5 번째 자리와 비교
<1Pass>
1 |
5 |
4 |
2 |
3 |
↓1번째 자리는 제외하고 2번째 자리를 기준으로 3,4,5 번째 자리와 비교
<2Pass>
1 |
2 |
5 |
4 |
3 |
↓3번째 자리를 기준으로 4,5 번째 자리와 비교
<3Pass>
1 |
2 |
3 |
5 |
4 |
↓4번째 자리를 기준으로 5 번째 자리와 비교
<4Pass>
1 |
2 |
3 |
4 |
5 |
<예제 소스코드 - SelectionSort.class>
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 | public static void main(String args[]) { // 정렬할 배열 초기화 int test[] = { 20, 30, 40, 50, 10 }; int i, j, temp; System.out.println("정렬 전"); // 정렬전 데이터 출력 for(i = 0 ; i < 5 ; i++) { System.out.println((i + 1) + "번째 데이터" + test[i]); } // 선택 정렬 for(i = 0 ; i < 4 ; i++) { for(j = i+1 ; j < 5 ; j++) { if(test[i] < test[j]) { temp = test[i]; test[i] = test[j]; test[j] = temp; } } } System.out.println("====================="); System.out.println("====================="); System.out.println("정렬 후"); // 선택후 for( i = 0 ; i < 5 ; i++) { System.out.println((i+1) + "번째 데이터" + test[i]); } } | cs |
<결과>
⑵ 버블정렬(Bubble Sort)
- 버블 정렬은 n개의 데이터가 있을 때 1부터 n-1번째 자료까지 n-1번 동안 다음 자료와 비교해가며 정렬하는 방법 입니다.
※빨간색칸은 정렬 대상, 파란색칸은 완료 된 원소
<초기상태>
7 |
4 |
11 |
9 |
2 |
<1Pass과정>
4 |
7 |
11 |
9 |
2 |
4 |
7 |
11 |
9 |
2 |
4 |
7 |
9 |
11 |
2 |
4 |
7 |
9 |
2 |
11 |
<2Pass과정>
4 |
7 |
9 |
2 |
11 |
4 |
7 |
8 |
2 |
11 |
4 |
7 |
2 |
9 |
11 |
<3Pass과정>
4 |
7 |
2 |
9 |
11 |
4 |
2 |
7 |
9 |
11 |
<4Pass과정>
2 |
4 |
7 |
9 |
11 |
<예제 소스코드 - BubbleSort.class>
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 BubbleSort { public static void main(String[] args) { // 정렬 할 배열 선언 int test[] = { 20, 30, 40, 50, 10 }; int i, j, temp, flag; System.out.println("정렬 전"); for (i = 0; i < 5; i++) // 정렬 전 배열 출력 { System.out.println((i + 1) + "번째 데이터" + test[i]); } // 버블 정렬 for (i = 0; i < 4; i++) { flag = 0; for (j = 0; j < 4 - i; j++) { if (test[j] < test[j + 1]) { temp = test[j]; test[j] = test[j + 1]; test[j + 1] = temp; flag = 1; } } if (flag == 0) { break; } } System.out.println("====================="); System.out.println("====================="); System.out.println("정렬 후"); for (i = 0; i < 5; i++) // 정렬 후 배열 { System.out.println((i + 1) + "번째 데이터" + test[i]); } } } | cs |
<결과>
5. 검색
- 검색이란 말그대로 원하는 원소를 찾는 것 입니다.
⑴ 순차 검색(SequentialSearch)
- 데이터가 정렬되어 있지 않은 경우 첫 번째 데이터부터 마지막 데이터까지 모두 검색해서 찾는 방법입니다.
- 데이터가 많거나 찾고자 하는 데이터가 배열에 없는 경우가 많을 경우 매우 비효율적인 방ㅂ법입니다.
<초기상태>
7 |
4 |
11 |
9 |
2 |
--------------------------------------------------------------------------------------------->
- 찾는 수가 11일때 하나하나 확인해 가며 11을 찾는 것이다.
<예제 소스코드 - SequentialSearch.class>
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 | import java.io.BufferedReader; import java.io.InputStreamReader; public class SequentialSearch { public static void main(String[] args) { // 배열 초기화 int ar[] = { 23, 47, 19, 63, 57, 26, 75, 73, 82, 89, 47, 11 }; int i, num; int key = 0, index = 0; num = ar.length; // 배열의 길이 BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); System.out.print("찾고자 하는 숫자를 2자리로 입력하세요: "); try { key = Integer.parseInt(in.readLine()); } catch (Exception e) // 예외 처리 { System.out.println("입력 오류"); } // 배열의 길이 만큼 반복 for (i = 0; i < num; i++) { // 키값과 벼열의 값이 같아질경우 // i+1값이 인덱스로 저장 if (ar[i] == key) { index = i + 1; } } // 인덱스 0인경우 찾는 값이 없음 if (index == 0) { System.out.println("찾고자 하는 값이 없습니다."); }else // 인덱스가 0이 아닐경우 위에 저장한 인덱스 { System.out.println("찾는 값은 " + index + "번째에 있습니다."); } } } | cs |
<결과>
⑵ 이분 검색(Binary Search)
- 데이터가 정렬되어 있는 경우 중앙 값과 비교해서 작으면 왼쪽, 크면 오른쪽으로 이동해서 검색하는 방법입니다.
① low = 0, high = n(데이터 개수) - 1로 초기화
② 무한 반복문에서 low> high 이면 데이터가 없는것 -> break
③ 아닐시 middle = (low + high)/2를 해서 middle값 찾기
④ 검색 값과 data[middle]과 비교해서 같으면 출력후 break
⑤ 검색 값이 중앙값보다 크다면 low = middle + 1
⑥ 작다면 high = middle -1 을 해서 loop를 돌리면 됩니다.
<예제 소스코드 - BinarySearch.class>
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 | import java.io.BufferedReader; import java.io.InputStreamReader; public class BinarySearch { public static void main(String args[]) { // 배열 초기화 int data[] = { 11, 16, 21, 26, 35, 39, 47 }; int k = 0, cnt = 0; int low = 0; int high = data.length - 1; int middle; BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); System.out.print("찾고자 하는 숫자를 2자리로 입력하세요: "); try { k = Integer.parseInt(in.readLine()); }catch(Exception e) // 예외 처리 { System.out.println("입력 오류"); } // 무한 반복문 사용 while (true) { if(low > high) // low값이 high값 보다 커질시 데이터가 없음 { System.out.println("검색 데이터가 없습니다."); break; } middle = ( low + high ) / 2; // 중앙값 구하기 cnt++; // 몇번 만에 찾는지 확인하기위한 카운트 변수 증가 System.out.println("비교값 : " + data[middle]); if( data[middle] == k ) // key값과 인덱스가 중앙값인 배열과 같을시 찾음 { System.out.println( middle + 1 + "번쨰 위치 검색횟수 = " + cnt + "번" ); break; } // 키값이 더 클시 low 값을 +1 if( k > data[middle] ) { low = middle + 1; }else // 키값보다 작을시 high값을 중앙값-1 { high = middle - 1; } } } } | cs |
<결과>
이번 시간에는 배열과 더 나아가서 정렬과 검색을 간단한 예제를 통해 알아보았습니다.
다음 시간에는 예외처리와 java.lang패키지에 대해 공부하겠습니다.
'조재연의 Java 개꿀떡 > 조재연의 Java 기초 개꿀떡' 카테고리의 다른 글
| 자바(Java)의 기초 박살내기 - 스레드(Thread) (0) | 2017.07.10 |
|---|---|
| 자바(Java)의 기초 박살내기 - 예외처리(Exception) & java.lang 패키지 (0) | 2017.07.06 |
| 자바(Java)의 기초 박살내기 - 상속(Inheritance)과 다형성(Polymorphism) (1) | 2017.07.04 |
| 자바(Java)의 기초 박살내기 - 객체지향(클래스)의 기본 개념 (0) | 2017.07.02 |
| 자바(Java)의 기초 박살내기 - 제어문(Control Statement) (0) | 2017.06.30 |
