[Git] Git Server & Client

Server : Ubuntu 14.04 LTS
Client : Windows 7, Ubuntu 14.04 LTS

reference : https://www.davidlab.net/ko/tech/how-to-setup-git-server-on-ubuntu-part1/


- Server
1. Open SSH 설치
$ sudo apt-get install openssh-server
$ sudo ufw allow ssh

2. Git 설치
$ sudo apt-get install git-core
$ sudo adduser --system --shell /bin/bash --gecos 'Git Admin' --group --disabled-password --home /opt/git git

3.User 정보 입력
$ git config --global user.name "foo" 
$ git config --global user.email "foo@bar.com"

4. Client들의 Public Key를 등록해주기
// 이 부분은 아래의 클라이언트들이 먼저 Public, Private Key를 만들고 나서 진행해야함
받은 key의 이름이 foo.pub 이고 그것을 tmp에 넣어뒀다고 가정하면..
$ sudo su - git
$ mkdir ~/.ssh
$ chmod 700 ~/.ssh
$ cat /tmp/foo.pub >> ~/.ssh/authorized_keys
$ chmod 600 ~/.ssh/authorized_keys

5. Repository 생성하기
$ sudo su - git
$ mkdir test.git
$ cd test.git
$ git init --bare
$ exit

6.




- Client (Ubuntu)
1. Key 만들기
$ ssh-keygen -t rsa -C “foo@bar” 
치면 key를 생성할 폴더와 패스워드를 입력한다. 패스워드는 공란으로 두어도 된다

2. Source Import
프로젝트 폴더를 만들고 내부에 파일을 생성한다.
$ git init
$ git add .
$ git commit -m "Initial Commit"

3.Remote 추가
git@<Git Server의 IP 또는 Domain Name>:<Repository 이름>
ssh://git@<Git Server의 IP 또는 Domain Name>/<Repository 이름>
$ git remote add origin git@dev.example.com:test.git
$ git push origin master

4. Git Clone
$ git clone git@dev.example.com:test.git





 - Client (Windows)
1. Git 설치
TortoiseGit 을 설치한다. Choose SSH Client 가 나오면 TortoiseGitPlink를 선택.
MSYSGit 을 설치한다. 중간에 선택지가 나올텐데 다음과 같은 항목을 선택한다.
Use Git from The windows command prompt를 선택.
Use (Tortoise)Plink를 선택.
Checkout Windows-style, commit unix-style line ending 선택.

2. Key 만들기
Windows Key + R 를 하여 puttygen 입력하고 엔터하면 창이 뜰 것이다.
Generate 버튼을 누르고 마우스 막 휘저어라 그럼 게이지가 채워진다.
끝나면 상단에 Public Key가 생성된다. 해당 파일을 id_rsa.pub 으로 저장한다.
그리고 Save Private Key 를 눌러 자신만의 폴더에 저장해둔다. (잃어버리면 안됨)

3. Git Clone 
프로젝트 폴더를 만들고 마우스 오른쪽 클릭하고 Git Clone을 선택한다.
URL : git@dev.example.com:test.git
Directory : 프로젝트 디렉토리
Load Putty Key : 2번에서 맏들어 두었던 Private Key를 가져온다.

이제부터는 pull, push, commit 등이 가능해진다.

[Algorithm] Kruskal Algorithm

Kruskal 알고리즘은 MST를 만들어내는 알고리즘 하나로서 Heap과 Union-Find 라는 자료구조를 이용한다. Greedy 알고리즘이라 최적해를 도출해 내는지 알 순 없지만 누군가 증명을 했단다. MST를 이용하면 Minimum Spanning Tree 가 만들어진다.


#include <iostream>
#include <stdio.h>
#define MAX_VETICES 100
using namespace std;

// Kruskal's element
typedef struct
{
int key;
int u;
int v;
} k_elem;

