이코의 세상 Season 1

/*
Data Structure Assignment #3
Spring, 2006
Due Date: 2006. 5. 8. Monday 6:00 PM.

주어진 input sequence에 대하여 heap을 구성하여 array에 저장하고 이를 in-order(type 1), pre-order(type 2), post-order(type 3), level-order(type 4)로 저장하는 프로그램을 작성 하시오. 속도에 따라 점수가 부여된다. 따라서, heap은 array에 저장되어야 하고 traversal은 iterative한 방법을 사용해야 한다 (recursive한 프로그램은 0점 처리).

예:
? Input:
10 // number of item
2 // traversal type
1 3 20 61 91 123 8 71 32 21 // items

30
1
30 40 13 12 11 .....

:
:

-1 // end of input

첫 번째 input으로부터의 max heap은 다음과 같다.

   123
          /   /    \
71   /   91
     /      /
61  21  3  8
  /       /       \
  1    32    20

123719161213813220

? Output:
123 71 61 1 32 21 20 91 3 8 // preorder traversal (because traversal type = 2)
123 71 61 1 32 21 20 91 3 8
0.034 // 수행속도 (입출력 시간 제외, 소수점 3자리)

40 30 13 12 11 ....
0.040

.
제한 사항
1. Input item의 개수는 최대 100000개입니다.

2. Input은 C:\ass3_input.txt에서 입력 받아서 C:\학번_이름_반.txt에 출력하면 된다.
예)출력 파일 c:\200621094_홍길동_A.txt

3.제출시 파일명은 "학번_이름_반"으로 작성하세요. 여기서 반은 과제물 제출 게시판의 반입니다.(A,B,C) 실행 파일과  C파일 두 개를 올려주세요.
예) 200621094_홍길동_A.exe /200621094_홍길동_A.c

4.소스 파일과 실행 파일을 압축하지 말고 올려주세요.  

5. c:\ 폴더에 실행파일이 없을 경우에도 동작해야 합니다.

6.변동 사항이 있을 수 있으니 공지 사항을 꼭 확인해 주세요.

7.과제물 제출 시 반드시 비밀글을 체크하시고 올리셔야 합니다. 

*/
ac
#include<stdio.h>
#include<windows.h>

#define IN_FILE "c:\\ass3_input.txt"
#define OUT_FILE "c:\\200120993_이지황_B.txt"

struct time{
LARGE_INTEGER   st, ed, freq ;
  double          gap ;
  BOOL            bEnable;
  char            szName[256];
  UINT            counter;
  double          fTotal_Time;
}mytime;

struct dat{
int num; // number of input datas
int type;
int *heap, *temp, *out; 
}data;

void inorder(void) // when case 1,
{
int i=1, j=1;
for( ; i<=data.num/2; i*=2);
 
while(1)
{     
if(i == 1)
{
  data.out[j++] = data.heap[i];
  data.temp[i] = -1;
  for(i=i*2+1; i<=data.num/2; i*=2);
}
else
{
  if(i*2 <= data.num && data.temp[i*2] != -1)
  {
   data.out[j++] = data.heap[i*2];
   data.temp[i*2] = -1;
  }

  if(data.temp[i] != -1)
  {
   data.out[j++] = data.heap[i];
   data.temp[i] = -1;
  }
   
  if(i*2+1 <= data.num && data.temp[i*2+1]!= -1)
  {
   for(i=i*2+1; i<=data.num/2; i*=2);
   continue;
  }
  //printf("i:%d j:%d\n",i,j);
}
i/=2;
if(j>data.num) break;
}
}

void preorder(void) // when case 2,
{
int i=1, j=1;

while(1)
{
for( ; i<=data.num; i*=2)
{
  if(data.temp[i]!= -1)
  {
   data.out[j++]=data.heap[i];
   data.temp[i]= -1;
  }
}
if(i/2-1>=data.num)
{
  i=i/2+1;
  data.out[j++]=data.heap[i];
  data.temp[i]= -1;
}

i=i/2+1;

if(i%2==0)
{
  while(i%2==0)
  i=i/2;
}
if(j>data.num)
  break;
}

}

