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

2018-05-13T16:52:14Z

175.193.47.92:

__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);
}
}
//힘들어ㅠㅠ

* 승진 - python
def swap(x, i, j) :
x[i], x[j] = x[j], x[i]

def s_selection(x) :
for s in reversed(range(len(x))) :
max_i = 0;
for i in range(1, 1+s) :
if x[i] > x[max_i] :
max_i = i
swap(x, max_i, s)

def s_insertion(x) :
for s in range(1, len(x)) :
tmp = x[s]
i = s
while i > 0 and x[i-1] > tmp :
x[i] = x[i-1]
i -= 1
x[i] = tmp

def s_merge(x) :
if len(x) > 1 :
mid = len(x)//2
l_x, r_x = x[:mid], x[mid:]
s_merge(l_x)
s_merge(r_x)

l_i, r_i, i = 0, 0, 0
while l_i < len(l_x) and r_i < len(r_x) :
if l_x[l_i] < r_x[r_i] :
x[i] = l_x[l_i]
l_i += 1
else :
x[i] = r_x[r_i]
r_i += 1
i += 1
x[i:] = l_x[l_i:] if l_i != len(l_x) else r_x[r_i:]

def pivotFirst(x, lmark, rmark):
pivot_val = x[lmark]
pivot_idx = lmark
while lmark <= rmark:
while lmark <= rmark and x[lmark] <= pivot_val:
lmark += 1
while lmark <= rmark and x[rmark] >= pivot_val:
rmark -= 1
if lmark <= rmark:
swap(x, lmark, rmark)
lmark += 1
rmark -= 1
swap(x, pivot_idx, rmark)
return rmark
def s_quick(x, pivotMethod=pivotFirst):
def _qsort(x, first, last):
if first < last:
splitpoint = pivotMethod(x, first, last)
_qsort(x, first, splitpoint-1)
_qsort(x, splitpoint+1, last)
_qsort(x, 0, len(x)-1)

def s_bubble(x) :
for s in reversed(range(len(x))):
for i in range(s):
if x[i] > x[i+1]:
swap(x, i, i+1)

import sys
import timeit

if __name__ == "__main__" :
try :
input_file = open(sys.argv[2], 'r')
except FileNotFoundError as e :
print(str(e))
exit(0)

n = input_file.readline()
data = str(input_file.read()).split()
data = [int(i) for i in data]

option = sys.argv[1]
t_start = timeit.default_timer()
if 's' in option :
s_selection(data)
elif 'i' in option :
s_insertion(data)
elif 'm' in option :
s_merge(data)
elif 'q' in option :
s_quick(data)
elif 'b' in option :
s_bubble(data)
else :
s_bubble(data)
t_end = timeit.default_timer()

try :
tmp = sys.argv[3]
output_file = open(tmp, 'w')
except :
output_file = open("o_"+sys.argv[2], 'w')

for d in data :
output_file.write(str(d) + ' ')
output_file.write("\n");
output_file.write("%s" % (t_end - t_start))

input_file.close()
output_file.close()
= 기타 / 후기 / 방명록 =

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

새싹교실/2018/C알/4월2일

2018-04-09T11:36:48Z

175.193.47.92:

__TOC__
= 예정 =
* 포인터(pointer)
** 포인터 타입, 다중 포인터, 포인터 연산, void*
** pointer as parameter
** 배열 타입(recall)
** 배열과 포인터의 관계
** pointer to arrays, array of pointers
** 프로그램 인자(argument) : int argc, char *argv[]
* 동적 메모리 할당(dynamic allocation)
** 프로세스 구조
** void* malloc(size_t)
** void free(void*)
** calloc, realloc
* 문자열
** C에서의 문자열 : null-terminated string
** string.h
** strlen, strcmp, strchr, strstr, strcpy, strcat, strtok
** sscanf, sprintf
* 함수 포인터
** void qsort(void*, void*, size_t, int(*)(void*, void*))

* 실습
** simpleformatter : 간단한 문자열 처리
simpleformatter <option> <string>
<option>
: {{{
-r : 문자열 뒤집기
-u : 소문자를 대문자로
-l : 대문자를 소문자로
-a : 알파벳만 남기기
-n : 숫자만 남기기
}}}
** 인자가 없을 경우 : 사용자 입력을 받아 처리
** '-'가 있는 경우와 없는 경우 '''모두''' 처리해야함
** 옵션만 있으면, 문자열만 입력 받을것

= 진행 =
* 과제 : 오늘의 실습을 python으로 구현 (3 추천)
= 실습 =

* 과제_승진
import sys
import re

try :
option = sys.argv[1]
s_data = str(sys.argv[2])
except :
option = input()
s_data = input()

if option == '-r' :
print(s_data[::-1])
elif option == '-u' :
print(s_data.upper())
elif option == '-l' :
print(s_data.lower())
elif option == '-a' :
print("".join(re.findall(r'^|[a-zA-Z]', s_data)))
elif option == '-n' :
print("".join(re.findall('\d+', s_data)))
= 기타 / 후기 / 방명록 =
* 앗 오늘은 4월3일이잖아 - [[성훈|멍청한 튜터]]
-----------------------------------
[[새싹교실/2018/C알]]
[[새싹교실/2018]]

ZeroWiki - User contributions [en]

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

새싹교실/2018/C알/4월2일