// Union-Find
int parent[MAX_VETICES];
int num[MAX_VETICES];
void set_init(int n)
{
for (int i = 0; i < n; i++){
parent[i] = -1;
num[i] = 1;
}
}
int set_find(int v)
{
int p, i = -1;
for (i = v; (p = parent[i]) >= 0; i = p);
int s = i;
for (i = v; (p = parent[i]) >= 0; i = p){
parent[i] = s;
}
return s;
}
void set_union(int s1, int s2)
{
int p1 = set_find(s1);
int p2 = set_find(s2);
if (num[p1] > num[p2]){
parent[p2] = p1;
num[p1] += num[p2];
}
else{
parent[p1] = p2;
num[p2] = parent[p1];
}
}

// MinHeap
k_elem h[MAX_VETICES];
int h_size;
void h_init()
{
h_size = 0;
}
void h_insert(k_elem v)
{
int i = ++h_size;
while (i != 1 && v.key < h[i/2].key){
h[i] = h[i / 2];
i /= 2;
}
h[i] = v;
}
k_elem h_remove()
{
k_elem item = h[1];
k_elem temp = h[h_size--];
int p = 1;
int c = 2;
while (c <= h_size){
if (h[c].key > h[c + 1].key) c++;
if (temp.key <= h[c].key) break;
h[p] = h[c];
p = c;
c *= 2;
}
h[p] = temp;
return item;
}

// Kruskal
int k_distance[MAX_VETICES][MAX_VETICES] =
{
{ 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 29, 0, 0, 0, 10, 0 }, // a
{ 0, 29, 0, 16, 0, 0, 0, 15 }, // b
{ 0, 0, 16, 0, 12, 0, 0, 0 }, // c
{ 0, 0, 0, 12, 0, 22, 0, 18 }, // d
{ 0, 0, 0, 0, 22, 0, 27, 25 }, // e
{ 0, 10, 0, 0, 0, 27, 0, 0 }, // f
{ 0, 0, 15, 0, 18, 25, 0, 0 }, // g
};


void kruskal(int n)
{
h_init();
set_init(n);
for (int i = 1; i <= n; i++){
for (int j = i; j <= n; j++){
if (k_distance[i][j] > 0){
k_elem element{ k_distance[i][j], i, j };
h_insert(element);
}
}
}

int accepted = 0;

while (accepted < (n - 1)){
k_elem e = h_remove();
int uset = set_find(e.u);
int vset = set_find(e.v);
if (uset != vset){
printf("(%d, %d) : %d\n", e.u, e.v, e.key);
accepted++;
set_union(uset, vset);
}
}
}


int main()
{
int n = 7;
kruskal(n);
return 0;
}

[Data Structure] Union Find

Union-Find는 집합을 다루는 트리 형태의 자료구조다. Union 함수를 통해 집합을 서로 결합시키고 Find를 통해 그 집합의 대표 정점을 가져온다. Union-Find 는 Kruskal 알고리즘을 구현하는 것에 사용된다. 물론 그 외에도 많이 사용된다.


#include <iostream>
#include <stdio.h>
#define MAX_VETICES 100

using namespace std;

int parent[MAX_VETICES];
int num[MAX_VETICES];

void set_init(int n)
{
for (int i = 0; i < n; i++){
parent[i] = -1;
num[i] = 1;
}
}

int set_find(int vertex)
{
int p, i = -1;
for (i = vertex; (p = parent[i]) >= 0; i = p);
int s = i;
for (i = vertex; (p = parent[i]) >= 0; i = p){
parent[i] = s;
}
return s;
}

void set_union(int s1, int s2)
{
int p1 = set_find(s1);
int p2 = set_find(s2);
if (num[p1] < num[p2]){
parent[p1] = p2;
num[p2] += num[p1];
}
else{
parent[p2] = p1;
num[p1] += num[p2];
}
}