void postorder(void) // when case 3,
{
int i=1, j=1;  
for( ; i<=data.num/2; i*=2);
 
while(1)
{     
if(data.temp[i]!= -1)
{
  data.out[j++]=data.heap[i];
  data.temp[i]=-1;
}

if(i+1<=data.num && data.temp[i+1]!= -1 && (i+1)%2==1) 
{
  i++;
  if(i*2<=data.num)
  {
   for( ; i<=data.num/2; i*=2);
   continue;
  }
  data.out[j++] = data.heap[i];
  data.temp[i]= -1;
}

i/=2;
if(j > data.num) break;
}
}

static void Start()
{
mytime.gap = 0.0;  // init
mytime.bEnable = FALSE;
mytime.counter = 0;
mytime.fTotal_Time = 0.0;

// system test
QueryPerformanceCounter ( &mytime.st ) ;
if ( mytime.st.QuadPart == 0 )
{
mytime.bEnable= FALSE;
OutputDebugString("시스템이 지원이 안됨,,, 사용할 수 없음[CTimeCounter Class]\n");
}

// start()
mytime.counter ++;
QueryPerformanceCounter ( &mytime.st ) ;
}

static void End()
{
char szMsg[64];

QueryPerformanceCounter ( &mytime.ed ) ;
QueryPerformanceFrequency ( &mytime.freq ) ;

// 소요 시간 계산
mytime.gap = ( (double) (mytime.ed.QuadPart - mytime.st.QuadPart )) / ( (double) mytime.freq.QuadPart ) ;
mytime.fTotal_Time += mytime.gap;

sprintf ( szMsg, "수행시간 %.6f초\n", mytime.gap) ;
OutputDebugString(szMsg);
}

int read(FILE *in_file)
{
int i;
fscanf(in_file,"%d",&data.num);
if(data.num== -1) return 0;
else
{
data.heap=(int*)malloc(sizeof(int)*(data.num+1)); // memory allocation
data.temp=(int*)malloc(sizeof(int)*(data.num+1));
data.out= (int*)malloc(sizeof(int)*(data.num+1));

fscanf(in_file,"%d",&data.type);

for(i=1; i<=data.num; i++)
{
  fscanf(in_file,"%d",&data.temp[i]);
}
}
return 1;
}

void sort(FILE *out_file)
{
int i,j,tmp;
int flaglevelorder=0;

Start(); // clock starts

// max heap insertion occurs here.
for(i=1; i<=data.num; i++)
{
data.heap[i]=data.temp[i];
for(j=i; j>1; j/=2)
{
  if(data.heap[j]<data.heap[j/2]) break;
  else
  {
   tmp=data.heap[j/2];
   data.heap[j/2]=data.heap[j];
   data.heap[j]=tmp;
  }
}
}

switch(data.type)
{
case 1:
inorder();
break;
case 2:
preorder();
break;
case 3:
postorder();
break;
case 4: //level-order
flaglevelorder=1;
//for(i=1; i<=data.num; i++) data.out[i]=data.heap[i];
break;
}

End(); // clock stops

if(flaglevelorder)
{
for(i=1;i<=data.num;i++) fprintf(out_file, "%d ", data.heap[i]);
}
else
{
for(i=1;i<=data.num;i++) fprintf(out_file, "%d ", data.out[i]);
}

fprintf(out_file,"\n%5.3f\n\n", mytime.fTotal_Time);

free(data.heap); // unallocation of memory
free(data.temp);
free(data.out);
}

void main(void)
{
FILE *infile, *outfile;

infile=fopen(IN_FILE,"r");
outfile=fopen(OUT_FILE,"w");

while(read(infile)) sort(outfile);

fclose(infile);
fclose(outfile);
}

/*
자료구조 - 2번째 과제물.
제출 기한 : 2006. 3. 31. Friday 6:00 PM.

주어진 숫자를 radix sort algorithm (pp. 350-357) 을 이용하여 정렬하라.

예 (radix 가 10일 경우):

329        720        720        329
457        355        329        355
657        436        436        436
839  ->    457   ->   839   ->   457
436        657        355        657
720        329        457        720
355        839        657        839

Input 양식:
5                // input 개수
10329353
2340213
234091223
2342321
2341323

Output 양식:
2340213
2341323
2342321
10329353
234091223

조건:
1. 각 숫자는 최대 9자리이다.
2. Input은 C:ass2_input.txt에서 입력 받아서 C:ass2_output.txt에 출력하면 된다.
3. 제출시 파일명은 "학번_이름_반"으로 작성하세요. 여기서 반은 과제물 제출 게시판의 반입니다.(A,B,C)
  예) 200621094_홍길동_A.exe /200621094_홍길동_A.c
4. 소스 파일과 실행 파일모두 제출 하셔야 합니다.  
5. input 개수에 상관없이 작동해야 합니다. 단 integer범위를 벗어나진 않습니다.
6. c: 폴더에 실행파일이 없을 경우에도 동작해야 합니다.
7. Radix_Size에 변동 사항이 있을 경우 공지사항에 다시 올리겠습니다.
8. 공지 사항을 꼭 확인해 주세요.
*/

