재귀 방식으로 이진 탐색하기.

이진 탐색을 재귀적인 방법으로 구현해 봤다.

"윤성우의 열혈 자료구조" 61페이지에 언급된 것을 스스로 구현해 봄.

  1 #include <stdio.h>
  2
  3 int main(int argc, char * argv[])
  4 {
  5         int arr[] = {3, 7, 9, 11, 25, 27, 30, 33};
  6         int target = 3;
  7         int first = 0;
  8         int len = sizeof(arr) / sizeof(int);
  9         int last = len - 1;
 10         bsr(arr, first, last, 3);
 11         bsr(arr, first, last, 7);
 12         bsr(arr, first, last, 9);
 13         bsr(arr, first, last, 11);
 14         bsr(arr, first, last, 25);
 15         bsr(arr, first, last, 27);
 16         bsr(arr, first, last, 30);
 17         bsr(arr, first, last, 33);
 18         bsr(arr, first, last, 34);
 19 }
 20
 21
 22 int bsr(int* arr, int first, int last, int target)
 23 {
 24
 25         int mid = (first + last) / 2;
 26
 27         if(first > last)  {
 28                 printf("not found %d %d\n", first, last);
 29                 return -1;
 30         }
 31
 32         if(arr[mid] == target) {
 33                 printf("found %d %d\n", mid, arr[mid]);
 34                 return mid;
 35         } else if (arr[mid] < target) {
 36                 printf("ele less than target (%d %d)\n", mid+1, last);
 37                 return bsr(arr, mid+1, last, target);
 38         } else if (arr[mid] > target) {
 39                 printf("ele greater than target (%d %d)\n", mid+1, last);
 40                 return bsr(arr, first, mid-1, target);
 41         }
 42 }

피보나치 구하기

피보나치 알고리즘 문제 풀기
재귀 기법(recursive)으로 해를 내봤다. recursive는 효율이 떨어지나, 왜 떨어지는지 알 필요가 있으므로 구현해볼 필요도 있다고 생각함.
recursive 사고 방식은 사고의 전환이 많이 필요하지만, 테크닉적인 면도 없지않아 있는듯.

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3
  4 int fib(int n, int * arr);
  5
  6 int main(int argc, char * argv[])
  7 {
  8         int * arr_fib = NULL;
  9         int target_num = 5;
 10         int i;
 11
 12         arr_fib = (int *)malloc((target_num+1)*sizeof(int));
 13
 14         fib(target_num, arr_fib);
 15         //printf("fib(%d) == %d\n", 10, fib(10, arr_fib));
 16
 17         for(i = 0; i <= target_num; i++)
 18         {
 19                 printf("arr[%d] %d\n", i, arr_fib[i]);
 20         }
 21
 22         free(arr_fib);
 23 }
 24
 25 int fib(int n, int * arr)
 26 {
 27         int ret_num;
 28         if (n <= 0) {
 29                 ret_num = 0;
 30         }
 31         else if (n == 1)  {
 32                 ret_num = 1;
 33         }
 34         else if (n > 1) {
 35                 ret_num = fib(n-2, arr) + fib(n-1, arr);
 36         }
 37         arr[n] = ret_num;
 38         printf("arr[%d] %d\n", n, arr[n]);
 39
 40         return ret_num;
 41 }
 42 

factorial 구하기

"윤성우의 열혈 자료구조" 53페이지의 팩토리얼 함수에 대해서 구현해 봄.
'내가 재귀함수에 대해서도 이렇게 구현을 잘 못하는구나.'라는 생각을 했다.
그런데, 구현은 얼추 맞는 것 같다.

  1 #include <stdio.h>
  2
  3 #define FACTORIAL_NUM 12
  4
  5 int fac(int n);
  6
  7 int main(int argc, char * argv[])
  8 {      
  9         int fac_n = FACTORIAL_NUM;
 10        
 11         printf("fac(8) %d\n", fac(fac_n));
 12 }
 13
 14 int fac(int n)
 15 {      
 16         int rec_val;
 17         if(n == 1) {
 18                 printf("last n = %d\n", n);
 19                 return 1;
 20         }
 21        
 22         rec_val = fac(n-1);
 23        
 24         printf("n = %4d, fac(n-1) = %d\n", n, rec_val);
 25         return n * rec_val;
 26 }