int main()
{
// Suppose Set S = {1,2,3,4,5,6};
set_init(7);

set_union(1, 4);
set_union(5, 2);
// {1,4}, {5,2}, {3}, {6}
for (int i = 1; i <= 6; i++){
printf("Parent of [%d] : %d\n",i, set_find(i));
}

set_union(4, 5);
set_union(3, 6);
// {1,4,5,2}, {3,6}
for (int i = 1; i <= 6; i++){
printf("Parent of [%d] : %d\n", i, set_find(i));
}
return 0;
}

[Data Structure] Topological Order (위상 정렬)

위상 정렬. 순회가 없고 방향이 있는 그래프(Directed acyclic graph)를 선후관계에 의해 정렬하는 방법이다. Stack을 이용해 구현을 하긴 했지만 다른 자료구조를 이용해도 문제는 없을 것으로 보인다. 포인터를 사용하지 않고 구현하려 애써봤지만 link 때문에 포인터가 필요하며, 그것 때문에 각 노드를 malloc 해줘야 했다. 이 이상 단순하게 짤 수 있을지 모르겠다.


#include <iostream>
#include <stdio.h>

using namespace std;

int s[100];
int s_size;
void init_s()
{
s_size = -1;
for (int i = 0; i < 100; i++){
s[i] = NULL;
}
}
int pop()
{
return s[s_size--];
}
void push(int i)
{
s[++s_size] = i;
}
int is_empty_s()
{
return s_size == -1;
}


#define MAX_NODE_NUM 100

typedef struct GraphNode
{
int vertex;
struct GraphNode *link;
} GraphNode;

int g_size;
GraphNode *adj_list[MAX_NODE_NUM];
int in_degree[MAX_NODE_NUM];

void graph_init(int n)
{
g_size = n;
for (int v = 0; v < MAX_NODE_NUM; v++){
adj_list[v] = NULL;
}
}

void insert_edge(int u, int v)
{
GraphNode *node = (GraphNode*)malloc(sizeof(GraphNode));
node->vertex = v;
node->link = adj_list[u];
adj_list[u] = node;
}

void topo_sort()
{
for (int i = 0; i < g_size; i++){
GraphNode *node = adj_list[i];
while (node){
in_degree[node->vertex]++;
node = node->link;
}
}
init_s();
for (int i = 0; i < g_size; i++){
if (in_degree[i] == 0) push(i);
}
while (!is_empty_s()){
int w = pop();
printf("%d ", w);
GraphNode *node = adj_list[w];
while (node){
in_degree[node->vertex]--;
if (in_degree[node->vertex] == 0) push(node->vertex);
node = node->link;
}
}
return;
}

int main()
{
graph_init(6);
insert_edge(0, 2);
insert_edge(0, 3);
insert_edge(1, 3);
insert_edge(1, 4);
insert_edge(2, 3);
insert_edge(2, 5);
insert_edge(3, 5);
insert_edge(4, 5);
topo_sort();
return 0;
}

[Algorithm] 알고리즘 정리

Algorithm

1. Basic : Complexity, Bit
2. Brute Force & Complete Searching
3. Greedy
4. Divide and Conquer
5. Back Tracking
6. Graph (MST, DSP, BSP, etc,.)
7. String
8. Dynamic Programming
9. Math (특히 이산수학, 정수론)
10. Probability

[Data Structure] 자료구조 정리

Data Structure

1. Array
2. List : Linked List, Circular Linked List, Double Linked List
3. Stack
4. Queue : Queue, Deck
5. Tree : Binary Tree, Thread Binary Tree
6. Heap (Priority Queue)
7. Sorting : Selection, Insertion, Bubble, Cell, Merge, Quick, Heap, Radix(기수)
8. Graph : DSP, BSP, MST, Shortest Path, Topological Sort
9. Hashing : Hash Function, Linear Probing, Chaining
10. Searching : Searching in sorted data, Searching in not sorted data, AVL Tree

[Algorithm] Repeated Squaring

Repeated Squaring은 a의 p승을 log 시간에 계산하는 알고리즘이다.
define 된 MOD 는 알고리즘 풀 때 너무 큰 값이 나오는 것을 방지하기 위한 모듈러 값이다.