#include <stdlib.h>  // to use function: atoi()
#include <string.h>  // to reset buffer: memset()
#include <windows.h> // for class CTimeCouter
#include <stdio.h>  // for class CTimeCouter

#define IN_FILE "c:\\ass2_input.txt"
#define OUT_FILE "c:\\ass2_output.txt"

// global variables here
struct data{
int* list;      // input data enters here
int* temp;  // mydata.temporary data to exchange
int num_in;    // number of inputs
}mydata;

struct time{
LARGE_INTEGER   st, ed, freq ;
   double          gap ;
   BOOL            bEnable;
   char            szName[256];
   UINT            counter;
   double          fTotal_Time;
}mytime;

static void Start()
{
mytime.gap = 0.0;         // init
mytime.bEnable = FALSE;
mytime.counter = 0;
mytime.fTotal_Time = 0.0;

// system test
QueryPerformanceCounter ( &mytime.st ) ;
if ( mytime.st.QuadPart == 0 )
{
 mytime.bEnable= FALSE;
 OutputDebugString("시스템이 지원이 안됨,,, 사용할 수 없음[CTimeCounter Class]\n");
}

// start()
mytime.counter ++;
QueryPerformanceCounter ( &mytime.st ) ;
}

static void End()
{
char szMsg[64];

QueryPerformanceCounter ( &mytime.ed ) ;
QueryPerformanceFrequency ( &mytime.freq ) ;

// 소요 시간 계산
mytime.gap = ( (double) (mytime.ed.QuadPart - mytime.st.QuadPart )) / ( (double) mytime.freq.QuadPart ) ;
mytime.fTotal_Time += mytime.gap;

sprintf ( szMsg, "수행시간 %.6f초\n", mytime.gap) ;
OutputDebugString(szMsg);
}

int read(FILE * in_file)
{
char tmpr[10]="";
int i;

fscanf(in_file,"%s",&tmpr);
if (atoi(tmpr)==0) return 0; // break if input is zero
else
{
 mydata.num_in=atoi(tmpr)+1;

 mydata.list = (int*)malloc(sizeof(int)*mydata.num_in); // memory allocation as size of mydata.num_in, and link this to mydata.list
 mydata.temp = (int*)malloc(sizeof(int)*mydata.num_in); // memory allocation as size of mydata.num_in, and link this to mydata.temp

 for(i=1; i<mydata.num_in; i++)
 {
  fscanf(in_file,"%s",&tmpr);
  mydata.list[i] = atoi(tmpr);
 }
}
return 1;
}

static void sort(FILE* out_file)
{
int cnt[256], idx[256], i;

Start(); // start stopwatch

memset(cnt, 0, 1024); // initializing count
idx[0]=0; // initializing index
for(i=0; i<mydata.num_in; i++)   cnt[(mydata.list[i] >> 0) & 255]++;
for(i=1; i<256; i++)   idx[i] = idx[i-1] + cnt[i-1];
for(i=0; i<mydata.num_in; i++)   mydata.temp[idx[(mydata.list[i] >> 0) & 255]++] = mydata.list[i];

memset(cnt, 0, 1024); // initializing count
idx[0]=0; // initializing index
for(i=0; i<mydata.num_in; i++)   cnt[(mydata.temp[i] >> 8) & (255)]++;
 for(i=1; i<256; i++)   idx[i] = idx[i-1] + cnt[i-1];
for(i=0; i<mydata.num_in; i++)   mydata.list[idx[(mydata.temp[i] >> 8) & 255]++] = mydata.temp[i];

memset(cnt, 0, 1024); // initializing count
idx[0]=0; // initializing index
for(i=0; i<mydata.num_in; i++)   cnt[(mydata.list[i] >> 16) & (255)]++;
for(i=1; i<256; i++)   idx[i] = idx[i-1] + cnt[i-1];
for(i=0; i<mydata.num_in; i++)   mydata.temp[idx[(mydata.list[i] >> 16) & 255]++] = mydata.list[i];

memset(cnt, 0, 1024); // initializing count
idx[0]=0; // initializing index
for(i=0; i<mydata.num_in; i++)   cnt[(mydata.temp[i] >> 24) & (255)]++;
for(i=1; i<256; i++)   idx[i] = idx[i-1] + cnt[i-1];
for(i=0; i<mydata.num_in; i++)   mydata.list[idx[(mydata.temp[i] >> 24) & 255]++] = mydata.temp[i];

End();  // stop stopwatch

fprintf(out_file,"%.10f\n", mytime.fTotal_Time);
for(i=0; i<mydata.num_in-1;i++) fprintf(out_file,"%d ", mydata.list[i]);
fprintf(out_file,"\n");
}

