★ 「2019학년도 1학기」 수/업/노/트 ★
by. 동동매니저 >_<
▶ 일자 : 2019년 04월 02일 (화)
▶ 과목 : 자료구조 1 실습
▶ 담당 교수님 : SCH 컴소공 성낙준 교수님
※ 실습 내용을 요약해보면?
▶ 반복문과 순환 알고리즘 활용
※ 오늘 실습한 문제!!
★ 문제 1
▶ 319 만큼 반복문을 수행하는 시간을 측정하시오.
▶ 값을 직접 계산해서 파일에 출력한 후, 비어있는 반복문으로 시간을 측정
★ 문제 2
▶ 순환 알고리즘으로 팩토리얼을 계산하는 프로그램을 작성하시오.
▶ 최대 얼마까지 구할 수 있는지도 측정!!
※ 문제를 풀어보면? (소스 코드)
★ 문제 1
#include <stdio.h>
#include <time.h>
int main(void){
int n=1; // 반복 횟수
int i;
clock_t start,finish; // 시작 및 종료 시간 측정
FILE *fp; // 파일 포인터 선언
for(i=0;i<19;i++) n*=3; // 3^19를 직접 계산
fp=fopen("data.txt","w"); // 파일을 쓰기 모드로 열기
fprintf(fp,"%d",n); // 파일에 계산된 값을 출력
fclose(fp); // 파일 닫기
printf("%d\n",n); // 계산된 값을 화면에 출력
start=clock(); // 시간 측정 시작
for(i=0;i<n;i++){} // 아무것도 하지 않는 반복문
finish=clock(); // 시간 측정 종료
printf("소요시간 : %.3f초\n",(double)(finish-start)/CLOCKS_PER_SEC); // 소요시간 출력
return 0;
}★ 문제 2
#include <stdio.h>
// 팩토리얼 계산 함수 (순환 알고리즘)
long long factorial(int i){
printf("factorial(%d)...\n",i); // 현재의 i 값 출력
if(i<1) return 1; // 순환을 멈추는 부분
else return i*factorial(i-1); // 순환 호출 부분
}
int main(void){
int n; // 팩토리얼을 구할 수
printf("팩토리얼을 구할 수 입력 : ");
scanf("%d",&n); // n을 입력받음
printf("계산값 : %lld\n",factorial(n)); // 팩토리얼 계산값 출력
return 0;
}
※ 수업을 듣고 나서 느낀 점!!
▶ 319 = 약 11억을 넘어가는데, 컴퓨터가 성능이 좋아져서 그런지, 필자의 노트북 컴퓨터로 약 2.6초가 소요되었음.
▶ 또, 팩토리얼 함수의 순환 호출에서 매우 큰 수를 입력하면 Stack Overflow가 발생할 수 있음.
▶ 팩토리얼의 경우 계산값이 기하급수적으로 커지기 때문에, int보다 큰 long long을 사용해도 약 20!까지만 정확히 계산할 수 있었음.
▶ 특히 피보나치 수열을 구할 때 순환을 사용하게 된다면...?? (당연히 Stack Overflow가 일어나겠죠??)
※ 기타 참고 사항!!
▶ 없음