알고리즘 이해를 해보자.
모든 p는 2의 배수로 나타낼수 있다. 12를 소인수분해 한 나머지를 생각해보자.
8(2의3승) + 4(2의2승) 으로 나타낼 수 있다. 그외의 모든 수가 그러하다. 왜냐하면 모든 수가 2진수로의 변환이 가능하기 때문이다. 12를 소인수 분해한 나머지를 나열해보면 1100이 나온다. 이게 12의 2진수를 의미한다. 그리고 그때마다 해당하는 2의 승수를 곱해주면 된다.

이해가 안갈테니 3의 36승이 있다고 하자. 이 때 36을 소인수분해 후 나머지를 나열해보면
100100 이 나온다. 이 값은 2의 5승 + 2의 2승이며 각각 32와 4이다.
이 때 1의 값이 나올 때의 2의 승수를 계속 곱해주면 값이 나오는 것이다. 이해하기 어려울 것인데....ㅜㅜ

아래 코드를 참고해서 말해 보면.

    a         p       v
3의1승    36      1
3의2승    18      1
3의4승     9       1
3의8승     4    3의4승
3의16승   2    3의4승
3의32승   1    3의4승
3의64승   0    3의4승 * 3의 32승

맨마지막의 v값이 결과다.


#include <stdio.h>
#include <iostream>

#define MOD 1000000007

using namespace std;

int pow(int a, int p)
{
int val = 1;
while (p > 0){
if (p % 2 == 1) val = (val * a) % MOD;
p /= 2;
a = (a *a) % MOD;
}
return val;
}

int main()
{
long long int ret = pow(2, 20);
printf("%lld\n", ret);
return 0;
}

[Algorithm] Edit Distance

Edit Distance 는 두 문자열을 동일하게 만들려면 얼만큼의 수정이 필요한지를 수치로 나타내는 알고리즘이다.

별로 어려운 건 없다. 핵심은 최소 수정의 값을 가져오는 DP라는 점이다.. 같은 문자가 발견되면 penalty를 없앤다. 자세한 것은 검색을 해보자. 아래는 내가 짠 기본적인 edit distance 코드다.


#include <iostream>
#include <stdio.h>
#define MIN(x,y,z) ((x) < (y)) ? ((z) < (x) ? (z) : (x)) \
: ((z) < (y) ? (z) : (y))

using namespace std;

int arr[100][100];
int strlen(char* str)
{
int cnt = 0;
while (str[cnt++] != '\0');
return cnt - 1;
}
int edit_dis(char* str1, char* str2)
{
int len1 = strlen(str1);
int len2 = strlen(str2);
for (int i = 0; i <= len1; i++) arr[i][0] = i;
for (int i = 0; i <= len2; i++) arr[0][i] = i;
for (int i = 1; i <= len1; i++){
for (int j = 1; j <= len2; j++){
int min = MIN(arr[i][j - 1] + 1, arr[i - 1][j] + 1,
(str1[i - 1] == str2[j - 1] ?
arr[i - 1][j - 1] : arr[i - 1][j - 1] + 1));
arr[i][j] = min;
}
}
return arr[len1][len2];;
}

int main()
{
char str1[100] = "monkey";
char str2[100] = "money";
int dis = edit_dis(str1, str2);
printf("%d\n", dis);
return 0;
}

[Algorithm] LCP

#include <iostream>
#include <stdio.h>

using namespace std;
char tstr[5005];
int idxarr[5005];
int LCP[5005];
int LEN[5005];
long long int noval;

void swap(int& a, int& b)
{
int tmp = a;
a = b;
b = tmp;
}

int strlen(char* chr)
{
int len = 0;
while(chr[len++] != '\0');
return len - 1;
}

int scmp(char ch1[], char ch2[])
{
int i = 0; int len1 = strlen(ch1);
int j = 0; int len2 = strlen(ch2);
while(i < len1 && j < len2){
if(ch1[i] < ch2[j]) return 1;
else if(ch1[i] > ch2[j]) return 0;
i++; j++;
}
return len1 < len2 ? 1 : 0;
}