void main(void)
{
   FILE *in_file, *out_file;

in_file=fopen(IN_FILE,"r");
out_file=fopen(OUT_FILE,"w");

while(read(in_file)) sort(out_file);

fclose(in_file);
fclose(out_file);

free(mydata.list);
free(mydata.temp);
}

/*/////////////////////////////////
Data Structure Assignment #1

과제1:
Operand의 크기가 너무커서 integer type으로 처리하지 못하는 더하기 연산을 integer 덧셈처럼 처리하는 프로그램을 작성하시오.

채점에 사용될 양식
예)
input.txt

21123424543254546575767868
+4235465475678687979797

2335344365547657
-345463574687

25434665457655765879
+4547568798080980

3543454
-46576985679

..
..
..
EOF

output.txt
325243436576970808976

3655765876987908606080

654768780900897979799
..
..
..

답 생성시 음수는 숫자앞에 '-'기호를 붙이셔야 됩니다.
위의 방식으로 하겠습니다.

값 사이의 줄 공백은 input 파일에서는 처리하셔야 되고
처리가 안되어 있다면 '순서대로 2줄을 읽어들여' 처리하는 식으로 되어 있으면 됩니다.

output파일에서의 공백은 처리 안하셨어도 됩니다.
*/

#include <fstream.h> // includes iostream.h
#include <string.h>  // for strcmp()

#define IN_FILE "C:\\input.txt" // don't forget to use double '\\' instead of '\'
#define OUT_FILE "C:\\output.txt"
#define MAX_LEN 200 // up to 200 chars (w/ cr & sign, +1)
#define POSITIVE 0
#define NEGATIVE 1

void mysort(char *mychar) // clear out spaces;
{
int j=0;
char temp[MAX_LEN]=""; // clearing garbages out (will temporary store cleared *mychar values)
for (int i=0;i<=MAX_LEN+1;i++)
{
 if (mychar[i]!=' ') temp[j++]=mychar[i]; // if the character is not a blank, than save to the temp.
}
strcpy(mychar, temp); // overwrite strings with 'blank removed' ones.
} 

int signcheck_rmv(char *mychar) // check sign and return 1 if it's negative, else 0.
{
int ret_key=0;
for (int i=0;i<=MAX_LEN+1;i++)
{
 switch(mychar[i])
 {
 case '-':
  ret_key=1;     // if it's negative turn the flag on.
 case '+':
  mychar[i]=' '; // and then change the sign symbol to a blank.
  break;
 }
}
mysort(mychar); // call sort function to remove spaces

return ret_key; // return 1 if it's negative, otherwise 0
}

void remove_zeros(char* output) // remove front zeros, ej) 001023 -> 1023
{
char temp[MAX_LEN]="";
strcpy(temp,output);

for (int i=0;(unsigned)i<strlen(temp);i++) {
 if(temp[i]>='1') break;
 else temp[i]=' ';
}
mysort(temp);

if (strcmp(temp,"")==0) strcpy(temp,"0"); // leave one '0', if output is null.
strcpy(output,temp);
}

inline int bigger(int a, int b){ if(a>b) return a; else return b; }  // return bigger integer, else return first input.