이진 탐색하기

윤성우의 열혈자료구조 24페이지의 '이진 탐색'에 대한 내용이 있어 나름대로 구현해봄.
그닥 나쁘지는 않지만, 컴퓨터공학 박사들이 구현해놓은 코드보다는 허접하겠지뭐.

  1 #include <stdio.h>
  2
  3
  4 #define TARGET_NUM 3
  5
  6 int main(int argc, char * argv[])
  7 {
  8
  9         int arr[] = {0, 1, 2, 3, 5, 7, 9, 12, 21, 23, 27, 40, 41, 50, 69};
 10         int arr_n = sizeof(arr)/sizeof(int);
 11         int c = arr_n / 2;
 12         int t = TARGET_NUM;
 13         int found = 0;
 14         int try_c = 0;
 15         printf("tot %d\n", arr_n);
 16 #define TEST
 17 #ifdef TEST
 18
 19         while(1) {
 20                 printf("try_c %d c = %d [%d]\n", try_c, c, arr[c]);
 21                 if(c < 0 || c >= arr_n) {
 22                         break;
 23                 }
 24                 try_c++;
 25
 26
 27                 if(t == arr[c]) {
 28                         found = 1;
 29                         break;
 30                 }
 31
 32                 if(t < arr[c]) {
 33                         c = c / 2;
 34                         continue;
 35                 }
 36
 37                 if(t > arr[c]) {
 38                         c = (arr_n + c) / 2;
 39                         continue;
 40                 }
 41         }
 42
 43         if(found) {
 44                 printf("Found %d\n", c);
 45         }
 46         else {
 47                 printf("Not found\n");
 48         }
 49
 50 #endif
 51         return 0;
 52 }

A집합은 B집합의 부분집합인가?