void init(int n)
{
for(int i=1; i<=n; i++){
idxarr[i] = i;
LCP[i] = 0;
LEN[i] = 0;
}
noval = 0;
}

int partition(int arr[], int left, int right)
{
int low = left;
int high = right + 1;
int ppos = left;
char* pval = tstr + arr[ppos];

do{
do low++;
while (low < right && !(scmp(pval, tstr + arr[low])));
do high--;
while (left < high && (scmp(pval, tstr + arr[high])));
if(low < high) swap(arr[low],arr[high]);
}while(low < high);
swap(arr[ppos],arr[high]);
return high;
}

void sortarr(int arr[], int left, int right)
{
if(left < right) {
int pivot = partition(arr, left, right);
sortarr(arr, left, pivot - 1);
sortarr(arr, pivot + 1, right);
}
}

void makelen(int n)
{
for(int i=1; i<=n; i++)
noval += (LEN[i] = strlen(tstr + idxarr[i]));
}

void makelcp(int n)
{
for(int i=2; i<=n; i++){
int len1 = strlen(tstr + idxarr[i-1]);
int len2 = strlen(tstr + idxarr[i]);
int len = len1 < len2 ? len1 : len2;
for(int j=0; j<len; j++){
if ((tstr + idxarr[i - 1])[j] == (tstr + idxarr[i])[j])
noval -= ++LCP[i];
else break;
}
}
}

char sol[5005];
void printsol(int t, int n, int k)
{
if(noval < k){
printf("#%d none\n",t);
return;
}
int cnt = k;
int iter = 1;
while(true){
int tmp = cnt;
tmp -= (LEN[iter] - LCP[iter]);
if(tmp <= 0)
break;
cnt -= (LEN[iter] - LCP[iter]);
iter++;
}
for(int i=0; i<cnt + LCP[iter]; i++){
sol[i] = (tstr + idxarr[iter])[i];
}
sol[cnt + LCP[iter]] = '\0';
printf("#%d %s\n",t, sol);
}

int main()
{
//freopen("sample_input.txt","r",stdin);
for(int t=1; t<=40; t++){
int K; cin >> K >> (tstr + 1);
int len = strlen(tstr + 1);
init(len);
sortarr(idxarr, 1, len);
makelcp(len);
makelen(len);
printsol(t, len, K);
}
return 0;
}

[Algorithm] 최단 경로 알고리즘 Dijkstra, Floyd

최단 경로 문제를 푸는 흔히 쓰이는 2가지 알고리즘이 있다.

Dijkstra와 Floyd다. Dijkstra는 한 정점 s에서 다른 모든 정점 사이의 최단 거리를 구한다.

반면 Floyd 알고리즘은 모든 정점 사이의 최단 거리를 구하는 알고리즘이다. 아주 심플하면서도 강력한 최단 경로 알고리즘이다.

먼저 Dijkstra 의 코드다.

#include <iostream>
#define TRUE 1
#define FALSE 0
#define MAX_VERTICES 7
#define INF 1000
using namespace std;
int weight[MAX_VERTICES][MAX_VERTICES] =
{
 { 0, 7, INF, INF, 3, 10, INF},
 { 7, 0, 4, 10, 2, 6, INF },
 { INF, 4, 0, 2, INF, INF, INF },
 { INF, 10, 2, 0, 11, 9, 4 },
 { 3, 2, INF, 11, 0, INF, 5 },
 { 10, 6, INF, 9, INF, 0, INF },
 { INF, INF, INF, 4, 5, INF, 0 }
};
int dis[MAX_VERTICES];
int found[MAX_VERTICES];
int choose(int distance[], int n, int found[])
{
 int min = INT_MAX;
 int minpos = -1;
 for (int i = 0; i < n; i++){
  if (distance[i] < min&&!found[i]){
   min = distance[i];
   minpos = i;
  }
 }
 return minpos;
};
void shortest_path(int s, int n)
{
 for (int i = 0; i < n; i++){
  dis[i] = weight[s][i];
  found[i] = FALSE;
 }
 found[s] = TRUE;
 dis[s] = 0;
 for (int i = 0; i < n - 2; i++){
  int u = choose(dis, n, found);
  found[u] = TRUE;
  for (int w = 0; w < n; w++)
  if (!found[w])
  if (dis[u] + weight[u][w] < dis[w])
  {
   dis[w] = dis[u] + weight[u][w];
  }
 }
}

