ZeroWiki - User contributions [en]

새싹교실/2018/C알

2018-05-12T10:45:58Z

211.37.12.90:

__TOC__

= 참여 인원 =
{| class="wikitable"
|-
| 튜터
| [[성훈]]
| 14학번
|-
| rowspan="3" | 튜티
| [[김승진]]
| rowspan="2" | 18학번
|-
| [[임창성]]
|}

= 진행 =
* 시간 : 화요일 17시 ~ 19시
* 장소 : 208관 6층 팀플실(자리 없으면 실습실)
* C언어, 포인터부터
* 알고리즘 개요 까지
= 진행 내역 =
* [[새싹교실/2018/C알/3월 27일]] : introduction
* [[새싹교실/2018/C알/4월 2일|/4월 3일]]
* [[새싹교실/2018/C알/4월11일|/4월 11일]] : 보강
* /5월 1일 : 휴강
* [[새싹교실/2018/C알/5월 1일|/5월 8일]]
= 기타 / 방명록 =
3년째 새싹을 길러내시는 제로페이지 대농이시닷 - [[안재형]]
* 그 대농의 새싹은 커서 갓재형이 됩니다. - [[박인서]]
* 이 반은 왜 처음부터 포인터를 나가죠..ㄷㄷ - [[박인서]]
* 조곤조곤하게 다 알려주는 튜터.. ㄷㄷㄷ - [[익명]]
* 파이팅~! - [[임창성]]
-----------------------------------
[[새싹교실/2018]]

새싹교실/2018/C알/5월1일

2018-05-12T10:38:21Z

211.37.12.90:

__TOC__
= 예정 =
* C언어 문법은 일단 여기까지
* 본격적 알고리즘 시작
* 선형 자료 구조(linear data structure)
** 배열(array) : fixed-sized collection of contiguous data
** random access
** 연결 리스트(linked list) : sequential of data linked by pointer
** node - link
** array v.s. linked list
* algorithms for sequential data
** 탐색(search)
** 선형 탐색(linear search)
** 이진 탐색(binary search)
** 정렬(sort)
** 선택 정렬(selection sort)
** 삽입 정렬(insertion sort)
** 병합 정렬(merge sort)
*** divide-and-conqurer
** 퀵 정렬(quick sort)
** performance
*** big-O notation(big-Omega, big-Theta)
*** speed, time complexity
*** memory, space complexity, in-place sort
*** stablity
** swap sort v.s. others
*** e.g) counting sort, radix sort
** '''이번주는 일정이 안맞아 휴강; 다음주에 이 내용으로 진행합니다.'''
= 진행 =

= 실습 =

* selection_sort, insertion_sort, merge_sort, quick_sort(,bubble_sort : optional)
*
<sort_instruction> input_file [output_file]
* any language
* input :
** 1st line : # of line N
** 2nd ~ : (unsorted) N integers
* output:
** N line : sorted N integers
** N + 1 line : elapsed time (in millisecond)
** print in output file; if no argument, to standard output(terminal console)

= 과제 =
* 창성
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<time.h>

#define swap(type,x,y) type t = x; x = y; y = t; //교환함수

void selection(void); //선택정렬
void insertion(void); //삽입정렬
void merge(int,int); //병합정렬
void quick(int,int); //퀵정렬
void bubble(void); //버블정렬
void output(char*); //(output.txt로 정렬된 수열과 elapsed time 출력) or 표준출력

int n;
int *a;
int *buff;

double milsec;
time_t start, end;

FILE *input_file;
FILE *output_file;

int main(int argc, char* argv[]){
int i;
char num[10]; //n은 1,000,000,000미만.

input_file = fopen(argv[2],"r");
output_file = fopen(argv[3],"w");

if(input_file == NULL){;
printf("ERROR_InputFile\n");
return 0;
}//input_file이 존재하지 않으면 에러 출력.

fgets(num,sizeof(num),input_file);
n = atoi(num); //배열의 크기 N을 구함.
a = calloc(n,sizeof(int));

for(i=0;i<n;i++){
fscanf(input_file,"%d",&a[i]); //배열 a에 정렬되지 않은 수 받기.
}

//명령받기.
if(!strcmp(argv[1],"selection")) selection();
else if(!strcmp(argv[1],"insertion")) insertion();
else if(!strcmp(argv[1],"merge")){
buff = calloc(n,sizeof(int));
merge(0,n-1);
free(buff);
}
else if(!strcmp(argv[1],"quick")) quick(0,n-1);
else if(!strcmp(argv[1],"bubble")) bubble();
else printf("Wrong_SortInstruction");

//결과출력.
output(argv[3]);

//배열해제 및 파일닫기.
free(a);
fclose(input_file);
fclose(output_file);

return 0;
}

