조용히 끄적끄적

▣Bipartite Graph Distinction(이분 그래프 판별) : 이분그래프의 여부를 판별하는 알고리즘-> 이분 그래프 정의: 그래프의 모든 정점을 2그룹으로 나눠지고 서로 다른 그룹의 정점이 간선으로 연결되어져 있는 그래프를 이분 그래프라고 한다. : 다음 알고리즘은 위 그래프가 2분그래프인지를 확인하는 알고리즘이다. : 그림에서 볼 수 있는 것과 같이 하나의 간선에 연결된 정점은 다른 색을 가지고 있는 것을 볼 수가 있다. : 즉, BFS 혹은 DFS를 이용하여 탐색을 하며 이미 visit된 정점을 확인할 당시 자기와 같은 색을 갖고 있다면, 이분 그래프가 아님을 확인 할 수가 있다.-DFS기준-: 이런식으로 DFS의 탐색순서를 따라가며, visit 처리를 색으로 구분하게 된다. : 이미 v..

▣ Dynamic-Programming(동적계획법): 동적계획법이랑 복잡한 문제를 여러 sub-problem으로 나누어 해결하는 방법이다. ->어떻게? 해당 sub-problem의 solution들을 Table(여분의 저장공간을 필요하게 된다.)에 기록 함으로써 중복계산을 피하는 방법. 장점: 중복계산을 피하기 때문에 시간적 이점을 얻을 수 있습니다.단점: 추가적인 메모리공간을 필요로 합니다. (시간과 메모리의 trade-off) example) 피보나치 함수의 계산피보나치 함수는 Fib(n) = Fib(n-1)+Fib(n-2)(Fib(0)=1, Fib(1)=1)로 정의 할 수 있습니다.원하고자 하는 피보나치 값을 계산하기 위해서는 위 그림과같은 과정을 수행하게 되며, 보다시피 여러번의 중복계산이 되어지..

▣Breadth-First Search(너비우선탐색) : 그래프의 모든정점을 방문하는 알고리즘 중 하나이다. -> 탐색의 기준 : 자신과 인접한 모든 간선을 우선적으로 검사하며, 그 중 visit하지 않은 정점을 찾아 순차적으로 visit해 나아간다. : 더이상 visit할 정점이 없을 때 까지 반복한다. : 인전한 간선을 우선적으로 검사하기 위하여 Queue를 이용하여 준다. 현재 visit한 정점에 인접한 모든 정점을 우선적으로 수행하기 위하여 큐에 넣어준다.example)1을 visit 하면서 인접한 정점인 2, 3 그리고 7을 큐에 넣어준다.그리고 큐에 들어간 순서대로 visit하면 반복 수행해 준다.(큐의 상태가 empty가 될 때까지 반복 됨을 알 수 있다.) Tip) BFS는 pop된 ver..

▣Depth-First Search(깊이우선탐색) : 그래프의 모든정점을 방문하는 알고리즘 중 하나이다. -> 탐색의 기준 : 자신과 인접한 간선을 검사하여 visit하지 않은 정점을 찾아 visit해 나아간다. : 더이상 visit할 정점이 없을 때 까지 반복한다. 1번 정점에서 시작하여 2->3->5->7->6의 순서로 visit 가능한 정점까지 진행한다.진행이 끝나면 다른 정점이 있는 곳까지 빠져나온 후 기존의 과정을 반복한다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364#include#include#include#include#i..