8건의 항목
그래프 용어 V : vertex E : Edge path 연결 그래프 : 어떤 두 정점 사이에도 경로가 존재하는 그래프 부분 그래프 가중치 포함 그래프 : Edge에 가중치가 달려있음 순환 경로 순환 그래프, 비순환 그래프 트리 - 비순환, 비방향그래프 신장 트리 : 연결된, 비방향성 그래프에서 순환경로를 제거하면서 연결된 부분 그래프가 되도록 하는 트리 신장 트리의 개수는 Cayley’s formula에 따른 개수를 가짐 최소비용신장트리 신장 트리가 되는 부분 그래프 중에서 가중치가 최소가되는 부분 그래프 무조건 트리로 나온다.
골드2 : 유니언 파인드 문제이다. 생각 이런 문제는 정말 비행기가 온다고 생각하고 푸는 것이 가장 좋은 것 같다. 그러니까 모든 문제는 시뮬레이션을 제대로 하는 것이 중요. 총 5개의 게이트가 있다고 하자. 그 때, 4번으로 비행기가 들어온다.
골드4 : union find 문제이다. 풀이 기본적인 union find 문제. 코드를 기억하자.
골드4 : 유니온 파인드 문제이다. 생각 이 문제의 핵심은 갈 수 있는지 없는지를 판단하는 것이다. 처음에 그래프라고 생각하고 접근하니, dfs를 수행할 때 depth가 너무 깊어져 터질 것 같아 다른 방법으로 진행했다.
골드4 : 유니온 파인드 문제이다. 생각 문제를 이해해보자. 먼저 처음에 아무일도 하지 않을 경우에 입력된 n에 대해서 0 ~ n까지의 바구니가 생긴다. 그 다음, m개의 명령이 들어온다.
실버2 : 유니온파인드 문제이다. 풀이 유니온 파인드로 같은 집합인지 아닌지를 검증하고, 같은 집합이라면 촌수를 계산한다! 이 때 pypy로 하지말고 python3로 할 것.
골드2 : union find 문제이다. 풀이 으으 너무 아쉽다. 잘해놓고 같은 친구가 들어올 경우에 계산이 중복된다는 것을 체크하지 못했다. 그리고 지나고 보니 코드가 더러워서 다시짰다.
골드2 : 트리, 유니온파인드 문제이다. Root 찾기 흠. 입력으로 들어오는 node들이 순차적이지 않다는 점을 알아야 한다.이거 때매 시간 엄청 날렸다 즉, 랜덤으로 들어오는 그래프 정보를 가지고, 어떤 녀석이 tree의 root가 될 것인지 알아내야 한다.