Peter's blog

https://m.blog.naver.com/PostView.nhn?blogId=babobigi&logNo=220479341235&proxyReferer=https%3A%2F%2Fwww.google.com%2F 그래프 자료구조는 정점(Node, Vertex)과 정점간의 관계인 간선(Edge)으로 나타낼 수 있다. G = (V, E) 경로(Path)는 정점 a에서 b로 이동할 때의 다양한 방법을 나타낸다. 위의 그래프에서 1에서 4로 이동할 경우, 1->3->4 1->2->3->4 가 존재한다. 실생활에서의 예를 들면 서울에서 부산까지 갈 때, 대구를 거쳐서 가는지, 울산을 거쳐서 가는지에 따라 경로가 달라지겠다. https://manducku.tistory.com/21 사이클(Cycle)은 a 정점에서 ..

#define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include using namespace std; vector a[1001]; // 2차원 동적배열 bool check[1001]; // 방문 플래그 void dfs(int node) { check[node] = true; for (int i = 0; i < a[node].size(); i++) { int next = a[node][i]; if (check[next] == false) { dfs(next); } } } void bfs(int start) { memset(check, false, sizeof(check)); // dfs를 수행한 후이기 때문에 초기화. check[st..

그래프의 탐색 방법 중에는 크게 깊이우선 탐색(DFS)와 너비 우선 탐색(BFS)가 있다. 이 탐색 방법들의 목적은 모든 정점을 1번씩 방문하는 것이다. DFS는 최대한 깊숙히 탐색. BFS는 최대한 넓게 탐색한다. DFS는 스택을 이용하고 BFS는 큐를 이용한다. BFS는 모든 간선의 가중치가 1일 때 최단거리를 탐색하는 알고리즘이 된다. *DFS check[i] =1 or 0 을 사용해 방문 여부를 저장한다. 시간복잡도는 인접행렬을 사용했을 때는 O(V^2), 인접리스트를 사용하면 O(V+E)이다. *BFS 시간복잡도 인접행렬 : O(V^2) 리스트: O(V+E)

버블 소트(Bubble sort)는 비록 O(n^2)급의 시간복잡도를 가지고 있지만 정말 간단한 코드를 가지고 있어 heavy-load(무거운 작업)이 아닌 이상 간단히 쓰일 수 있다. 정렬 방식이 마치 거품이 떠오르는 것과 유사하다 하여 붙여진 이름 "bubble sort". 위 예제에서는 샘플의 크기가 n=8인 자료를 정렬한다. i가 룹을 한 번 돌 때마다 j는 0부터 n-i까지 룹을 도는데, n-i까지 지정해 준 이유는, 오름차순의 경우, 밖의 룹이 한 번 돌 때마다 n-i까지는 정렬이 완료되어서 더 이상 불필요하기 때문이다. 정렬 방식은 j의 interation이 돌면서 바로 다음 index값과 비교/swap하는 방식이다. 여기서 change는 정렬이 완료되었을 때 더 이상 작업반복을 하지 않기 ..