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

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

1) 이분 탐색

 while (lower_bound <= upper_bound) {  
   int mid = (lower_bound + upper_bound) / 2;  
   if (test(mid) == true) {  
     answer = mid;  
     upper_bound = mid - 1;  
   } else {  
     lower_bound = mid + 1;  
   }  
 }  

2) 행렬을 이용한 그래프 표현

 int V; // 정점의 수  
 int E; // 간선의 수  
 int G[MAX_V + 1][MAX_V + 1]; // 인접행렬  
 scanf("%d", &V);  
 scanf("%d", &E);  
 for (int i = 0; i < E; ++i) {  
   int u, v;  
   scanf("%d%d", &u, &v);  
   G[u][v] = 1; // 정점 u와 v는 연결  
   G[v][u] = 1; // 정점 v와 u는 연결  
 }  

3) 행렬을 이용한 그래프 표현(가중치)

 int V; // 정점의 수  
 int E; // 간선의 수  
 int G[MAX_V + 1][MAX_V + 1]; // 인접행렬  
 scanf("%d", &V);  
 scanf("%d", &E);  
 // 인접행렬 초기화  
 for (int i = 0; i < V; ++i) {  
   for (int j = 0; j < V; ++j) {  
     G[i][j] = -1;  
   }  
   G[i][i] = 0;  
 }  
 // 간선을 입력 받아 인접행렬을 채운다  
 for (int i = 0; i < E; ++i) {  
   int u, v, w;  
   scanf("%d%d%d", &u, &v, &w);  
   G[u][v] = w;  
   G[v][u] = w;  
 }  

4) DFS - 인접행렬

 bool visited[MAX_N + 1];  
 bool finished[MAX_N + 1];  
 void DFS(int u) {  
   // 이미 방문했는지 검사  
   if (visited[u]) {  
     return;  
   }  
   // u번째 정점을 지금 방문함  
   visited[u] = true;  
   printf("%d\n", u);  
   // 인접한 정점을 방문  
   for (int v = 1; v <= N; ++v) {  
     if (v == u) continue;  
     if (A[u][v]) {  
       DFS(v);  
     }  
   }  
   // u번째 정점 방문을 마침  
   finished[u] = true;  
 }  

5) DFS

 int Y, X;  
 map[MAX_ROW + 1][MAX_COL + 1];  
 visited[MAX_ROW + 1][MAX_COL + 1];  
 void dfs(int y, int x) {  
   // 지도의 경계를 벗어나는지 검사  
   if (y < 0 || y >= Y || x < 0 || x >= X) {  
     return;  
   }  
   // 이미 방문했는지 검사  
   if (visited[y][x]) {  
     return;  
   }  
   // (y, x)를 방문  
   visited[y][x] = true;  
     
   // 인접한 칸을 방문  
   dfs(y - 1, x);  
   dfs(y, x - 1);  
   dfs(y + 1, x);  
   dfs(y, x + 1);  
 }  

6) BFS - 인접행렬

 push(int v) {  
   if (visited[v] == false) {  
     pushQueue(v);  
     visited[v] = true;  
   }  
 }  
 ...  
 push(start);  
 int step = 0;  
 while (!queueIsEmpty()) {  
   step++;  
   int queue_size = queueSize();  
   for (int i = 0; i < queue_size; ++i) {  
     int u = pop();  
     printf("%d\n", u);  
     for (int v = 1; v <= N; ++v) {  
       if (u != v && G[u][v]) {  
         push(v);  
       }  
     }  
   }  
 }  

7) BFS - 격자

 dy[] = { 1, 0, -1, 0 };  
 dx[] = { 0, 1, 0, -1 };  
 ...  
 push(startPoint);  
 int step = 0;  
 while (!queueIsEmpty()) {  
   step++;  
   int queue_size = queueSize();  
   for (int i = 0; i < queue_size; ++i) {  
     Point p = pop();  
     printf("%d %d\n", p.x, p.y);  
     for (int d = 0; d < 4; ++d) {  
       Point next;  
       next.x = p.x + dx[d];  
       next.y = p.y + dy[d];  
       push(next);  
     }  
   }  
 }  

8) BFS - 나이트

 dy[] = { 2, 1, -1, -2, -2, -1, 1, 2};  
 dx[] = { 1, 2, 2, 1, -1, -2, -2, -1};  
 ...  
 push(startPoint);  
 int step = 0;  
 while (!queueIsEmpty()) {  
   step++;  
   int queue_size = queueSize();  
   for (int i = 0; i < queue_size; ++i) {  
     Point p = pop();  
     printf("%d %d\n", p.x, p.y);  
     for (int d = 0; d < 8; ++d) {  
       Point next;  
       next.x = p.x + dx[d];  
       next.y = p.y + dy[d];  
       push(next);  
     }  
   }  
 }  

9) 플로이드 알고리즘