❓문제https://www.acmicpc.net/problem/20040성능 요약메모리: 116208 KB, 시간: 292 ms분류자료 구조, 분리 집합 문제 설명사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 번호가 부여된 평면 상의 점 n 개가 주어지며, 이 중 어느 세 점도 일직선 위에 놓이지 않는다. 매 차례 마다 플레이어는 두 점을 선택해서 이를 연결하는 선분을 긋는데, 이전에 그린 선분을 다시 그을 수는 없지만 이미 그린 다른 선분과 교차하는 것은 가능하다. 게임을 진행하다가 처음으로 사이클을 완성하는 순간 게임이 종료된다. 사이클 C는 플레이어가 ..

❓문제https://www.acmicpc.net/problem/1956성능 요약메모리: 112760 KB, 시간: 2168 ms분류그래프 이론, 최단 경로, 플로이드–워셜 문제 설명V개의 마을와 E개의 도로로 구성되어 있는 도시가 있다. 도로는 마을과 마을 사이에 놓여 있으며, 일방 통행 도로이다. 마을에는 편의상 1번부터 V번까지 번호가 매겨져 있다고 하자.당신은 도로를 따라 운동을 하기 위한 경로를 찾으려고 한다. 운동을 한 후에는 다시 시작점으로 돌아오는 것이 좋기 때문에, 우리는 사이클을 찾기를 원한다. 단, 당신은 운동을 매우 귀찮아하므로, 사이클을 이루는 도로의 길이의 합이 최소가 되도록 찾으려고 한다.도로의 정보가 주어졌을 때, 도로의 길이의 합이 가장 작은 사이클을 찾는 프로그램을 작성하시..

❓문제https://www.acmicpc.net/problem/1976성능 요약메모리: 32412 KB, 시간: 40 ms분류그래프 이론, 자료 구조, 그래프 탐색, 분리 집합 문제 설명동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인지 알아보자. 물론 중간에 다른 도시를 경유해서 여행을 할 수도 있다. 예를 들어 도시가 5개 있고, A-B, B-C, A-D, B-D, E-A의 길이 있고, 동혁이의 여행 계획이 E C B C D 라면 E-A-B-C-B-C-B-D라는 여행경로를 통해 목적을 달성할 수 있다.도시들의 개수와 도시들 간의 연결 여부가 주어져 있고, 동..

❓문제https://www.acmicpc.net/problem/1717성능 요약메모리: 77876 KB, 시간: 284 ms분류자료 구조, 분리 집합문제 설명초기에 n+1n+1개의 집합 {0},{1},{2},…,{n}{0},{1},{2},…,{n}이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.집합을 표현하는 프로그램을 작성하시오.✍🏻풀이https://yoongrammer.tistory.com/102 서로소 집합(Disjoint Set) & 유니온 파인드(Union find)목차서로소 집합(Disjoint Set) & 유니온 파인드(Union find)서로소 집합(Disjoint Set)Disjoint Set(서로소 집합, 분리 집합)이란 서로..

❓문제https://www.acmicpc.net/problem/1197성능 요약Kruskal, Python3➡️메모리: 57288 KB, 시간: 264 msPrim, PyPy3➡️메모리: 129144 KB, 시간: 380 ms분류최소 스패닝 트리, 그래프 이론문제 설명그래프가 주어졌을 때, 그 그래프의 최소 스패닝 트리를 구하는 프로그램을 작성하시오.최소 스패닝 트리는, 주어진 그래프의 모든 정점들을 연결하는 부분 그래프 중에서 그 가중치의 합이 최소인 트리를 말한다.✍🏻풀이2024.11.29 - [Computer Science/Algorithms] - [Algorithms] 최소 신장 트리 (Minimum Spanning Tree) [Algorithms] 최소 신장 트리 (Minimum Spannin..

❓문제https://www.acmicpc.net/problem/13549성능 요약메모리: 115084 KB, 시간: 232 ms분류그래프 이론, 그래프 탐색, 너비 우선 탐색, 최단 경로, 데이크스트라, 0-1 너비 우선 탐색 문제 설명수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 걷는다면 1초 후에 X-1 또는 X+1로 이동하게 된다. 순간이동을 하는 경우에는 0초 후에 2*X의 위치로 이동하게 된다.수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시..