1-1 1-2 1-3 1-4 1-5 1-6 1-7 1-8
1-1-1 C int main(void){ int x,y,z; int sum=0; double avg=0.0; scanf("%d",&x) ; scanf("%d",&y) ; scanf("%d",&z) ; sum=x+y+z ; avg=sum/3.0; printf("%f\n",avg); system("pause"); 2
return 0; int main(void){ int student[3]; int sum=0, n=0, i; double avg=0.0; do{ scanf("%d",&student[n]) ; n++ ; while(n<3); for(i=0 ;i<3 ;i++) sum=sum+ student[i]; avg=sum/3.0; printf("%f\n",avg); system("pause"); return 0 ; 3 scanf while for (Data Structure) 3
ABC 1-1-2 1. (static data structure) 2. (dynamic data structure) 4
88 1-2-1 1-2-2 5
1-2-3 1. 2. 3. 1. 2. (1) (2) (3) (4) 3. 1. 2. 3. 4. 5 1. 1. 2. (a) (b) (c) (d) (1) (2) (3) (4) (1) (2) (3) (1)(2) (3) (4)(5) (6) (7)B tree (8)2-3 (9)2-3-4(10) (11)M(12) (13)B+ 1. 2. 6
1. 2. 1. 2. 1. 2. (DFS BFS) 1.2.3. 4.5.6. 7. 1.2.3.4. 5. 1-3-1 = + 1-3-2 7
1-3-3 (Virtual Memory) (Secondary Memory) 1-4-1 1. 1 n1 n int sum(int a[], int n) { int i; 1 1 1 8
for(i=0; i<n; i++) 1 n+1 n/2+1 { if(a[i]= =9) 1 n n/2 break; 1 1 1 printf( %d\n,i); 1 1 1 5 2n+4 n+4 2. (Worse Case) (Best Case) (Average Case) 1. int sum(int n) { int i=0, ttl=0; while(i<=n) { ttl+=i; i++; return ttl; 2. n (TOEIC) 9
1. int sum(int n) { int i=1, ttl=0; 1 while(i<=n) n+1 { ttl+=i; n i++; n return ttl; 1 3n+3 3n+3 2. int ttlscore(int score[], int n) { int i, ttl=0; 1 for(i=0;i<n,i++) n+1 { ttl+= score[i]; n return ttl; 1 3n+3 3n+3 10
(1~n) 1-4-2 1000n+3 n 2 +4 n (1) 1000n+3 (2) n 2 +4 (1) (2) 1 1003 5 998 10 10003 104 9899 100 100003 10004 89999 1000 1000003 1000004-1 10000 10000003 100000004-90000001 100000 100000003 10000000004-9900000001 n 1~100 n1000 f(n) c n 0 n n 0 n n 0 f(n) cg(n)f(n) g(n) g(n) g(n) f(n) f(n)=o(g(n)) g(n) 11
1. T(n)=1001n+5 2. x++ i=1 while(i<=n){ for(j=i ;j<=n ;j++) x++ ; i++ 3. T(n)= i n i=1 4. y-- y-- ; 1. O(n) T(n)=1001n+5 1001n+n T(n) 1002n c=1002 n 0 T(n) 1002n f(n) cg(n)f(n)=o(g(n))t(n)=o(n) T(n)O(n) 2. O(n 2 ) i j=1~n x++ 1 1~n n 2 2~n n 1... n 2 n n~n 1 (1+n)*n/2 (1+n)*n/2= n/2+n 2 /2 T(n)=n 2 /2+ n/2 n 2 T(n) n 2 c=1 n 0 =0n n 0 T(n) n 2 12
f(n) cg(n)f(n)=o(g(n))t(n)= O(n 2 ) T(n)O(n 2 ) 3. O(n 2 ) n i=1 2 (1+n)*n n +n T(n)= i=1+2+...+n= = 2 2 T(n)O(n 2 ) 4. O(1) y-- y=y+1 1T(n)=1 T(n)O(1) 1-4-3 1. (Time Complexity) (Compile Time) (Execution Time) 2. O(n) Ω(n)Θ(n) (O(n)) 3. O(n) Big-Oh of nf(n)=o(g(n))c n 0 nn n 0 f(n) cg(n) f(n) n 0 f(n) cg(n) nc f(n) g(n)2 c n 0 f(n) cg(n) cg(n)f(n)cg(n) f(n) f(n)f(n)=o(g(n)) f(n) g(n) f(n) 3n+8 3n+n 4nf(n)=3n+8 4n=cg(n) c=4 g(n)=n 3n+8 4n n 0 n n 0 3n+8 4nf(n)=3n+8g(n)=n 3n+8 4n 8 n n 0 =83n+8 4n f(n) g(n)=n f(n)=o(n) 13
4. Ω(n) Omega of n f(n)=ω(g(n))c n 0 nn n 0 f(n) cg(n) 2 c n 0 f(n) cg(n) cg(n)f(n)cg(n) f(n) f(n) f(n)=ω(g(n)) f(n) g(n) f(n) 3n 2 +8n 3n 2 +8n3n 2 3n 2 +8n 3n 2 cg(n)= 3n 2 c=3 g(n)= n 2 n 0 f(n) cg(n) 3n 2 +8n 3n 2 8n 0 n 0 =1n 0 =0~n 3n 2 +8n 3n 2 f(n)g(n)=n 2 f(n)=ω( n 2 ) 5. Θ(n) Theta of n f(n)=θ(g(n))c 1 c 2 n 0 nn n 0 c 1 g(n) f(n) c 2 g(n) 3 c 1 c 2 n 0 c 1 g(n) f(n) c 2 g(n) f(n) c 1 g(n) c 2 g(n) c 1 g(n) c 2 g(n) f(n) f(n) f(n)=θ(g(n)) f(n)c 1 g(n) c 2 g(n) f(n) 2n 2 +3n+2 2n 2 +3n+2 3n 2 2n 2 2n 2 2n 2 +3n+2 3n 2 c 1 g(n)=2n 2 c 2 g(n)=3n 2 c 1 =2 c 2 =3 g(n)=n 2 n 0 c 1 g(n) f(n) c 2 g(n) 2n 2 2n 2 +3n+2 3n 2 2n 2 2n 2 +3n+2-1/3 n 2n 2 +3n+2 3n 2 2 n 2 3n=n*(n 3)n 4 2 n*(n 3)-1/3 n n 0 =4 2n 2 2n 2 +3n+2 3n 2 f(n) g(n)= n 2 f(n)=θ( n 2 ) 6. O(1) O(log 2 n) O(n) O(nlog 2 n) O(n 2 ) O(n 3 ) O(2 n ) O(n!) (1) O(1) O(1)(Constant) 14
A. n B. for whilex++ C. if(x>5) y-- (2) O(log 2 n) O(log 2 n)(logarithmic) while forn(step) x*=2 for x*=2 for (i=1;i<=n; i*=2){ x++ (3) O(n) O(n)(Linear) while forn x++ A. while while(x<=n){ x++ B. for for (i=1;i<=n;i++){ x++ (4) O(nlog 2 n) O(nlog 2 n) (Log-linear) while for n x*=2x++ for x*=2 x++ for (i=1;i<=n; i*=2) for (j=1;j<=n; j++){ x++ (5) O(n 2 ) O(n 2 )(Quadratic) while for nx++ forx++ for (i=1;i<=n; i++) for (j=1;j<=n; j++){ x++ (6) O(n 3 ) O(n 3 )(Cubic) while for nx++ 15
for(step)x++ for (i=1;i<=n; i++) for (j=1;j<=n; j++) for (k=1;k<=n; k++){ x++ (7) O(2 n ) O(2 n )(Exponential) while fori=1 TO 2 n for for (i=1;i<=2 n ; i++){ x++ (8) O(n!) O(n!)(Factorial) while for I=1 TO n! for for (i=1;i<=n!; i++){ x++ 7. O(1)<O(log 2 n)<o(n)<o(nlog 2 n)<o(n 2 )<O(n 3 )<O(2 n )<O(n!) n a log 2 n n nlog 2 n n 2 n 3 2 n n! 1 0 1 0 1 1 2 1 1 1 2 2 4 8 4 2 1 2 4 8 16 64 16 24 1 3 8 24 64 512 256 40320 1 3.3 10 33 100 1000 1024 3628800 1 4 16 64 256 4096 65536 20922789888000 16
1. (1) x 3 +x 2 +1; (2) if(x<100) x+=2; else x--; (3) long recursion_fact(int n){ if(n==1) return 1; else return n* recursion_fact(n-1); 2. (1) for(i=0; i<=n; i++) a++; (2) for(j=0; j<=n; j+=3) b++; (3) for(k=0; k<=n; k*=5) c++; 3. (1) for(i=0; i<=n; i++) for(j=0; j<=n; j+=3) a++; (2) for(i=0; i<=n; i++) for(j=i;j<=n;j+=3) for(k=0;k<=n;k+=5) b++; (3) for(i=0; i<=n; i++) for(k=0;k<=n;k/=2) c++; 4. (1) for(i=0 ; i<=100 ; i++) for(j=0; j<=100 ; j+=3) a++ ; 17
(2) for(i=0 ; i<=n ; i++) for(j=0; j<=n ; j+=3) a++ ; for(i=0 ; i<=n ; i++) for(j=i ;j<=n ;j+=3) for(k=0 ;k<=n ;k+=5) b++; 5. (1) 3n+4 (2) 9n+2logn (3) 3n 2 +8n+1 (4) 5n 2 +3nlogn+7n (5) 5*2 n +n 3 +1 (6) n 4 +2 n 1. (1) O(1) (2) O(1) (3) n O(n) 2. (1) ni++o(n) (2) nj+=3o(n) (3) n k*=5 O(logn) 3. (1) ni++ j+=3 O(n 2 ) (2) ni++ j+=3 k+=5 O(n 3 ) (3) ni++ k/=2 O(nlogn) 4. (1) 100 O(1) (2) 5 n 2 +n 3 O(n 3 ) 18
5. O(1)<O(log 2 n)<o(n)<o(nlog 2 n)<o(n 2 )<O(n 3 )<O(2 n )<O(n!) (1) 3n O(n) 4 O(1)O(n) (2) 9n O(n) 2logn O(log 2 n)o(n) (3) 3n 2 O(n 2 ) 8n+1 O(n)O(n 2 ) (4) 5n 2 O(n 2 ) 3nlogn O(nlog 2 n) O(n 2 ) (5) 5*2 n O(2 n ) n 3 +1 O(n 3 )O(2 n ) (6) n 4 O(n 4 ) 2 n O(2 n )O(2 n ) 1-4-4 (Space Complexity) 1. (Fixed Space) 2. (Variable Space) (Pseudo Code) C JAVA VB PB i x1+x2 i=x1+x2 i=x1+x2 = = = = = not <>! <> and and && and or or or if Ifthen end If if{ IfThen End If 19
C JAVA VB PB if, else Ifthen if{ IfThen else else { Else end If End If switch Case switch{ Select Case :1: case 1: Case 1 :2: break; Case 2 :else: default: End Select end Case break; while Whiledo end While while{ Do While Loop While End While Do Until Loop do while Do do{ Do end While while; Loop While Do Loop Until for For i x1 to x2 do for(i=a;i<b;i++){ For i=a To b Step 1 end For Next i Exit exit for break Exit For Exit Do Exit Sub Exit Function Continue continue Continue Continue Return return return return dim var x integer int x Dim x As integer Array Array A[] A[] A[][] A() A(,) Pointer Pointer Tree->data Procedure Begin end void (){ Sub() End Sub 20