과제3
가정: 입력 파일 (in.txt)의 양식은 다음과 같다.
N a1 a2 a3 … an
N: 정수의 개수
ai: 오름차순으로 정렬된 서로 다른 양의 정수
단, 정수들은 1 개 이상의 space 로 구분됨
단계 1. 입력 파일 in.txt 에 포함된 정수들을 차례대로 읽어들여 array 에 저장한다. 이때, array 는
malloc 을 이용해 생성한 뒤 사용한다.
단계 2. scanf_s 를 이용하여 값 s 를 입력 받는다. 값 s 가 음수일 경우에는 프로그램 실행을 종료한다.
단계 3. Sequential search 를 이용하여 s 를 array 에서 search 한 뒤, search 에 성공하면 해당 index
번호를 출력하고 실패하면 -1 을 출력하라.
단계 4. 단계 3 을 수행하는 데 걸린 계산 시간을 ms (millisecond) 단위로 출력하라.
단계 5. Iterative binary search 를 이용하여 s 를 array 에서 search 한 뒤, search 에 성공하면 해당
index 번호를 출력하고 실패하면 -1 을 출력하라.
단계 6. 단계 5 를 수행하는 데 걸린 계산 시간을 ms 단위로 출력하라.
단계 7. Recursive binary search 를 이용하여 s 를 array 에서 search 한 뒤, search 에 성공하면 해당
index 번호를 출력하고 실패하면 -1 을 출력하라.
단계 8. 단계 7 를 수행하는 데 걸린 계산 시간을 ms 단위로 출력하라.
단계 9. Malloc 된 array 를 free 한다.
단계 10. 단계 2 부터 다시 반복하여 수행한다.
예제
(in.txt)
4 23 170 234 315
(실행)
컴퓨터학부 202020394 홍길동
(scanf_s) 175
(화면 출력)
Sequential : -1 <???ms>
Iterative : -1 <???ms>
Recursive : -1 <???ms>
(scanf_s) -1
(in.txt)
6 10 12 15 18 100 2000
(실행)
컴퓨터학부 202020394 홍길동
(scanf_s) 2000
(화면 출력)
Sequential: 5 <???ms>
Iterative: 5 <???ms>
Recursive: 5 <???ms>
(scanf_s) 19
(화면 출력)
Sequential: -1 <???ms>
Iterative: -1 <???ms>
Recursive: -1 <???ms>
(scanf_s) -10
풀이 코드
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int binsearch(int array[], int size, int key) {
int left, right;
int mid;
left = 0;
right = size - 1;
while (left <= right) {
mid = (left + right) / 2;
if (key == array[mid]) {
return mid;
}
else if (key < array[mid]) {
right = mid - 1;
}
else if (key > array[mid]) {
left = mid + 1;
}
}
return -1;
}
int recursive(int array[], int key, int left, int right) {
int mid;
if (left <= right) {
mid = (left + right) / 2;
if (key == array[mid]) {
return mid;
}
else if (key < array[mid]) {
return recursive(array, key, left, mid - 1);
}
else {
return recursive(array, key, mid + 1, right);
}
}
return -1;
}
int main() {
clock_t start, finish;
double elapsed;
while (1) {
int N, num, n; //정수 N search 하기 위한 수. num은 txt 저장하는 수, n은 정수의 개수
int index, key;
int count = 0;
scanf_s("%d", &N, sizeof(N));
if (N <= 0) {
return 0;
}
FILE* fp = NULL;
fopen_s(&fp, "in1.txt", "r");
if (fp == NULL) {
return 0;
}
fscanf_s(fp, "%d", &n);
int* array;
array = (int*)malloc(sizeof(int) * n);
for (int i = 0; i < n; i++) {
fscanf_s(fp, "%d", &num);
array[i] = num;
}
printf("\n");
start = clock();
for (int i = 0; i < n; i++) {
if (array[i] == N) {
printf("Sequential : %d\n", i);
count++;
}
}
if (count == 0) {
printf("Sequential : -1\n");
}
finish = clock();
elapsed = ((double)(finish)-(double)(start)) / CLOCKS_PER_SEC;
printf("time: %f\n", elapsed * 1000.0);
start = clock();
index = binsearch(array, n, N);
if (index == -1) {
printf("Iterative: -1\n");
}
else {
printf("Iterative : %d\n", index);
}
finish = clock();
elapsed = ((double)(finish)-(double)(start)) / CLOCKS_PER_SEC;
printf("time: %f\n", elapsed * 1000.0);
start = clock();
index = recursive(array, N, 0, n - 1);
if (index == -1) {
printf("Recursive: -1\n");
}
else {
printf("Recursive :%d\n", index);
}
finish = clock();
elapsed = ((double)(finish)-(double)(start)) / CLOCKS_PER_SEC;
printf("time: %f\n", elapsed * 1000.0);
fclose(fp);
free(array);
}
return 0;
}주의해야 할 점 : 재귀 함수 쓸 때 base case 주의하기!
풀이 결과
추가과제 #03
과제#3 의 문제에서 입력 파일의 내용을 양의 정수 대신 알파벳 소문자로 대치하여, scanf_s 로 입력
받은 알파벳 소문자를 search 하는 프로그램을 작성하라. 이때, scanf_s 로 알파벳 소문자가 아닌 문자가
입력되면 수행을 멈추도록 하라. *알파벳의 ASCII 코드를 사용하면 쉽게 구현 가능함.
예제
(in.txt)
5 a b d e f
(실행)
컴퓨터학부 202020394 홍길동
(scanf_s) a
(화면 출력)
Sequential : 0 <???ms>
Iterative : 0 <???ms>
Recursive : 0 <???ms>
(scanf_s) A
(in.txt)
4 c f g j
(실행)
컴퓨터학부 202020394 홍길동
(scanf_s) a
(화면 출력)
Sequential: -1 <???ms>
Iterative: -1 <???ms>
Recursive: -1 <???ms>
(scanf_s) g
(화면 출력)
Sequential: 2 <???ms>
Iterative: 2 <???ms>
Recursive: 2 <???ms>
(scanf_s) #
풀이 코드
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
int binsearch(char array[], int size, int key) {
int left, right;
int mid;
left = 0;
right = size - 1;
while (left <= right) {
mid = (left + right) / 2;
if (key == array[mid]) {
return mid;
}
else if (key < array[mid]) {
right = mid - 1;
}
else if (key > array[mid]) {
left = mid + 1;
}
}
return -1;
}
int recursive(char array[], int key, int left, int right) {
int mid;
if (left <= right) {
mid = (left + right) / 2;
if (key == array[mid]) {
return mid;
}
else if (key < array[mid]) {
return recursive(array, key, left, mid - 1);
}
else {
return recursive(array, key, mid + 1, right);
}
}
return -1;
}
int main() {
clock_t start, finish;
double elapsed;
while (1) {
char N;
int num, n; //정수 N search 하기 위한 수. num은 txt 저장하는 수, n은 정수의 개수
int index, key;
int count = 0;
char enter;
scanf_s("%c", &N, sizeof(char));
scanf_s("%c", &enter, sizeof(char));
if ((int)N < 97 || (int)N > 122) {
return 0;
}
FILE* fp = NULL;
fopen_s(&fp, "in3.txt", "r");
if (fp == NULL) {
return 0;
}
fscanf_s(fp, "%d ", &n);
char* array;
array = (char*)malloc(sizeof(char) * n);
for (int i = 0; i < n; i++) {
fscanf_s(fp, "%c ", &num);
array[i] = num;
}
printf("\n");
start = clock();
for (int i = 0; i < n; i++) {
if (array[i] == int(N)) {
printf("Sequential : %d\n", i);
count++;
}
}
if (count == 0) {
printf("Sequential : -1\n");
}
finish = clock();
elapsed = ((double)(finish)-(double)(start)) / CLOCKS_PER_SEC;
printf("time: %f\n", elapsed * 1000.0);
start = clock();
index = binsearch(array, n, int(N));
if (index == -1) {
printf("Iterative: -1\n");
}
else {
printf("Iterative : %d\n", index);
}
finish = clock();
elapsed = ((double)(finish)-(double)(start)) / CLOCKS_PER_SEC;
printf("time: %f\n", elapsed * 1000.0);
start = clock();
index = recursive(array, int(N), 0, n - 1);
if (index == -1) {
printf("Recursive: -1\n");
}
else {
printf("Recursive :%d\n", index);
}
finish = clock();
elapsed = ((double)(finish)-(double)(start)) / CLOCKS_PER_SEC;
printf("time: %f\n", elapsed * 1000.0);
fclose(fp);
free(array);
}
return 0;
}
주의해야 할 점 : 과제 3과의 코드가 비슷하나 문자 알파벳을 입력 받으므로 N을 char로 선언해줘야 된다.
그리고 문자열을 fscanf받을때는 text내의 띄워쓰기도 인식하므로 fscanf_s(fp, "%d ", &n);로 %d 뒤에 띄워쓰기를 해줘야된다.
풀이 결과