void reform(char *mychar, int len) //digit count and modify 11 as 0011 to fit for 2222
{
int j=len-strlen(mychar); //+1 is for case of increase of number over 10
if (strlen(mychar)==(unsigned)len) {} //skip if strlen(mychar) is equal to itself.
else {
 while(j--) {
  for (int i=len; i>=0; i--) //repeat as length of mychar.
  {
   if(i<=0) mychar[i]='0'; // put '0' to mychar[i] if [i] is 0.
   else mychar[i]=mychar[i-1]; //otherwise
  }
 }
}
}

void calculate_plus(char* a, char* b, char *output, int last) // calculate and saves value to *output
{
int c=0;
int inta, intb;

char temp[MAX_LEN]="";

// digit count and modify 11 as 0011 to fit for 2222
reform(a, last);
reform(b, last);
reform(temp, last);

for (int i=1;i<=last;i++)
{
 inta=a[last-i]-'0';
 intb=b[last-i]-'0'; // converts a character to an integer
 //cout<<"inta+intb:"<<inta+intb<<endl;

 temp[last-i]=(((inta+intb)%10)+c)+'0'; // perform plus calculation

 if((inta+intb)/10) // if a+b is over 10, then we need to
 {
  c=1;    // set flag to 1 which says the output is more than 10.
  if(i==last) // in case the output have more digit than input, like 999+999.
  {
   reform(temp,strlen(temp)+1); // increase one more digit
   temp[0]='1';                 // then put 1 in front.
  }
 }
 else c=0; // otherwise reset the flag
}

remove_zeros(temp);
strcpy(output,temp); // copy temp to output
}

void calculate_minus(char* a, char* b, char *output, int last) // calculate and saves value to *output
{
int inta=0, intb=0, c=0;
char temp[MAX_LEN]="";
char my_a[MAX_LEN]="";
char my_b[MAX_LEN]="";

strcpy(my_a,a);
strcpy(my_b,b);

// count digit and modify 11 as 0011 to fit for 2222
reform(temp, last);
reform(my_a, last);
reform(my_b, last);

for (int i=1;i<=last;i++)
{
 if((my_a[last-i]-'0')==0) inta=0;
 else inta=(my_a[last-i]-'0');
 if((my_b[last-i]-'0')==0) intb=0;
 else intb=(my_b[last-i]-'0'); // converts a character to an integer

 if(inta-intb-c>=0)
 {
  temp[last-i]=(((inta-intb)%10)-c)+'0'; // perform minus calculation
  c=0;
 }
 else //if(inta-intb-c<0)
 {
  temp[last-i]=(inta-intb-c+10)+'0';
  c=1;
 }
}
remove_zeros(temp);
strcpy(output, temp);
}