'누워서 읽는 알고리즘' 95페이지의 문제를 풀어보았다.
오래간만에 집합이란 개념에 대해서 접하게 된건지 아니면 생각의 속도가 느린건진 모르겠지만 1시간은 걸린 것 같다. 물론 이 방법이 최적화되거나 원하는 답이 아닐 수 있으나, 나름 맞는 듯.

  1 #include <stdio.h>
  2
  3 int A[] = {1, 2, 3, 4, 5, 7, 11 };
  4 int B[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
  5
  6 int inc_A(int A_el, int * B, int m);
  7 int main(int argc, char * argv)
  8 {
  9         int j;
 10         int n = 7;
 11         for (j = 0 ; j < n; j++) {
 12                 if(!inc_A(A[j], B, 10)) {
 13                         printf("A is not super B\n");
 14                         return 1;
 15                 }
 16         }
 17         printf("A is super B\n");
 18         return 0;
 19 }
 20
 21
 22 int inc_A(int A_el, int * B, int m)
 23 {
 24         int i;
 25         for(i = 0; i < m; i++) {
 26                 if(A_el == B[i]) {
 27                         printf("matched A_el (%d) == B[%d] (%d)\n",
 28                                 A_el, i, B[i]);
 29                         return 1;
 30                 }
 31         }
 32
 33         printf("A_el (%d) not included\n", A_el);
 34         return 0;
 35 }

~                                                                                                            
~                                                                                                            
~              

요일 계산하기 프로그래밍

'누워서 읽는 알고리즘'을 읽고 있다. 나의 알고리즘 실력이 형편없다고 느껴서다.
역시 이 책에 나오는 알고리즘 문제를 풀고 있는데 형편없다는 것이 증명되고 있다.
쉽지 않다. 그래서 더더욱 이 책을 끝내야겠다는 생각이 들었다.
저자의 마인드가 마음에 든다.
85페이지의 프로그래밍 과제를 풀었다.
요일을 알아맞추는 프로그래밍 과제이다. C를 짜는 사람이므로 C로 풀었다.

결과는 얼추 맞는 것 같다. :-)
(ㅋㅋ 이건 뭐지. 이 프로그래머 같지 않은 문장이라니. 얼추 맞다니 ㅋㅋ)

  1 /*
  2 created at 9:50 AM Jan.8.2016
  3 by T.Y. Jin
  4 */
  5 #include <stdio.h>
  6
  7 #define WED_IDX 2
  8 #define DAYS    7
  9
 10 int main(int argc, char * argv[])
 11 {
 12         int i;
 13         int y, m, d;
 14         int dif_y, dif_m, dif_d;
 15         int d_idx;
 16         int n_leap_year;
 17         int is_leap_year;
 18         int cal_d;
 19                        // 0      1      2      3      4      5      6
 20         char* days[] = {"Mon", "Tue", "Wed", "Thu", "Fri", "Sat", "Sun"};
 21                      //  1   2   3   4   5   6   7   8   9  10  11  12
 22         int months[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31 };
 23
 24         if(argc < 4) {
 25                 printf("argc = %d\n", argc);
 26                 return 1;
 27         }
 28         y = atoi(argv[1]);
 29         m = atoi(argv[2]);
 30         d = atoi(argv[3]);
 31
 32         printf("%d.%d.%d\n", y, m, d);
 33
 34         // 2000.2.29 Tue
 35         // <-- 31 + 29 =  Tue
 36         // 1999.12.31 X day
 37         // (X + 60) % 7  --> Tue (1)
 38         // X = Fri (4)
 39         // 2000. 1. 1  Sat (5) <-- Ref Day
 40
 41         // check the valid year
 42         if (y < 2000) {
 43                 printf("Invalid year (%d)\n", y);
 44                 return 1;
 45         }
 46         // check the valid month
 47         if(m > 12) {
 48                 printf("Invalid month (%m)\n", m);
 49                 return 1;
 50         }
 51
 52         // years
 53         dif_y = y - 2000;
 54         printf("dif_y = %d\n", dif_y);
 55
 56         // is the leap day???
 57         n_leap_year = dif_y / 4;
 58         is_leap_year = (dif_y % 4 == 0) ? 1 : 0;
 59         printf("num leap year %d\n", n_leap_year);
 60         printf("is leap year %d\n", is_leap_year);
 61
 62         // check the valid date
 63         if (is_leap_year) {
 64                 if (m == 2) {
 65                         if (d > months[m-1]+1) {
 66                                 printf("Invalid 1 date (%d)\n", d);
 67                                 return 1;
 68                         }
 69                 } else {
 70                         if (d > months[m-1]) {
 71                                 printf("Invalid 2 date (%d)\n", d);
 72                                 return 1;
 73                         }
 74                 }
 75         }
 76         else {
 77                 if (d > months[m-1]) {
 78                         printf("Invalid 3 date (%d)\n", d);
 79                         return 1;
 80                 }
 81         }
 82
 83         // months
 84         for(i = 0; i < m - 1; i++) {
 85                 if(is_leap_year && i == 1) { // Feb recal
 86                         dif_m += months[i]+1;
 87                 } else {
 88                         dif_m += months[i];
 89                 }
 90         }
 91         printf("dif_m = %d\n", dif_m);
 92
 93         // days
 94         dif_d = (dif_y * 365) + dif_m + (d-1);
 95         dif_d += dif_y ? n_leap_year : 0;
 96         printf("dif_d = %d\n", dif_d);
 97
 98         // calculate the day
 99         cal_d = (dif_d + 5)  %  DAYS;
100         printf("cal_d = %s\n", days[cal_d]);
101
102
103         return 0;
104 }