❓문제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의 위치로 이동하게 된다.수빈이와 동생의 위치가 주어졌을 때, 수빈이가 동생을 찾을 수 있는 가장 빠른 시간이 몇 초 후인지 구하는 프로그램을 작성하시..

❓문제https://www.acmicpc.net/problem/11657성능 요약메모리: 34456 KB, 시간: 788 ms분류그래프 이론, 최단 경로, 벨만–포드문제 설명N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동을 하는 경우, C 1번 도시에서 출발해서 나머지 도시로 가는 가장 빠른 시간을 구하는 프로그램을 작성하시오.✍🏻풀이벨만 포드 알고리즘을 사용한다. 사이클을 확인은 아래 사이트를 참고하면 된다.https://growth-coder.tistory.com/2..

❓문제https://www.acmicpc.net/problem/1504성능 요약메모리: 126204 KB, 시간: 376 ms분류그래프 이론, 최단 경로, 데이크스트라문제 설명방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.✍🏻풀이우선 주어진..

❓문제https://www.acmicpc.net/problem/9655성능 요약메모리: 32544 KB, 시간: 36 ms분류수학, 다이나믹 프로그래밍, 게임 이론 문제 설명돌 게임은 두 명이서 즐기는 재밌는 게임이다.탁자 위에 돌 N개가 있다. 상근이와 창영이는 턴을 번갈아가면서 돌을 가져가며, 돌은 1개 또는 3개 가져갈 수 있다. 마지막 돌을 가져가는 사람이 게임을 이기게 된다.두 사람이 완벽하게 게임을 했을 때, 이기는 사람을 구하는 프로그램을 작성하시오. 게임은 상근이가 먼저 시작한다.✍🏻풀이N = 1 일 때는 상근이가 이긴다.N = 2 일 때는 창영이가 이긴다.N = 3 일 때는 상근이가 3개를 모두 가져가거나 1 개씩 가져가서 상근➡️창영➡️상근으로 상근이가 이긴다.이 상황으로 봤을 때 N..