int calculate(char *a, char *b, char *output, int a_is_neg, int b_is_neg) //(unsigned)bigger number comes to a, return 1 when the answer is MINUS.
{
char temp[MAX_LEN]="";
int type_a=0, type_b=0, i;
int len_a=strlen(a);
int len_b=strlen(b);
int last=bigger(len_a,len_b);

int a_size=1, b_size=1;

if(len_a==len_b) // assume that we have same length, because we already reform(a)&(b)
{
 for (i=0;i<=last;i++) // compare one by one
 {
  if(a[i]>b[i]) a_size*=(i+1); // +1 to prevent result is 0,  when i==0;
  if(b[i]>a[i]) b_size*=(i+1);
 }
 //cout<<"a_size: "<<a_size<<endl<<"b_size: "<<b_size<<endl;
 if(a_size>b_size)
 {
  if(a_is_neg) {calculate_minus(a,b,output,last); return NEGATIVE;} // when a_is_big and a_is_neg, output must be NEGATIVE
  if(b_is_neg) {calculate_minus(a,b,output,last); return POSITIVE;}
  calculate_plus(a,b,output,last); return POSITIVE;
 }
 if(b_size>a_size) //switch between (a,b) is occuring here.
 {
  if(b_is_neg) {calculate_plus(b,a,output,last); return NEGATIVE;} // when b_is_big and b_is_neg, output must be NEGATIVE
  if(a_is_neg) {calculate_plus(b,a,output,last); return POSITIVE;}
  calculate_plus(a,b,output,last); return POSITIVE;
 }
 calculate_plus(a,b,output,last); return POSITIVE;
}

int LONG=1;  //define as variable because we have to change later..
int SHORT=0;
//negative=1
//positive=0

if (len_a>len_b) { type_a=LONG; type_b=SHORT; }
if (len_b>len_a) { type_b=LONG; type_a=SHORT; }
if (a_is_neg) type_a+=NEGATIVE; else type_a+=POSITIVE;
if (b_is_neg) type_b+=NEGATIVE; else type_a+=POSITIVE;

// long-  type_x=2,
// long+  type_x=1,
// short- type_x=1,
// short+ type_x=0.

// first determine two definite situation.
// long+a(1) - short-b(1) = 0 // minus_calc, return POSITIVE
// long+a(1) - short+b(0) = 1 // plus_calc, return POSITIVE
// long-a(2) - short-b(1) = 1 // plus_calc, return NEGATIVE
// long-a(2) - short+b(0) = 2 // minus_calc, return NEGATIVE
// short+a(0) - long-b(2) = -2 // switch, minus_calc, return NEGATIVE
// short+a(0) - long+b(1) = -1 // plus_calc, return POSITIVE
// short-a(1) - long-b(2) = -1 // plus_calc, return NEGATIVE
// short-a(1) - long+b(1) = 0 // switch, minus_calc, return NEGATIVE

// now arranging by output, we can see top 2 has distinctive output.

// long-a(2) - short+b(0) = 2 // minus_calc, return NEGATIVE
// short+a(0) - long-b(2) = -2 // switch, minus_calc, return NEGATIVE

// long+a(1) - short-b(1) = 0 // minus_calc, return POSITIVE
// short-a(1) - long+b(1) = 0 // switch, minus_calc, return NEGATIVE
// long+a(1) - short+b(0) = 1 // plus_calc, return POSITIVE
// long-a(2) - short-b(1) = 1 // plus_calc, return NEGATIVE
// short+a(0) - long+b(1) = -1 // plus_calc, return POSITIVE
// short-a(1) - long-b(2) = -1 // plus_calc, return NEGATIVE

// so we can write:
if ( (type_a-type_b) == 2 ) { calculate_minus(a,b,output,last); return NEGATIVE; }
else if ( (type_a-type_b) == -2 ) { calculate_minus(b,a,output,last); return NEGATIVE; }

// now we have 6 conditions left, so we change the calculation from a-b to a+b.
// then we'll have two distinctive output from them.

// long+a(1) + short-b(1) = 2 // minus_calc, return POSITIVE
// short-a(1) + long+b(1) = 0 // switch, minus_calc, return NEGATIVE

// long+a(1) + short+b(0) = 1 // plus_calc, return POSITIVE
// long-a(2) + short-b(1) = 3 // plus_calc, return NEGATIVE
// short+a(0) + long+b(1) = 1 // plus_calc, return POSITIVE
// short-a(1) + long-b(2) = 3 // plus_calc, return NEGATIVE

// so we can write:
else if ( (type_a+type_b) == 2 ) { calculate_minus(a,b,output,last); return POSITIVE; }
else if ( (type_a+type_b) == 0 ) { calculate_minus(b,a,output,last); return NEGATIVE; }

// now we have 4 conditions left, so we change the definition of long
// now change the def of long.
else{
 LONG=10;
 type_a=type_b=0; //reset type_a and type_b

 // recalculate then.
 if (len_a>len_b) { type_a=LONG; type_b=SHORT; }
 if (len_b>len_a) { type_b=LONG; type_a=SHORT; }
 if (a_is_neg) type_a+=NEGATIVE; else type_a+=POSITIVE;
 if (b_is_neg) type_b+=NEGATIVE; else type_a+=POSITIVE;

 // LONG=10
 // SHORT=0
 // NEGATIVE=1
 // POSITIVE=0
 
 // which makes
 // long-  type_x=11,
 // long+  type_x=10,
 // short- type_x=1,
 // short+ type_x=0.

 // we perform the plus calculations to determine next top two.
 // long+a(10) + short+b(0) = 10 // plus_calc, return POSITIVE
 // short+a(0) + long+b(10) = 10 // plus_calc, return POSITIVE
 
 // long-a(11) + short-b(1) = 12 // plus_calc, return NEGATIVE
 // short-a(1) + long-b(11) = 12 // plus_calc, return NEGATIVE

 // so we now can write:
 if ((type_a+type_b) == 10) { calculate_plus(a,b,output,last); return POSITIVE; }
 else { calculate_plus(a,b,output,last); return NEGATIVE; }
}

return POSITIVE; // return positive if the answer is 0 situation(a=b) like (111-111)=0
}

