『 1~100을 이용한 알고리즘의 이해 2: C언어편 』
저자: 김득수
사용 프로그램: Visual Studio 2019
※ 본 게시글에 작성된 문제는 책 본문과 일치하지 않는 부분이 존재하며, 풀이 또한 정확하지 않습니다.
11-1.
배열 A에 4개 데이터 (1, 3, 6, 8)이고 배열 B에 6개 데이터 (2, 4, 5, 7, 9, 10)이 정렬되어 있다.
배열 A와 배열 B의 정렬된 데이터를 배열 C에 오름차순 정렬을 위한 순서도를 완성하시오.
문제풀이
#include <stdio.h>
void main() {
int a[4] = { 1, 3, 6, 8 };
int b[6] = { 2, 4, 5, 7, 9, 10 };
int c[10];
int i = 0, j = 0, k = 0;
while ((i < 4) && (j < 6)) {
if (a[i] < b[j]) {
c[k] = a[i];
i++;
k++;
}
else {
c[k] = b[j];
j++;
k++;
}
}
if (i > 3) {
do {
c[k] = b[j];
j++;
k++;
} while (j <= 5);
}
else {
do {
c[k] = a[i];
i++;
k++;
} while (i <= 3);
}
for (k = 0; k < 10; k++) {
printf("%d \t", c[k]);
}
}
실행결과
1 2 3 4 5 6 7 8 9 10
11-2.
배열 A에 6개의 데이터 (2, 4, 5, 7, 9, 10)이고 배열 B에 4개 데이터 (1, 3, 6, 8)이 정렬되어 있다.
배열 A와 배열 B의 정렬된 데이터를 배열 C에 오름차순 정렬을 위한 알고리즘을 완성하시오.
문제풀이
#include <stdio.h>
void main() {
int a[6] = { 2,4,5,7,9,10 };
int b[4] = { 1,3,6,8 };
int c[10];
int i = 0, j = 0, k = 0;
while ((i <= 5) && (j <= 3)) {
if (a[i] < b[j]) {
c[k] = a[i], i++, k++;
}
else {
c[k] = b[j], j++, k++;
}
}
if (i > 5) {
do {
c[k] = b[j], j++, k++;
} while (j <= 3);
}
else {
do {
c[k] = a[i], i++, k++;
} while (i <= 5);
}
for (k = 0; k < 10; k++) {
printf("%d \t", c[k]);
}
실행결과
1 2 3 4 5 6 7 8 9 10
11-3.
배열 A에 (1, 6, 7, 2, 3, 4, 5, 8, 9, 10)의 10개 데이터가 앞부분 3개 뒷부분 7개는 이미 정렬되어 있는 경우 배열 C에 정렬하는 순서도를 완성하시오.
문제풀이
#include <stdio.h>
void main() {
int a[10] = { 1,6,7,2,3,4,5,8,9,10 };
int c[10];
int i = 0, j = 3, k = 0;
while ((i <= 2) && (j <= 9)) {
if (a[i] < a[j]) {
c[k] = a[i], i++, k++;
}
else {
c[k] = a[j], j++, k++;
}
}
if (i > 2) {
do {
c[k] = a[j], j++, k++;
} while (j <= 10);
}
else {
do {
c[k] = a[i], i++, k++;
} while (i <= 2);
}
for (k = 0; k <= 9; k++) {
printf("%d ", c[k]);
}
}
실행결과
1 2 3 4 5 6 7 8 9 10
11-4. 배열 A에 다음과 같은 데이터가 있는 경우 배열 C의 C(5)~C(14)에 정렬하는 순서도를 완성하시오.
| 배열 |
~ |
A(3) |
A(4) |
A(5) |
A(6) |
A(7) |
A(8) |
A(9) |
A(10)
|
A(11) |
A(12) |
~ |
| 데이터 |
? |
1 |
7 |
10 |
2 |
3 |
4 |
5 |
6 |
8 |
9 |
? |
문제풀이
#include <stdio.h>
void main() {
int a[12] = { 0, 0, 1, 7, 10, 2, 3, 4, 5, 6, 8, 9 };
int c[14];
int i = 2, j = 3, k = 4; // ※ j = 5
while ((i <= 4) && (j <= 11)) { // ※ i <= 11
if (a[i] < a[j]) {
c[k] = a[i], i++, k++;
}
else {
c[k] = a[j], j++, k++;
}
}
if (i > 11) { ※ i > 4
do {
c[k] = a[j], j++, k++;
} while (j <= 11); ※ i <= 12
}
else {
do {
c[k] = a[i], i++, k++;
} while (i <= 11); ※ i <= 4
}
for (k = 0; k <= 13; k++) { // ※ C(5)부터의 값이 필요한 것이므로, k = 4 여야함
printf("%d ", c[k]);
}
}
오답풀이
#include <stdio.h>
void main() {
int a[12] = { 0, 0, 1, 7, 10, 2, 3, 4, 5, 6, 8, 9 };
int c[14];
// 병합정렬을 염두해두고 임의로 숫자를 지정하되, 계산에 틀리지 않도록 유의
int i = 2, j = 5, k = 4;
while ((i <= 4) && (j <= 11)) {
if (a[i] < a[j]) {
c[k] = a[i], i++, k++;
}
else {
c[k] = a[j], j++, k++;
}
}
if (i > 4) {
do {
c[k] = a[j], j++, k++;
} while (j <= 12);
}
else {
do {
c[k] = a[i], i++, k++;
} while (i <= 4);
}
for (k = 4; k <= 13; k++) {
printf("%d ", c[k]);
}
}
실행결과
1 2 3 4 5 6 7 8 9 10