https://www.acmicpc.net/problem/2162문제조건N개의 선분들이 2차원 평면상에 주어져 있다. 선분은 양 끝점의 x, y 좌표로 표현이 된다.두 선분이 서로 만나는 경우에, 두 선분은 같은 그룹에 속한다고 정의하며, 그룹의 크기는 그 그룹에 속한 선분의 개수로 정의한다. 그룹의 수, 가장 크기가 큰 그룹에 속한 선분의 개수를 구하시오.접근방법 선분끼리 만나는 경우를 하나하나 모두 체크를 해줘야하는지 생각해봤다.그리고 선분끼리 교차하는 건 코드로 어떻게 나타낼지 감이 안와서 검색을통해 알아냈다.https://bowbowbow.tistory.com/17 [기하] 외적을 이용해서 선분과 선분의 교차점 구하기[기하]외적을 이용해서 선분과 선분의 교차점 구하기 목차 [기하]외적을 이용해서 ..

https://www.acmicpc.net/problem/2463문제조건가중치그래프가 존재한다.서로다른 정점 u, v에 대해서 경로가 있다면 경로가 없을때까지 최소 가중치 간선을 제거한다. u 접근방법 딱봐도 MST(최소비용신장트리)와 정말 유사하게 동작하는 문제였다. 그리디한 접근법인 Prim, Kruskal 알고리즘을 떠올렸는데, 이 알고리즘의 핵심은 서로소 분리 집합으로 초기에 모든 노드(정점)을 각각 독립적인 집합으로 초기화 시킨후, 집합이 하나가 될때까지 최소비용인 간선들을 더해가는 것이다. Kruskal 알고리즘과 이 문제의 차이점은, 최대 가중치를 가진 간선부터 그래프에 추가한다는 점이다. 간선의 가중치를 내림차순으로 정렬한다.임의의 간선부터 시작해서 정점이 속해있는 집합이 서로다른 경우에만..