void main(void)
{
char a[MAX_LEN]="";
char b[MAX_LEN]="";
char output[MAX_LEN]="";  // clearing out garbages

// opening files...
ifstream input_file(IN_FILE); //open file to read
ofstream output_file(OUT_FILE); //open file to write
if(input_file.fail()) //input file check
 cerr << "Error opening "<<IN_FILE<<endl;
else if(output_file.fail()) //output file check
 cerr << "Error opening "<<OUT_FILE<<endl;
else
{
 while (! input_file.eof()) //loop starts to get lines, stops end of the file.
 {
  strcpy(output,""); // just in case if the line have odd number
  //read file by line
  input_file.getline(a, sizeof(a)); //get a line, when repeats get the next odd line
  input_file.getline(b, sizeof(b)); //get a next line, when repeats get the next even line
  if (strcmp(a,"EOF")==0 || strcmp(b,"EOF")==0) break; // break out loop when meets "EOF" string, no matter if there's more to read.
   // so, really doesn't matter either line number is on even, or odd.

  //calculation
  //remove the sign
  int is_a_neg=signcheck_rmv(a);
  int is_b_neg=signcheck_rmv(b);

  switch(calculate(a, b, output, is_a_neg, is_b_neg)) // check out whether output positive calculation or negative.
  {
  case NEGATIVE:
   reform(output,strlen(output)+1);
   output[0]='-';
  case POSITIVE:
   break;
  }

  //cout<<"a: "<<a<<endl<<"b: "<<b<<endl<<"o: "<<output<<endl;  // just for testing purpose.
  output_file<<output<<endl; // write a line to output file.
 }//end of eof checking loop
}//end of input file error checking

// closing files...
input_file.close();
output_file.close();
} //end of main(void)*/

아는 서버를 뚫어봤다.

신가하게도 잘 들어가진다.

보안상의 문제로 이것저것 세팅을 해놓은줄 알았는데

일부러 열어 놓은것인지 아니면 그냥 생각이 없던것인지는 모르겠으나

하여튼 나는 일이 쉽게 된다고 생각했다.

처음에는 wget으로 파일의 이름을 잘 맞춰서 data 디렉토리에 접근하면 된다고 생각했는데

(어짜피 permission이 707이니깐) 그런데 일이 생각지도 않은 apache부분에서 쉽게 풀려버렸다.

어째서 이 옵션은 기본적으로 enabled되어있는것인데 이걸 생각을 못했을까 하는 생각도 들고

설마 나같은 사람이 있을꺼란 생각을 못했겠지 라는 생각도 들고...

아무튼 이 포스팅은 일단 secret.

[Secret]
Q:내가 해킹한 서버는 어디일까요??
A:자료구조

프로그래밍 과제를 올리는 곳인데...

뚫린다... 오오... 신가하다...

아니... 조교는 이런것도 안막아놓고 뭐했대?

얘기해서 프로그램 안짜고 10점만점 달라고 할까... 보안상 문제되는곳은 막아주겠다고 하면서-ㅋ

하지만.. 프로그래밍 과제도 몇개 안남았다..;;

그럼.. 이 포스팅은 어느정도 날짜가 지나야 공개가 되야하는군...

그렇다면 깔끔하게 7월 1일... 모든 기말고사와 채점이 다 끝난 이후로군... 후후..

[/secret]

학교에서 자료구조 수업을 듣는데, 벌써 2번째 과제가 나왔다.

첫번째 과제는 개강 첫날 수업을 듣자마자 대뜸 내주시던 교수님...

생각했던대로 쉬웠던것은 아니였다. 그리고 결과는 참담;;;


이번에는 반드시 제대로 만들리라 하고 다짐했는데,

이번과제는 radix소트를 하는 프로그램이다.

아아.. 이런... 냅다 만들어서 테스트를 하려는데 entry를 쉽게쉽게

만들기 귀찮아서 그냥 프로그램으로 해결...;

갯수를 지정할수도 있고, random인지, 거꾸로 정렬된것인지, 제대로 정렬된것인지

모두 고를수있다!

음하하하!

invalid-file