int main()
{
 shortest_path(0, MAX_VERTICES);
 return 0;
}




그리고 아래는 Floyd의 코드다.


#include <iostream>
#include <stdio.h>

using namespace std;

int arr[50][50];
int main()
{
 int N; cin >> N;
 for (int i = 1; i <= N; i++)
 for (int j = 1; j <= N; j++)
  cin >> arr[i][j];
 for (int k = 1; k <= N; k++){
  for (int i = 1; i <= N; i++){
   if (i == k) continue;
   for (int j = 1; j <= N; j++){
    if (j == i || j == k) continue;
    if (arr[i][k] + arr[k][j] < arr[i][j]){
     arr[i][j] = arr[i][k] + arr[k][j];
    }
   }
  }
 }
 return 0;
}

[Data Structure] #7-1 Graph - MST (Kruskal's Method)

신장트리(Spanning Tree)는 그래프 내의 모든 정점을 포함하는 트리를 의미한다. 쉽게 말해 모든 정점이 연결되어 있어야 한다는 말이다. 만약에 N개의 정점이 있다면 N-1개의 간선만 존재하면 신장트리가 된다. 그 중에 MST(Minimum Spanning Tree)는 간선 비용의 총합이 가장 적은 트리를 의미한다.

참고로 MST 도 결국에는 Tree다. Tree는 connected acyclic graph로 모든 정점이 연결되어 있고 사이클이 없어야 한다. MST도 이러한 Tree의 특성을 물려받았다.

MST 를 구현하는 방법으로는 Kruskal 과 Prim 알고리즘이 있다. 여기서는 Kruskal만 정리한다.

Kruskal은 Sorting + Disjoint-Sets 이다..  자세한 것은 책이나 검색을 해보자.



Kruskal's Method


#include <iostream>
#define MAX_VERTICES 100
#define INF 100

using namespace std;

int parent[MAX_VERTICES];
int num[MAX_VERTICES];

/* Union_Find */

typedef struct {
int key; // 간선의 가중치
int u; // 정점1
int v; // 정점2
} element;

void SetInit(int n)
{
for (int i = 0; i < n; i++) {
parent[i] = -1;
num[i] = 1;
}
}

int SetFind(int vertex)
{
int p, s, i;
for (i = vertex; (p = parent[i]) >= 0; i = p);
s = i; // s 는 집합의 대표 원소가 된다
for (i = vertex; (p = parent[i]) >= 0; i = p)
parent[i] = s; // 집합의 모든 원소들의 부모를 s로 설정한다
return s;
}

void SetUnion(int s1, int s2)
{
if (num[s1] < num[s2]) {
parent[s1] = s2;
num[s2] += num[s1];
}
else {
parent[s2] = s1;
num[s1] += num[s2];
}
}

/* Heap */
element h[10000];
int hsize;

void Init()
{
hsize = 0;
}

void Insert(element item)
{
int i = ++hsize;
while ((i != 1) && item.key < h[i / 2].key)
{
h[i] = h[i / 2];
i /= 2;
}
h[i] = item;
}

element Remove()
{
int p, c;
element item = h[1];
element temp = h[hsize--];
p = 1;
c = 2;
while (c <= hsize)
{
if (c < hsize && h[c].key > h[c + 1].key) c++;
if (temp.key <= h[c].key) break;
h[p] = h[c];
p = c;
c *= 2;
}
h[p] = temp;
return item;
}

void InsertHeapEdge(int u, int v, int weight)
{
element e;
e.u = u;
e.v = v;
e.key = weight;
Insert(e);
}

void InsertAllEdge()
{
InsertHeapEdge(0, 1, 29);
InsertHeapEdge(1, 2, 16);
InsertHeapEdge(2, 3, 12);
InsertHeapEdge(3, 4, 22);
InsertHeapEdge(4, 5, 27);
InsertHeapEdge(5, 0, 10);
InsertHeapEdge(6, 1, 15);
InsertHeapEdge(6, 3, 18);
InsertHeapEdge(6, 4, 25);
}

void Kruskal(int n)
{
int edge_accepted = 0; // 현재까지 선택된 간선의 수
int uset, vset; // 정점 u와 정점 v의 집합 번호
element e;

Init();
InsertAllEdge();
SetInit(n);
while (edge_accepted < (n - 1))
{
e = Remove();
uset = SetFind(e.u);
vset = SetFind(e.v);
if (uset != vset) {
printf("(%d,%d) %d \n", e.u, e.v, e.key);
edge_accepted++;
SetUnion(uset, vset);
}
}
}

int main()
{
Kruskal(7);
return 0;
}

[Algorithm] Quick Sorting

퀵소트는 알고리즘 문제를 풀 때 가장 현실적이면서도 가장 빠른 성능의 정렬 알고리즘이다. 가장 쉬운 구현 방법을 여기에 적어둔다.  내림차순으로 정렬한다.

#include <iostream>

#include <cstdio>

using namespace std;

void Swap(int &a, int &b)

{

    int temp = a;

    a = b;

    b = temp;

}

int Partition(int *list, int left, int right)

{

    int low = left;

    int high = right + 1;

    int ppos = left;

    int pval = list[ppos];

    

    do{

        do low++;

        while(low <= right && list[low] > pval);

        do high--;

        while(high >= left && list[high] < pval);

        if(low < high){

            Swap(list[low],list[high]);

            for (int i = 0; i < 5; i++)

                printf("%d ",list[i]);

            printf("\n");

        }

     }while(low < high);

    Swap(list[ppos], list[high]);

    return high;

}

void QuickSort(int *list, int left, int right)

{

    if (left < right) {

        int pivot = Partition(list, left, right);

        QuickSort(list, left, pivot - 1);

        QuickSort(list, pivot + 1, right);

    }

}

int arr[5] = {5,2,1,6,3};

int main (int argc, char *argv[])

{

    setbuf(stdout, NULL);

    QuickSort(arr, 0, 4);

    for (int i=0; i<5; i++) {

        printf("%d ",arr[i]);

    }

    printf("\n");

    return 0;

}

[Algorithm] Bit 연산

1  <<  n

 2의 n승을 의미함. 예를 들어 n = 3 이면, 1 << 3 = 8 = 2의 3승!

{1,2,3}의 모든 부분 집합의 개수를 의미하기도 함.

{ }, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} 은 8 = 2의 3승개이다.
자세한 것은 http://karmainearth.tistory.com/150

i & (1 << j)

i의 j번째 bit가 1인지를 검사한다. 

이를 이용해 모든 부분집합의 수를 출력해 볼 수 있다. 코드는 다음과 같다.

#include <iostream>

using namespace std;

int arr[3] = 

{

    1,2,3

};

void makeCandidates(int n)

{

    int k = (1 << n); 

    for(int i=0; i<k; i++)

    {   

        printf("{");

        for(int j=0; j<n; j++)

        if(i & (1 << j)) printf("%d",arr[j]);

        printf("}\n");

    }   

}

int main()

{

    makeCandidates(3);

    return 0;

}

Result

{}                                                               

{1}                                                              

{2}                                                              

{12}                                                             

{3}                                                              

{13}                                                             

{23}                                                             

{123}

집합 {1,2,3} 의 모든 부분 집합을 출력 했다. 이를 이용해 완전 검색 문제를 해결할 수도 있을 것이라 예상된다..