//선택정렬
void selection(void){
start = clock();
int i, j;
for(i=0;i<n-1;i++){
int min = i;
for(j=i+1;j<n;j++){
if(a[j]<a[min]){
min = j;
}
}
swap(int,a[i],a[min]);
}
end = clock();
}

//삽입정렬
void insertion(void){
start = clock();
int i,j;
for(i=1;i<n;i++){
int tmp = a[i];
for(j=i; j>0 && a[j-1]>tmp; j--){
a[j] = a[j-1];
}
a[j] = tmp;
}
end = clock();
}

//병합정렬
void merge(int left, int right){
start = clock();
if(left<right){
int i, j = 0, k = left, p = 0;
int center = (left + right) / 2;
merge(left,center);
merge(center+1,right);
for(i=left;i<=center;i++){
buff[p++] = a[i];
}
while(i<=right && j<p){
a[k++] = (buff[j]<=a[i]) ? buff[j++] : a[i++];
}
while(j<p){
a[k++] = buff[j++];
}
}
end = clock();
}

//퀵정렬
void quick(int left, int right){ //재귀적인 방식.
start = clock();
int pl = left;
int pr = right;
int x = a[(pl+pr)/2];
do{
while(a[pl] < x) pl++;
while(a[pr] > x) pr--;
if(pl <= pr){
swap(int,a[pl],a[pr]);
pl++;
pr--;
}
}while(pl <= pr);
if(left < pr) quick(left,pr);
if(pl < right) quick(pl,right);
end = clock();
}//비재귀적인 방법은 스택을 활용.

//버블정렬
void bubble(void){
start = clock();
int i = 0, j;
while(i<n-1){
int last = n-1; //가장 마지막으로 교환이 일어난 위치
for(j=n-1;j>i;j--){
if(a[j]<a[j-1]){
swap(int,a[j],a[j-1]);
last = j;
}
}
i = last;
}
end = clock();
}

//출력함수
void output(char* argv){
int i;
milsec = 1000.0 * (end-start) / CLOCKS_PER_SEC;
if(argv){
for(i=0;i<n;i++){
fprintf(output_file,"%d ",a[i]); //정렬된 배열 a 출력
}
fprintf(output_file,"\n");
fprintf(output_file,"elapsed_time = %.3f ms\n",milsec); //elapsed_time 출력
}
else{
for(i=0;i<n;i++){
printf("%d ",a[i]);
}
printf("\n");
printf("elapsed_time = %.3f ms\n",milsec);
}
}
//힘들어ㅠㅠ
= 기타 / 후기 / 방명록 =

-----------------------------------
[[새싹교실/2018/C알]]
[[새싹교실/2018]]

새싹교실/2018/C알/5월1일

2018-05-12T10:38:11Z

211.37.12.90:

새싹교실/2018/C알/5월1일

2018-05-12T10:37:45Z

211.37.12.90:

새싹교실/2018/C알/5월1일

2018-05-12T10:30:22Z

211.37.12.90:

정석우

2017-03-19T11:15:49Z

211.37.12.90:

'''코딩 못합니다 헤헤'''

== 이력 ==
* 충남삼성고등학교 정보보안동아리 AXEL 초대 부장, 2대 부장 역임
* 교육부 지정 공주대학교 정보보안 영재교육원 1기 전문1반 수료 (2014년)
* 2016년 충남 정보올림피아드 교육감 동상 수상 (전국이 아니라 죄송합니다 ㅠ)

== 소개 ==
* 현 중앙대학교 미식축구부 블루 드래곤즈 부원
* 충남삼성고등학교 미식축구부 삼성 라이온즈 부원
* 콕콕팡도 해요
* 개발경력은 거의 없습니닷

== 관심 분야 ==
* 정보보안 (리버스 엔지니어링, 칼리로 장난치기, 워게임 문제 풀기)
* 프로그래밍 대회!
* 자바를 배워서 안드로이드 앱 개발 하고 싶어요
* 주력 언어는 c

??? - [[박인서]]

정석우

2017-03-19T09:02:04Z

211.37.12.90: