2JINISHAPPY 2JINISHAPPY

#include #include #include #define INF 987654321 using namespace std; vector graph; int V, E; int prim() { vector cost(V + 1, INF); vector prev(V + 1, -1); vector visit(V + 1, false); priority_queue pq; pq.push(make_pair(0, 1)); cost[1] = 0; while (!pq.empty()) { int u = pq.top().second; pq.pop(); visit[u] = true; for (auto next : graph[u]) { int v = next.second; int weight = next.first; if (!vi..

MST를 생성하는 방법에는 Kruskal, Prim 두 가지 알고리즘이 존재한다. Kruskal 알고리즘을 빠른 시간 내에 동작하게 하려면 Union-Find 자료구조(라이브러리가 없기에 직접 구현해야함)를 사용해야 한다는 번거로움이 있지만, 여기에서 다룰 Prim's Algorithm은 priority queue를 가지고 구현할 수 있다. Prim's Algorithm을 관통하는 가장 중요한 property를 정의하고 가자. Cut Property: Edge e = (u,v)는 MST의 edge set T에 속해 있다 ↔ e는 vertex u를 포함한 어떤 vertex set S와 v를 포함한 V(G) - S를 이어주는 edge들 중 제일 cost가 작다 (오른쪽 그림, ←)MST가 위에서 설명한 e ..

이전 글에서 MST의 정의에 대해 다뤘다(2jinishappy.tistory.com/114) 이제 MST를 생성하는데 사용하는 자료구조인 Disjoint Set과 그것을 관리하는 자료구조인 Union Find에 대해 정의하고, 어떤 연산으로 MST를 만들 수 있는지 알아본다 Union Find의 대표적인 연산은 다음과 같다 1️⃣ makeSet(x): 단일 element(disjoint set)로 이루어진 set을 하나 생성한다. 2️⃣ find(x): x가 포함된 set을 return한다. 3️⃣ union(x, y): x가 포함된 set과 y가 포함된 set을 하나의 set으로 합친다. Union Find는 vertex set을 directed tree를 이용하여 저장한다. 이 때, tree의 각 n..

이전에 MST(Minimum Spanning Tree)에 대해 다룬 적이 있다. Weighted Connected Graph에서는 edge의 cost 합이 최소가 되게 하는 Subgraph(Tree)를 구성할 수 있고, 이를 MST라고 한다. 이러한 MST를 생성하는 대표적인 알고리즘으로는 Kruskal(크루스칼), Prim(프림)알고리즘이 있다. Kruskal's Algorithm(Greedy) : 그래프 G의 MST를 이루는 edge set을 T라고 가정한다. 각 step마다 T에 추가해도 cycle이 생기지 않는 edge들 중 cost가 가장 작은 edge를 T에 추가한다. 이 과정을 MST가 완성될 때 까지 반복한다. 이와 같이 T에 새로운 edge e를 추가해도 spanning tree의 성질이..

programmers.co.kr/learn/courses/30/lessons/67257 코딩테스트 연습 - 수식 최대화 IT 벤처 회사를 운영하고 있는 라이언은 매년 사내 해커톤 대회를 개최하여 우승자에게 상금을 지급하고 있습니다. 이번 대회에서는 우승자에게 지급되는 상금을 이전 대회와는 다르게 다음과 programmers.co.kr 이전에 풀었었던 수식 최대화 문제를 최근에 스터디 때문에 다시 풀게 되었다 미팅 때 너무너무 좋은 라이브러리를 알게 돼서 다시 풀어봤는데 풀이가 엄청나게 간소화되어서 다시 올린다 코딩테스트에서 사용하기 좋은 python 메소드인, permutations combinations eval이 존재한다. 이 중 permutations와 combinatiosn는 각각 from ite..

www.acmicpc.net/problem/2933 2933번: 미네랄 창영과 상근은 한 동굴을 놓고 소유권을 주장하고 있다. 두 사람은 막대기를 서로에게 던지는 방법을 이용해 누구의 소유인지를 결정하기로 했다. 싸움은 동굴에서 벌어진다. 동굴에는 미네랄 www.acmicpc.net 삼성 A형 시험과 유사한 문제 우선 예제를 살펴보면 ........ ........ .....xx. ...xxx.. ..xxx... ..x.xxx. ..x...x. .xxx..x. ........ ........ .....x.. ...xxx.. ..xxx... ..x.xxx. ..x...x. .xxx..x. ........ ........ .....x.. ...xxx.. ...xx... ..x.xxx. ..x...x. .xx..

1. node.js를 설치한다 google에 node.js를 검색한 뒤 개인 OS에 맞게 설치한다. https://nodejs.org/ko/download/ 2. 프로젝트 디렉터리에서 오른쪽 마우스를 클릭한 뒤 [Code로 열기]를 선택한다(vscode 내에서 파일 - 폴더 열기를 선택해도 됩니다). 중요한 것은 디렉터리 경로에 한글명이 들어가면 안된다!! 3. ctrl + (Shift) + `로 터미널을 연다 4. 프로젝트 폴더에 package.json이 없는 상태라면 터미널에 'npm init'을 입력한다. 이후에 나오는 정보들은 default 정보가 자동 입력된 상태이므로 계속 엔터를 눌러주면 된다. 5. 4번이 완료되었다면 'npm install @types/jquery --save'를 입력한다...

우리는 종종 Connected Component에 대해 들어보곤 한다. 주로 BFS 알고리즘 관련 문제를 풀이할 때 등장하는 개념이며, 정확하게는 maximal connected subgraph(가능한 한 connected한 모든 vertex 및 edge를 포함해야하며, 하나라도 더 추가한 순간 disconnected해야한다)를 의미한다. 여기에서 사이클에 대한 조건을 추가한 개념이 Biconnected Component(BCC)라고 할 수 있다. 위의 그림과 같은 무방향 간선 (연결) 그래프가 있다고 가정하자. 이 상태에서 vertex A 및 A와 연결된 모든 edge를 삭제하면 그래프는 (D,G,H)와 (B,C,E,F,I,J)로 분리된 disconnected graph가 된다. 이렇게 해당 그래프에서..