전체 글265 [알고리즘 정리] 최소 신장 트리(MST, Minumum Spanning Tree) 알고리즘(프림 알고리즘) 최소 신장 트리와 다익스트라 알고리즘 차이 우선 최소 신장트리에는 프림 알고리즘, 크루스칼 알고리즘 2가지 방법이 있지만 여기서는 프림 알고리즘에 대해서 알아본다. (보통 하나의 알고리즘만 알더라도 대부분의 경우 해결이 되었다.)다익스트라 알고리즘의 경우 한 노드에서 다른 노드까지 가장 작은 가중치를 가지는 경로 입니다.최소 신장 트리는 각 노드들의 가중치가 가장 작은 상태로 모든 vertex(node)를 연결하는 경로 입니다.밑에 과정을 보시면서 가장 중요한 다른 부분은 Update하는 순간 입니다. - 다익스트라의 경우 A로 부터 해당 노드까지의 경로가 더 작아지는 순간에 Update 하는 반면 - 최소 신장 트리의 경우 새로 발견된 Edge의 가중치가 기존의 가중치보다 작은 경우 Update 하게됩.. 2018. 6. 3. 백준(BOJ) 14621 나만 안되는 연애 ** # 최소 신장 트리(MST) 기본적인 최소 신장 트리에서 남자와 여자가 이어져야 한다는 점이 추가 된 문제이다. 개념 자체는 어려운 문제는 아닌 것 같은데... 많이 안 풀어 보다 보니 코드가 지저분하다.... #include #include #include #include #include #include #include #include #include #include #include #define MAX 1005 #define INF 987654321 #define MOD 1000000009 #pragma warning(disable:4996) using namespace std; typedef long long ll; typedef pair pi; typedef pair ppi; int n, m,a,.. 2018. 6. 3. [알고리즘] 비트를 이용한 시프트, 논리 연산 ( <<, >>, &, |) 시프트 연산( )시프트 연산을 이용하면 1을 오른쪽으로 5칸 또는 왼쪽으로 5칸 이동 시킬 수 있다.또한 시프트 연산한 값을 더할 수도 있다. 논리 연산( &, | ) 만약에 5개의 칸을 전부 1로 만들고 싶다면 1 2018. 6. 2. 백준(BOJ) 15787 기차가 어둠을 헤치고 은하수를 ** # 비트연산 이 문제의 경우 비트연산을 이해하고 사용할 줄 안다면 쉽게 풀 수 있는 문제이다. 푸는 과정에서 3, 4명령어의 이동 방향을 잘 못 생각하여 실수를 하였다. [알고리즘/문제 풀 때 유용한 Tip] - 비트를 이용한 시프트, 논리 연산 ( , &, |) #include #include #include #include #include #include #include #include #include #include #include #define MAX 100005 #define INF 987654321 #define MOD 1000000009 #pragma warning(disable:4996) using namespace std; typedef long long ll; typedef pair p.. 2018. 6. 2. 이전 1 ··· 36 37 38 39 40 41 42 ··· 67 다음
