Coding StudyRoom

그래프 탐색: 하나의 정점으로부터 시작하여 차례대로 모든 정점들을 한 번씩 방문하는 것 깊이 우선 탐색(DFS, Depth-Frist Search) : root node(혹은 다른 임의의 노드)에서 시작해서 다음 branch로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법 너비 우선 탐색(BFS, Breadth-First Search) : root node(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회방법

Hamiltonian Circuits (HC) Problem = Hamiltonian Path, Hamiltonian Cycle Problem Def: Given a connected, undirected graph, HC (H.tour) is a path that starts at a given vertex, visits each vertex exactly once, and ends at the starting vertex. Promising/Nonpromising fn: 1. i_th node -> (i+1)_node 지속적으로 연결되어 있어야 됨. 2. (n-1)_th node 는 출발 node (zero node)로 돌아와야 됨. 3. i_th node cannot be one of zero ~ ..

Graph Coloring Problem == Vertex Coloring Problem == m-Coloring Problem (difficult) m을 찾는 문제 - Color undirected graph with = m colors - 2 Adj. vertices must have different colors #include using namespace std; // 그래프의 vertex 개수 #define V 4 void printSolution(int color[]); // index v를 가지는 vertex와 인접한 vertex중에서 index v의 color c와 겹치는 색이 있는지 확인 bool isSafe(int v, bool graph[V][V], int color[], int c)..

a special case of 0/1 KS. (배낭 문제와 비슷) S = {item1, item2, ..., item_n} weight = {weight1, weight2, ..., weight_} W: fixed weight (Given) -> Find A (a subset of S) such that sum of weights in A equals W. Example: |S| = 5, n = 5. weight_i={5,6,10,11,16}, W=21kg. solution: {i1,i2,i3}, {i1,i5}, {i3,i4} => multiple solutions algorithms design? -> Brute-force. All enumerations of possible subsets. -> f..

Backtraking 1. DFS of a tree except that nodes are visited if promising. 2. Backtrack if NON-promising : Pruning. 3. Do a DFS of a state-space tree, checking whether each node is promising, and if it is nonpromising, backtraking to the node's parent. Design key: promising function의 설계. Analysis key: - optimality: 답이 있으면 반드시 정답을 찾는다. - time complexity: EXP (NOT poly. time) BF complexity. - 중요성: e..

* Greedy algorithm이 중요한 이유 1. 쉽고 빠른 구현: heuristic idea(경험과 지식에 기반) 2. Test-bed: baseline performance 제공. - 연구자들이 가장 먼저 접근하는 설계 전략. 3. May be "optimal" : optimal substructure - local optimal --> global optimal : proof required. ex 1. 도둑 가방(sack) -> 보석방: 보석(무게/부피, 가치) --> 보석 아이템의 일부만 담을 수 있다. (constraint) --> 도둑boss Q: optimal? highest prices? ex 2. startup company: fund raising. --> 투자가: 사업아이템, 전..

희소행렬이란? 정확한 정의는 없지만 행렬의 원소의 대부분이 0인 행렬 -> 2D matrix로 표현시에 불필요한 메모리의 낭비가 심하다. C에서 구조체를 사용하여 값으로 0이 아닌 값들만 표현이 가능 각 배열의 0번째 index의 값은 총 행, 열, 값의 수를 나타낸다. #include #include // sparse matrix typedef struct { int row;// index of row int col;// index of col double val;// value }term; // a[i,j] -> b[j,i] void transpose(term a[], term b[]) { int i, j; int curb;// current index of b b[0].row = a[0].col; ..

1번째 index부터 앞의 값들을 순차적으로 탐색하며 정렬 #include #include template void insertionSort(T arr[], const int size) { for (int i = 1; i = 0 && tmp < arr[j]; j--) { arr[j + 1] = arr[j]; } arr[j + 1] = tmp; } }

- edge들을 오름차순으로 정렬 후 edge를 기준으로 vertex를 선택하자. >> edge-based approach Pseudo_code Kruskal_MST(input G) --------------------------- Sort Edge set 'E' while NOT solved yet{ select next edge 'e': from sorted list IF cycle check: YES -> remove/pass, NO -> add 'e' // kruskal's algo.에서 중요한 부분 IF stop condition: YES-> stop, NO->repeat. } cycle check?? -> 특별한 자료구조와 동작이 필요 tree들이 여러개 존재하고 그들의 관계성을 보려고 한다...

#include #include #include #define MAX_ROW 13 #define MAX_COL 17 #define START_POINT 0 #define END_POINT 0 #define MAX_STACK_SIZE (MAX_ROW - 2) * (MAX_COL - 2) #define EXIT_ROW (MAX_ROW - 2) #define EXIT_COL (MAX_COL - 2) // declaration of maze -> // if maze[row][col] == 0 path // else if maze[row][col] == -1 block short maze[MAX_ROW][MAX_COL] = { {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1}, {1,START_PO..