정보처리기사 실기 복습 03
20 May 2019
Reading time ~4 minutes
정보처리기사 실기 복습 03
선택 정렬
- 10개의 수치 자료를 입력 받아 배열에 저장한 후 저장된 자료를 오름차순으로 정렬
- 선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행
- 이 설명은 오름차순에 대한 설명, 내림차순이라면 1회전에 가장 큰 값을 찾아 첫 번째 위치에 놓음
- 회전 : 첫 번째 자료의 위치를 결정하기 위해 첫 번째 자료를 다른 모든 자료와 비교하는 과정
- 선택정렬에선 마지막 자료가 자기 자신과 비교하는 것을 생략하므로 자료가 10건이라면 9회전을 수행
public class Test23 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] input = new int[10];
for(int i=0; i<10; i++) {
System.out.print("입력해주세요["+i+"] : ");
input[i] = sc.nextInt();
}
System.out.println(Arrays.toString(input));
int min = 0;
int minIdx = 0;
int temp = 0;
for(int i=0; i<input.length; i++) {
min = 9999999;
for(int j=i; j<input.length; j++) {
if (input[j] < min) {
min = input[j];
minIdx = j;
}
}
temp = input[minIdx];
input[minIdx] = input[i];
input[i] = temp;
}
System.out.println(Arrays.toString(input));
}
}
버블정렬
- 배열의 기억된 10건의 자료를 오름차순으로 정렬
- 버블 정렬은 첫 번째 자료와 두 번째 자료를, 두 번째 자료와 세 번째 자료를, 세 번째와 네 번째를… 이런식으로 (마지막-1)번째 자료와 마지막 자료를 비교하여 교환하면서 자료를 정렬한다
- 1회전을 수행하고 나면 가장 큰 자료가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 자료는 정렬에서 제외된다
- 2회전을 수행하고 나면 끝에서 두 번째 자료까지는 정렬에서 제외된다
- 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 늘어난다
public class Test24 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] input = new int[10];
for(int i=0; i<input.length; i++) {
input[i] = sc.nextInt();
}
int temp = 0;
for(int i=0; i<input.length-1; i++) {
for(int j=i+1; j<input.length; j++) {
if (input[i] > input[j]) {
temp = input[j];
input[j] = input[i];
input[i] = temp;
}
}
}
System.out.println(Arrays.toString(input));
}
}
삽입 정렬
- 10개의 수치 자료를 입력 받아 배열에 저장한 후 저장된 자료를 오름차순으로 정렬
- 삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘
- 즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료, 네번째 자료는 세 번째, 두 번째, 첫 번째 자료와 비교한 후 자료가 삽입될 위치를 찾음
- 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킴
public class Test25 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int[] input = new int[10];
for(int i=0; i<10; i++) {
input[i] = sc.nextInt();
}
int key = 0;
int j = 0;
for(int i=1; i<input.length; i++) {
key = input[i];
for(j=i-1; j>=0; j--) {
if(input[j] > key) {
input[j+1] = input[j];
} else {
break;
}
}
input[j+1] = key;
}
System.out.println(Arrays.toString(input));
}
}
이분 검색
- 키보드로 입력 받은 값이 data배열의 몇 번째에 기억되어 있는지 알아보기 위해 출력하는 순서도를 작성하시오. 단 data[10] 배열에는 10개의 숫자가 들어 있으며, 찾는 자료가 없을 경우 자료와 함께 ‘not found’를 출력하고 끝냄
- 이분 검색은 말 그대로 검색할 자료를 반씩 나누어서 나머지 반만 검색하는 방식을 반복하여 자료를 찾는 것.
- 빠른 속도로 자료를 찾을 수 있다.
- 자료의 범위를 반씩 줄여 가는 것이므로 최대 검색 횟수는 log2N
- 단, 이분 검색은 데이터가 정렬되어 있어야 작업이 가능하다.
- 끝나는 조건은 자료의 범위를 좁혀오다 시작 위치가 끝 위치보다 커지면 해당 자료가 없는 것.
public class Test26 {
public static void main(String[] args) {
int[] data = { 7,15,33,60,61,70,80,92,99 };
Scanner sc = new Scanner(System.in);
int searchNum = sc.nextInt();
int start = 0, last = data.length, m = 0;
while(true) {
if (start <= last) {
m = (start+last)/2;
if (searchNum == data[m]) {
System.out.println("입력값 : "+searchNum+", 인덱스 위치 : "+m);
break;
}
if (searchNum < data[m]) {
last = m-1;
} else {
start = m+1;
}
} else {
System.out.println("입력하신 "+searchNum+"가 없습니다");
break;
}
}
}
}
병합 (MERGE)
- 병합은 정렬된 2개의 파일 또는 배열을 하나의 정렬된 자료로 만드는 것
- 배열을 이용할 때는 자료의 크기가 작은 쪽의 배열 첨자를 증가시키면서 2개의 배열을 1개로 합친다
- 병합을 수행할 때는 병합할 두 자료의 대소를 비교하여 클때, 같을 때, 작을 때를 구분하여 처리
public class Test28 {
static int a_idx = 0, b_idx = 0, m_idx = -1;
static void fillA(int[] a, int[] mergedArr) {
do {
m_idx++;
mergedArr[m_idx] = a[a_idx];
a_idx++;
} while(a[a_idx] != 0);
finish(mergedArr);
}
static void fillB(int[] b, int[] mergedArr) {
do {
m_idx++;
mergedArr[m_idx] = b[b_idx];
b_idx++;
} while (b[b_idx] != 0);
finish(mergedArr);
}
static void finish(int[] mergedArr) {
m_idx++;
mergedArr[m_idx] = 0;
System.out.println(Arrays.toString(mergedArr));
System.exit(0);
}
public static void main(String[] args) {
int[] a = {2,3,5,8,9,10,12,13,0};
int[] b = {1,3,5,7,0};
int[] mergedArr = new int[20];
while(true) {
m_idx++;
if (a[a_idx] < b[b_idx]) { // a값이 b보다 작으면
// a값을 merged에 넣고 인덱스 증가
mergedArr[m_idx] = a[a_idx];
a_idx++;
if (a[a_idx] == 0) {
fillB(b,mergedArr);
}
} else if (a[a_idx] == b[b_idx]) { // 두 값이 같으면
// 둘 중 한 값을 넣고 둘다 인덱스 증가
mergedArr[m_idx] = a[a_idx];
a_idx++;
b_idx++;
if (a[a_idx]==0) {
fillB(b,mergedArr);
} else if (b[b_idx] == 0) {
fillA(a,mergedArr);
}
} else { // b의 값이 a값보다 작을 때
// b를 merged에 넣고 인덱스 증가
mergedArr[m_idx] = b[b_idx];
b_idx++;
if(b[b_idx]==0) {
fillA(a,mergedArr);
}
}
}
}
}