---
title: "정보처리기사 실기 알고리즘 정리 04"
date: "2018-08-03"
tags: ["정보처리기사실기"]
status: archived
verified: false
---
## 정보처리기사 실기 알고리즘 정리 04
---
### 10개의 수치 자료를 입력 받아 배열에 저장한 후 저장된 자료를 오름차순으로 정렬하는 순서도를 작성하시오
(삽입 정렬)
#### 알고리즘의 이해
* 삽입 정렬은 두 번째 자료부터 시작하여 그 앞(왼쪽)의 자료들과 비교하여 삽입할 위치를 지정한 후 자료를 뒤로 옮기고 지정한 자리에 자료를 삽입하여 정렬하는 알고리즘.
* 즉, 두 번째 자료는 첫 번째 자료, 세 번째 자료는 두 번째와 첫 번째 자료, 네번째 자료는 세 번째, 두 번째, 첫 번째 자료와 비교한 후 자료가 삽입될 위치를 찾음.
* 자료가 삽입될 위치를 찾았다면 그 위치에 자료를 삽입하기 위해 자료를 한 칸씩 뒤로 이동시킴.
* 변수
* a[10] : 정렬할 숫자가 저장될 배열
* j : 입력 받은 숫자의 개수가 저장될 배열
* i : 정렬 회전 수, key 값의 위치를 지정해 주는 변수, 즉 i는 2부터 10까지 차례로 변경됨
* k : 비교 대상이 있는 위치를 지정해 주는 변수, 즉 k는 i-1에서 i까지 차례로 변경됨
* key : 비교 기준인 key 값이 저장될 변수
```cpp
main() {
int j, i, k, key;
int a[10];
j = -1;
do {
j++;
scanf("%d", &a[j]);
} while(j < 9);
for (i = 1; i <= 9; i++) { // i는 정렬 회전수(기준값 인덱스)
key = a[i]; // 비교 기준 key. 2부터 시작함
for (k = i - 1; k >= 0; k--) { // 왼쪽에 있는 수를 비교, 비교대상을 가리키는 k
if (a[k] > key) // 왼쪽에 더 기준보다 큰수가 있다면
a[k + 1] = a[k]; // 비교대상을 오른쪽칸으로 이동시킴
else // 왼쪽 비교 대상이 키값보다 작으면
break; // 비교안하고 빠져나옴
}
a[k + 1] = key; // 비교대상(왼쪽)값 바로 우측칸이 삽입될 위치, 그 자리에 기준값 삽입
}
for (i = 0; i <= 9; i++)
printf("%d", a[i]);
}
```
#### if 문을 이용한 삽입 정렬
```cpp
main() {
int i, k, key;
int a[20] = {
9,7,4,6,3,1,8,2,5,10,19,17,14,16,13,11,18,12,15,20
};
i = 1; // 2번째 요소부터 기준으로 비교
do {
key = a[i]; // 2번째 값을 key에 저장하고
k = i - 1; // 기준 왼쪽을 비교할 인덱스 k
do {
if (key < a[k]) { // key값이 왼쪽 값보다 작으면 정렬해야지
a[k+1] = a[k]; // 왼쪽에 있던 값을 오른쪽에 옮김.
k--; // 옮기고 비교 대상을 왼쪽으로 한칸 이동
} else { // 왼쪽에 비교대상이 현재 기준값보다 작으면
break; // 빠져나옴.
}
} while(k >= 0);
a[k+1] = key; // 해당 비교대상 + 1(우측)에 기준값을 넣음(제자리)
i++; // 기준값 인덱스를 올림.
} while(i <= 19);
for (i = 0; i < 20; i++)
printf("%d ", a[i]);
}
```
### 10명의 학생에 대한 중간고사 점수의 석차를 구하는 순서도를작성하시오.
(석차 구하기 - 배열 이용)
#### 알고리즘의 이해
* 특정인 점수에 대한 석차를 알려면 다른 사람들과 점수를 비교해 보면 됨.
* 다른 사람들과 비교 전엔 1등이고, 비교하며 점수가 높은 사람이 있으면 석차를 1씩 증가시킴.
* 여러 사람의 석차를 계산한다면 이런 작업을 모든 사람에게 반복해 적용하면 됨.
* 변수
* score[10] : 입력 받은 점수가 저장될 배열
* m : 입력 받은 점수의 개수가 저장될 변수(점수를 입력 받을 때 사용)
* rank[10] : 석차가 저장될 배열
* n : 입력 받은 점수의 개수가 저장될 변수(석차를 구하는 과정에서 사용)
* i : 회전 수, 석차를 구할 점수가 있는 위치를 지정해 주는 변수
* j : 각 회전에서의 비교 횟수, 비교 대상 점수가 있는 위치를 지정해 주는 변수
```cpp
main() {
int m, n, i, j;
int score[10], rank[10];
m = -1;
do {
m++;
scanf("%d", &score[m]);
} while(m < 9);
n = 9;
i = 0;
while (i <= n) {
rank[i] = 1; // 모든 등수를 1로 초기화
i++;
}
i = 0; // 회전수 i, 비교 기준 인덱스
while (i <= n) {
j = 0; // 비교 대상 인덱스 j
while (j <= n) {
if (score[i] < score[j]) // 비교대상의 점수가 더 높으면 기준의 등수를 올림.
rank[i]++;
j++;
}
i++;
}
for (int x = 0; x < 10; x++)
printf("%d ", score[x]);
printf(" \n");
for (int x = 0; x < 10; x++)
printf("%d ", rank[x]);
}
```
### 10명 학생의 국어, 수학 점수를 각각 입력 받아 총점을 계산한 후 총점 기준 내림차순으로 순위를 출력하는 순서도를 작성하시오. 단, 동점은 동석차로 하고 총점이 0인 경우는 출력하지 않음.
(석차구하기 - 바로 출력)
알고리즘의 이해
* 유형 1과 다른 점은 석차를 배열에 넣지 않고 바로 출력한다는 것.
* 즉, 어떤 사람의 석차가 1등이라 가정하고 다른 사람들과 비교하면 석차를 계산 후 점수와 함께 바로 출력한다.
* 석차를 매길 사람이 10명이라면 이런 일은 10번 반복.
* 변수
* kor[10] : 국어 점수가 저장될 변수
* mat[10] : 수학 점수가 저장될 변수
* sum[10] : 국어와 수학 점수의 합계가 저장될 배열
* i : 입력 받은 자료의 개수가 저장될 변수, 비교 기준 점수의 위치를 지정해 주는 변수(회전수)
* j : 비교 대상의 위치를 지정해 주는 변수, 각 회전에서의 비교수
* rank: 석차가 계산되어 저장될 변수
```cpp
main() {
int i, j, rank; // i는 비교 기준 인덱스, j는 비교 대상 인덱스
int kor[10], mat[10], sum[10];
i = -1;
do {
i++;
scanf("%d %d", &kor[i], &mat[i]);
sum[i] = kor[i] + mat[i];
} while(i < 9);
for (i = 0; i <= 9; i++) {
if (sum[i] != 0) {
rank = 1; // 현재 비교 기준 i의 등수를 1로 초기화
for (j = 0; j <= 9; j++) { // 비교대상보다 점수가 낮으면 등수를 올림
if (sum[i] < sum[j])
rank++;
}
printf("%d %d %d %d %d\n", i + 1, kor[i], mat[i], sum[i], rank);
}
}
}
```
### 키보드로 입력 받은 값이 data배열의 몇 번째에 기억되어 있는지 알아보기 위해 출력하는 순서도를 작성하시오. 단 data[10] 배열에는 10개의 숫자가 들어 있으며, 찾는 자료가 없을 경우 자료와 함께 ‘not found’를 출력하고 끝냄.
(이분 검색 - 1차원 배열)
알고리즘의 이해
* 이분 검색은 말 그대로 검색할 자료를 반씩 나누어서 나머지 반만 검색하는 방식을 반복하여 자료를 찾는 것.
* 빠른 속도로 자료를 찾을 수 있다.
* 자료의 범위를 반씩 줄여 가는 것이므로 최대 검색 횟수는 log2N
* 자료가 100건일 때 , log<sub>2</sub>100 = log<sub>2</sub>2<sup>6.xx</sup> = 6회. 100만건이라도 19번만 검색하면 찾을 수 있음.
* 단, 이분 검색은 데이터가 정렬되어 있어야 작업이 가능하다.
* 끝나는 조건은 자료의 범위를 좁혀오다 시작 위치가 끝 위치보다 커지면 해당 자료가 없는 것.
* 변수
* data[10] : 입력 받은 숫자가 저장될 배열
* input : 입력 받은 찾을 값이 저장될 변수
* start : 검색 범위의 시작 위치를 지정해 주는 변수
* last : 검색 범위의 마지막 위치를 지정해 주는 변수
* m : 검색 위치의 중간 위치가 저장될 변수
```cpp
main() {
int input, start, last, m;
int data[10] = {8,15,35,60,61,70,80,92,99};
scanf("%d", &input);
start = 0; // 탐색 범위 0~
last = 9; // 탐색 범위 ~9
while (1) {
if (start <= last) { // 탐색 시작 인덱스가 끝 인덱스보다 커지면 없는거
m = (start + last) / 2; // 가운데 인덱스 찾음
if (input == data[m]) { // 입력 값과 비교, 동일하면 출력(값, 인덱스 위치))
printf("%d %d", input, m + 1);
break;
}
if (input < data[m]) // 입력값이 가운데 값보다 작으면
last = m - 1; // 가운데 인덱스보다 왼쪽 탐색
else
start = m + 1; // 가운데 값보다 크면 가운데 인덱스보다 오른쪽 탐색
} else {
printf("%d NOT FOUND", input);
break;
}
}
}
```
### 키보드로 입력 받은 번호에 대한 점수를 data 배열에서 찾아 출력하는 순서도를 작성하시오. 단 data[2][10] 배열에는 번호와 점수가 들어 있다고 가정하고, 찾는 자료가 없을 경우 자료와 함께 “NOT FOUND”를 출력하고 끝낸다.
(이분 검색 - 2차원 배열)
#### 알고리즘의 이해
* 2차원 배열 1행에는 학생 번호가, 2행에는 학생 점수가 저장되어 있다.
* 변수
* data[2][10] : 자료가 저장될 2차원 배열
* input : 찾을 번호가 저장될 변수
* start : 검색 범위의 시작 위치를 지정해 주는 변수
* last : 검색 범위의 마지막 위치를 지정해 주는 변수
* m : 검색 범위의 중간 위치가 저장될 변수
```cpp
main() {
int input, start, last, m;
int data[2][10] = {
{1,2,3,4,5,6,7,8,9,10},
{100,66,25,88,90,65,87,86,58,99}
};
scanf("%d", &input);
start = 0;
last = 9;
while (1) {
if (start <= last) {
m = (start + last) / 2;
if (input == data[0][m]) { // 입력 받은 값과 학생번호의 값이 같은지 확인
printf("%d %d\n", input, data[1][m]); // 같으면 점수 결과 출력.
break;
}
if (input < data[0][m])
last = m - 1;
else
start = m + 1;
} else {
printf("%d NOT FOUND", input);
break;
}
}
}
```
### 다음 처리 조건에 맞게 병합하는 순서도를 작성하시오(병합(MERGE))
#### 처리 조건
1. 배열 A, B에는 정수가 오름차순으로 정렬되어 있다.
2. 데이터는 10건 미만이다.
3. 배열 A, B에서 0이 들어 있는 다음 요소에는 데이터가 없는 것으로 간주한다.
4. 배열 A, B를 병합시켜 배열 C에 기억시키고 맨 마지막에는 0을 기억시킨다.
5. 배열 A와 B에 같은 데이터가 있으면 한 번만 C에 옮긴다.
* 예)
* A[10] : 1, 3, 5, 6, 0
* B[10] : 2, 3, 5, 8, 9, 10, 12, 13, 0
* C[20] : 1, 2, 3, 5, 6, 8, 9, 10, 12, 13, 0
#### 알고리즘의 이해
* 병합은 정렬된 2개의 파일 또는 배열을 하나의 정렬된 자료로 만드는 것.
* 배열을 이용할 때는 자료의 크기가 작은 쪽의 배열 첨자를 증가시키면서 2개의 배열을 1개로 합친다.
* 병합을 수행할 때는 병합할 두 자료의 대소를 비교하여 클때, 같을 때, 작을 때를 구분하여 처리하면 됨.
* 두 배열을 합치므로 20짜리 c배열 필요
* a, b, c의 위치를 가리키는 변수 사용
* a의 값 < b의 값
* a의 값을 c에 넣고 a와 c ++ 1
* a의 값 == b의 값
* 둘 중 한개의 값만 c에 넣고 a, b둘다 ++1
* a의 값 > b의 값
* b의 값을 c에 넣고 b와 c ++1
* 0이면 배열의 끝이므로 한 배열이 끝나면 나머지 배열의 값을 모두 넣고 0을 붙여 끝을 알림
* 변수
* a[10] : 병합할 자료가 들어 있는 배열
* b[10] : 병합할 자료가 들어 있는 배열
* c[20] : 2개의 배열을 병합할 자료가 들어갈 배열
* c_index : 배열 c의 위치를 지정해 주는 변수
* a_index : 배열 a의 위치를 지정해 주는 변수
* b_index : 배열 b의 위치를 지정해 주는 변수
```cpp
#include
#include // exit(), atoi(), atof()함수가 정의되어 있는 헤더
void fillA(a, c); // b 요소가 0일 때, 남은 a 배열 값으로 c를 채우는 함수
void fillB(b, c); // a 요소가 0일 때, 남은 b 배열 값으로 c를 채우는 함수
void finishC(c); // fillA, fillB가 끝나고 c배열에 0을 붙여주는 함수
int a_index, b_index, c_index;
main() {
int a[10] = {2,3,5,8,9,10,12,13,0};
int b[10] = {1,3,5,6,0};
int c[20];
a_index = 0;
b_index = 0;
c_index = -1;
while (1) {
c_index++;
if (a[a_index] < b[b_index]) { // a값이 b의 값보다 작으면 c에 넣고 a, c인덱스 증가
c[c_index] = a[a_index];
a_index++;
if (a[a_index] == 0)
fillB(b, c);
} else if (a[a_index] == b[b_index]) {// 두 값이 같으면, a의 값 저장, a,b 두 인덱스 증가
c[c_index] = a[a_index];
a_index++;
b_index++;
if (a[a_index] == 0)
fillB(b, c);
else if (b[b_index] == 0)
fillA(a, c);
} else { // b의 값이 a값보다 작을 때 b를 c에 넣고 b, c인덱스 증가
c[c_index] = b[b_index];
b_index++;
if (b[b_index] == 0)
fillA(a, c);
}
}
}
void fillB(int b[10], int c[10]) {
if (b[b_index] == 0)
finishC(c);
do {
c_index++;
c[c_index] = b[b_index];
b_index++;
} while(b[b_index] != 0);
finishC(c);
}
void fillA(int a[10], int c[10]) {
do {
c_index++;
c[c_index] = a[a_index];
a_index++;
} while(a[a_index] != 0);
finishC(c);
}
void finishC(int c[10]) {
c_index++;
c[c_index] = 0;
for (int i = 0; i < 20; i++) {
if (c[i] == 0)
break;
printf("%d ", c[i]);
}
exit(0);
}
```
### 10 개의 요소를 갖는 1차원 배열을 스택으로 이용하는 순서도를 작성하시오. 입출력되는 데이터가 스택의 크기보다 커지면 “Overflow”를 출력하고, 제거할 데이터가 없으면 “Underflow”를 출력한다.
(스택(stack))
* 스택은 한쪽 끝으로만 자료의 삽입과 삭제가 이루어지는 자료구조.
* 배열을 이용해 단순 스택을 구성할 때는 배열의 가장 마지막에 삽입된 자료의 위치, 즉 스택 포인터의 위치를 이용하여 입력과 제거를 수행.
* 스택에 자료를 삽입하는 작업을 push라 하고, 스택에서 자료를 제거하는 작업을 pop이라 함.
* 변수
* stack[5] : 스택으로 이용할 배열
* top : 스택 포인터로 값을 저장할 스택의 위치를 기억하는 변수
* i : 입력할 값, 제거한 값, overflow, underflow 등을 확인하는 다용도 변수
* select : 입력 또는 삭제를 선택할 변수(1이면 삽입(push), 2이면 삭제(pop))
* input : 스택에 저장될 자료를 입력 받을 변수
* push_val : push 함수에서 k의 값을 받을 변수
* pop_val : pop 함수에서 스택에서 제거된 자료를 기억할 변수
```cpp
#include
#define MAX 5 // 숫자 5를 MAX로 정의
int stack[MAX];
int top = -1;
int push(int push_val) {
top++;
if (top >= MAX) {
printf("OverFlow!\n");
top--;
return -1;
}
stack[top] = push_val;
return 0;
}
int pop(void) {
int pop_val;
if (top < 0) {
printf("UnderFlow!\n");
return -1;
}
pop_val = stack[top];
top--;
return pop_val;
}
main() {
while (1) {
int i, select, input;
printf("작업을 선택하세요 : (1)삽입, (2)삭제 : ");
scanf("%d", &select);
if (select == 1) {
printf("삽입할 숫자를 입력하세요 : ");
scanf("%d", &input);
i = push(input);
if (i == -1) break;
} else if (select == 2) {
i = pop();
if (i == -1) break;
else
printf("제거된 자료는 %d입니다. \n", i);
} else break;
}
if (top < 0)
printf("스택에 자료가 없습니다.\n");
else {
printf("스택의 자료는 다음과 같습니다.\n");
for (int i = top; i >= 0; i--)
printf("%10d ", stack[i]);
}
}
```