알고리즘 문제 풀이: 자주 쓰이는 코드3

* 초보자를 위한 추천 읽을꺼리 강의자료에서 모음

1) SWAP

 // 템플릿을 사용하여 범용성 있게  
 template<typename T>    
 // 레퍼런스를 사용하여 빠르게  
 void swap(T& a, T& b) {    
   T t = a;  
   a = b;  
   b = t;  
 }  

2) MAX

 int MAX(int p, int q) {  
   return p > q ? p : q;  
 }  

3) MIN

 int MIN(int p, int q) {  
   return p > q ? q : p;  
 }  

4) ABS

 int abs(int a) {  
   return a > 0 ? a : ‐a;  
 }   

5) Log 출력

 #if 1  
 #define PA(X, ...) printf(X, __VA_ARGS__)  
 #define P(X) printf(X)  
 #else  
 #define PA(X, ...)  
 #define P(X)  
 #endif  
 int main() {  
   P("Hello!");  
   PA(" %s", "world");  
 }  

6) 수행시간 측정

 #include <ctime> or <time.h>  
 clock_t = t1, t2;  
 t1 = clock();  
 {  
   Code  
 }  
 t2 = clock();  
 printf("time: %lf\n", (double)(t2-t1)/CLOCKS_PER_SEC);  

7) 나머지 연산

 (a + b) % m = ( a % m + b % m) % m  
 (a * b) % m = ( a % m * b % m) % m  

8) BigInteger for C++
C에서 BigInteger 사용에 관한 백준님의 추천링크
https://www.acmicpc.net/board/view/3125
=> http://stackoverflow.com/questions/4507121/c-big-integer
=> http://codeforces.com/blog/entry/16380

9) quick sort

 void quickSort(int arr[], int left, int right) {  
     int i = left, j = right;  
     int tmp;  
     int pivot = arr[(left + right) / 2];  
     while (i <= j) {  
         while (arr[i] < pivot)  
             i++;  
         while (arr[j] > pivot)  
             j--;  
         if (i <= j) {  
             tmp = arr[i];  
             arr[i] = arr[j];  
             arr[j] = tmp;  
             i++;  
             j--;  
         }  
     };  
     if (left < j)  
         quickSort(arr, left, j);  
     if (i < right)  
         quickSort(arr, i, right);  
 }  

10) merge sort

 void merge(int arr[], int copy[], int start, int end) {  
   int mid = (start + end) / 2;  
   int i = start;  
   int j = mid + 1;  
   int k = start;  
   while (i <= mid && j <= end) {  
     if (arr[i] <= arr[j])  
       copy[k++] = arr[i++];  
     else  
       copy[k++] = arr[j++];  
   }  
   while (i <= mid)  
     copy[k++] = arr[i++];  
   while (j <= end)  
     copy[k++] = arr[j++];  
   for (int i = start; i <= end; i++)  
     arr[i] = copy[i];  
 }  
 void sort(int arr[], int copy[], int start, int end) {  
   if (start == end)  
     return;  
   int mid = (start + end) / 2;  
   sort(arr, copy, start, mid);  
   sort(arr, copy, mid + 1, end);  
   merge(arr, copy, start, end);  
 }