반응형 python142 [알고리즘] DFS (깊이 우선 탐색), BFS(너비 우선 탐색) 포인트 깊이 우선 탐색은 재귀를 주로 사용합니다. 저는 용어를 나누어서 사용해서 헷갈리는 부분이 많았던 것 같습니다. 깊이 우선 탐색과 너비 우선 탐색은 그렇게 다르지 않다. 사실 계속해서 알고리즘 공부를 하면서 생각이 나는 것은 사실 엄청 모르고 있는 것들이 깨어나간다라는 생각이 많이 든다. 🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. #include #include using namespace std; vector map; vector visited; int n, m; int u, v; void dfs(int x) { //기본적으로 재귀를 사용한다고 하면 생각하기 쉽다. visited[x] = true; //bfs 처럼 방문 배열 표시를 하고 cout n >> m; map.resize(n.. 2020. 12. 3. [알고리즘] 이진 변환 반복하기 포인트 1. 구현 문제와 진법 변환을 같이 한거라고 할 수 있다. 진법 변환은 생각보다 많이 쓸 수 있다. 2. string 을 사용하는 이유는 int ~ long long 범위를 만족하기 위해서 입니다. 🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. c++/cpp #include using namespace std; string n_to_2(int one){ string bin; while(one>0){ bin = to_string(one%2)+bin; one/=2; } return bin; } vector solution(string s) { vector answer; int i=0; int zero = 0; while(true){ i+=1; zero+=count(s.begin(), s.e.. 2020. 11. 6. [알고리즘] 다리를 지나는 트럭 포인트 다리를 지나는 트럭 구조체를 만들어서 다리라는 큐를 만들고 큐를 돌면서 진행을 하면 된다. 구조체를 잘 만들면 의미 분석하기 편하다. 🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. c++/cpp #include #include using namespace std; struct Car { //차로 구조체를 만들기 int weight, length; }; int solution (int bridge_length, int weight, vector truck_weights) { int answer=0; queue bridge; //weight , length int currentWeight=0; while(1) { int size=bridge.size (); for(int i=0;i 2020. 11. 4. [알고리즘] 섬 연결하기 포인트 섬을 연결을 하는 방법은 무엇인가? 모든 섬이 최소 비용으로 연결되어 있어야 한다. 최단거리가 아님을 인지하자 (최소 비용으로 연결된 MST 를 구하는 문제이다. ) 결국은 연결되는 cost 를 전부 더해주는 것입니다. MST 를 구하는 알고리즘은 크루스칼(union, find 를 사용합니다), 프림 등이 있다. (저는 프림을 애정합니다. ) 시간 복잡도 O(n^2) 을 가지고 있다. c++ 에서는 우선 순위 큐에서 greater 를 통해서 만들 수 있고, python 은 heapq 모듈을 통해서 만들 수 있다. 🧶문서는 항상 수정 될 수 있습니다. 비판은 환영합니다. 프림 알고리즘(min_heap 을 이용하여 구현) #include #include #include #include using na.. 2020. 10. 23. 이전 1 ··· 27 28 29 30 31 32 33 ··· 36 다음 반응형