Brute force Study

크루스칼 알고리즘그래프의 최소 가중치 에지를 차례대로 추가하여 MST를 구현한다.시간 복잡도 : O(E log V)주로 적은 수의 에지로 구성된 희소 그래프(sparse graph)에서 사용된다 프림 알고리즘그래프의 아무 정점부터 시작하여 MST를 구성한다가장 널리 알려진 시간 복잡도는 O(E + V log V)이다.주로 많은 수의 에지로 구성된 밀집 그래프(dense graph)에서 사용된다

이 내용에 대해선 앞으로 보완해나갈 예정입니다. 많은 문제를 풀어보면서 최대한 정리해보겠습니다.BFS vs DFSBFSBFS는 시작 정점에서 가까운 정점을 찾는데 적합하다큐를 이용하여 가까운 원소들부터 탐색하기 때문최단 거리 경로를 찾는데 적합하다.BFS에서는 특정 정점을 방문할 경우, 시작 정점에서 해당 정점까지의 최단 거리 경로가 보장된다.BFS는 현재 경계에서 인접한 모든 정점을 방문하므로 BFS에 의해 생성된 검색 트리는 짧고 넓은 편이며, 많은 메모리를 필요로 한다DFSDFS는 대체로 시작 정점에서 멀리 있는 정점을 찾을 때 적합하다.재귀적인 풀이 방식에 적합하다 (후입선출의 스택 구조를 사용하기 때문)백트래킹 방식의 PS 풀이에서 적합하다.모든 경우를 하나 하나 다 탐색해야 하는 경우 적합하다..

1. Terminal에서 다음 명령어를 입력c++ --version   2. InstalledDir에서 bin의 이전 directory로 이동cd /Library/Developer/CommandLineTools/usr/ 위 경로는 사용자 환경에 따라 다를 수 있습니다. cd 명령어 이후 나오는 경로는 1번에서 얻은 경로로 설정하면 됩니다 (3번 과정을 생략하려면 ~~~~/usr/include/로 한 번에 이동하면 됩니다) 3. usr 디렉토리에서 include 디렉토리로 이동cd include 4. include 디렉토리에서 bits 디렉토리 생성mkdir bits 5. bits 디렉토리로 이동cd bits 6. stdc++.h 파일 생성 후 편집기 열기vi stdc++.h또는vim stdc++.h Pe..