3/27 추가포스팅: 몇몇 버그가 있어서 소스코드와 함께 다시 올린다.
변경된 사항은 코멘트가 몇가지 추가된것, 9자리 숫자가 나와야하는데 10자리가 나오는 버그, output을 check하는 프로그램이다.

닫기

 

// I know this is just brute force, not fully tested,
// but it's fit to purpose.
// it's free to change, modify, rebuild, compile this source code, but DO NOT REDISTRIBUTE!
// thanks for using my program, HAPPY PROGRAMMING!
// for more information, please visit: http://jihwang.org

#include <fstream.h> // for file i/o, includes iostream.h
#include <stdlib.h>  // for srand() rand()
#include <time.h>  // for time()
#include <conio.h>  // for getch()
#include <iomanip.h> // for setw()

#define MAX_LEN 12 // used for checker(), usually need required digit+3(\n, etc)

void checker(char* IN_FILE, int line_size)
{
char a[MAX_LEN]="";
char b[MAX_LEN]="";
char output[MAX_LEN]="";  // clearing out garbages
int inta, intb, init_i=3, i=init_i;

// opening files...
ifstream input_file(IN_FILE); //open file to read
if(input_file.fail()) //input file check
cerr << "Error opening "<<IN_FILE<<endl;
else
{
input_file.getline(a, sizeof(a)); //just read first two line, it's just file header. so we can ignore this part of the file.
input_file.getline(a, sizeof(a));
input_file.getline(a, sizeof(a)); //get a line, when repeats get the next odd line
inta=atoi(a);

while (! input_file.eof()) //loop starts to get lines, stops end of the file.
{
  if (line_size+init_i<=i) break;
  //read file by line
  input_file.getline(b, sizeof(b)); //get a line, when repeats get the next odd line

  //int conversion
  intb=atoi(b);
 
  //compare
  if(inta>intb) cout<<"The output is not ordered at line number "<<i<<"."<<endl;
  i++;
  inta=intb;
}
}
input_file.close();
}

void main(void)
{
char max_size_c[11]="";
int max_size=1000000, my_sw=3;
char* filename="c:\\ass2_input.txt";
char* filename_in="c:\\ass2_output.txt";

int temporary;

cout<<"--- 9-digit NUMBER Generator & Checker ---  by ikko"<<endl;
cout<<"for full source code please visit at http://jihwang.org"<<endl<<endl;
cout<<"Enter number of entry (max: range of int): ";
cin.get(max_size_c, 11);
cin.ignore(1,'\n');
max_size=atoi(max_size_c);
cout<<"for "<<max_size<<" entries..."<<endl;

cout<<endl<<"1. Ascendent order"<<endl<<"2. Descendent order"<<endl<<"3. Random order(default)"<<endl<<"4. Check output if it's ordered(new)"<<endl;
cout<<"choose order: "<<endl;
my_sw=getch();
cout<<endl<<endl;

ofstream output_file(filename);
if(output_file.fail()) cerr <<"Error opening "<<filename<<endl; else 
{

output_file<<max_size<<endl;

switch(my_sw)  {
case 49:
  cout<<"generating ASCENDENT number to "<<filename<<"..."<<endl;
  break;
case 50:
  cout<<"generating DESCENDENT number to "<<filename<<"..."<<endl;
  break;
case 52:
  cout<<"checking order of "<<filename_in<<"..."<<endl;
  checker(filename_in, max_size);
  break;
case 51:
default:
  cout<<"generating RANDOM number to "<<filename<<"..."<<endl;
  srand(time(NULL));  
  break;
}

for (int i=0;i<=max_size-1;)
{
  switch(my_sw)   {
  case 49:
   output_file<<i++<<endl;
   break;
  case 50:
  case 52:
   break;
  case 51:
  default:
   temporary=rand()*rand();
   if (temporary>=1000000000) temporary=temporary/10;
   output_file<<temporary<<endl;
   i++;
   break;
  }
  if (my_sw==50||my_sw==52) break;
}
if (my_sw==50) for (i=max_size-1;i>=0;i--)  output_file<<i<<endl;
}
output_file.close();

cout<<endl<<"------------ PROCESS COMPLETED! ------------"<<endl<<endl;
}

invalid-file

소스 다운받기

닫기

invalid-file

(최종버전이길 기대하면서;;)