1. gcd, quickSort, swap

 CCI 문제를 파이썬으로 풀고 프로젝트도 자바나 파이썬을 주로 쓰니 C를 쓸 일이 없어서 거의 6개월은 C를 못 만진거같다.  C 문법이 필요해서 기억을 살릴겸 기본 알고리즘, 자료구조들을 구현하면서 C언어 감각을 살리는 방향으로 진행할 예정이다.

 대략 gcd, quickSort, swap (call by value, call by reference), mergeSort, linked list, binary search tree, priority queue, graph, hash table(chaining & probing) 정도를 구현하며 함수 포인터 사용을 추가적으로 공부한다.

 기본 자료구조를 파이썬으로 구현하는 것은 CCI 연습을 파이썬으로 했기 때문에 손에 익어서 쉽게 구현할 수 있지만, 몇 가지 C언어와 파이썬의 다른점( list 합치기나 자료형을 명시해주는 선언방식)이 손에 익으려면 일주일 정도는 연습해야겠다고 판단했다.

-quickSort

#include <stdio.h>
 
#define    L_SIZE    10
 
void quickSort(int L[], int left, int right){
    int pivot = L[(left + right) / 2];
    int i, j, tmp;
    i = left;
    j = right;
 
    while(1){
        while(pivot > L[i])
            i++;
        while(pivot < L[j])
            j--;
 
        if(i <= j){
            tmp = L[i];
            L[i] = L[j];
            L[j] = tmp;
            i++;
            j--;
        } else {
            break;
        }
    }
    if(left < j)
        quickSort(L, left, j);
    if(right > i)
        quickSort(L, i, right);
    
}
 
int main(){
    
    int L[L_SIZE] = {46, 25, 5, 94, 88, 18, 48, 43, 1, 69};
 
    int i = 0;
    
    
 
    quickSort(L, 0, L_SIZE - 1);
    for(i = 0; i < 10; i++){
        printf("%d ", L[i]);
    }
    return 0;
}

 정렬되어있을 경우 피봇을 첫 번째 원소로 잡고 반복하면 O(n^2)의 복잡도가 나오지만 그럴 확률은 적다.  보통 O(n log n)의 평균 복잡도가 나오며 불안정 정렬에 속한다.

-swap (call by value / call by reference)

#include <stdio.h>
 
int swapByValue(int a, int b){
    int tmp;
    tmp = b;
    b = a;
    a = tmp;
    
}
 
void swapByReference(int *a, int *b){
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}
 
int main(){
    
    int a = 10;
    int b = 20;
 
    int * ptr1;
    int * ptr2;
 
    ptr1 = &a;
    ptr2 = &b;
 
    swapByValue(a, b);
    swapByReference(ptr1, ptr2);
    printf("%d, %d", a, b);
    return 0;
}

 별거아닌 코드지만 안쓰다가 쓰라하면 헷갈릴 수 있다.  ptr1, ptr2는 a, b를 담는 int형 포인터변수인데 포인터 변수에 a와 b를 가리키는 주소를 저장하고 이것들을 매개변수로 swapByReference 함수에 사용했다.  의미가 a와 b의 주소를 저장하는 것이므로 아래와 같이 간소화해도 관계없다.

#include <stdio.h>
 
int swapByValue(int a, int b){
    int tmp;
    tmp = b;
    b = a;
    a = tmp;
    
}
 
void swapByReference(int *a, int *b){
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}
 
int main(){
    
    int a = 10;
    int b = 20;
 
    swapByValue(a, b);
    swapByReference(&a, &b);
    printf("%d, %d", a, b);
    return 0;
}

-gcd/lcm

#include <stdio.h>
 
int gcd(int big, int small){
    if(small == 0){
        return big;
    } else {
        return gcd(small, big % small);
    }
}
 
int lcm(int big, int small){
    int gcdVal = gcd(big, small);
    if(gcdVal == small){
        return big * small;
    } else {
        return big * small * gcdVal;
    }
}
 
int main(){
    
    int a = 153;
    int b = 15;
 
    
    printf("%d\n", gcd(a, b));
    printf("%d", lcm(a, b));
    return 0;
}

f(a, b)를 gcd(big, small)이라고 할 때, <big mod small>이 0일 경우 f(big, small) = small이 된다.

그렇지 않다면, f(big, small) = f(small, big % small)이 된다.  이를 유클리드 호제법이라고 한다.  lcm은 만일 최대공약수가 제시된 작은 수와 같을 경우 big * small만 리턴하면 되며, 그렇지 않다면 big * small * gcdVal를 리턴항 최소 공배수를 구한다.

-malloc

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
typedef struct Person {
    char name[10];
    int id;
    char phoneNumber[14];
}Person ;
 
int main(){
    Person *p1 = (Person *) malloc(sizeof(Person));
    if(p1 == NULL) printf("P1 not Found!");
    strcpy(p1->name, "김남규");
    p1->id = 20130022;
    strcpy(p1->phoneNumber, "010-2766-5124");
 
    printf("id : %d / name : %s / phoneNumber : %s", p1->id, p1->name,  p1->phoneNumber); 
    
    free(p1);
    return 0;
 
}

 c에서는 malloc 함수를 사용해서 구조체 변수의 값을 생성해줘야 한다.