전체 글121 [백준 4386번] 별자리 만들기 문제 풀이 (with Python) 크루스칼 알고리즘과 MST(최소 신장 트리) 알고리즘을 이용했다. 별자리들의 좌표를 입력받고, 그 별자리들 중 두개씩 골라 두 별사이의 거리를 계산해서 저장한다. 두 별사이의 거리가 작은 순으로 정렬한 후, 두 별의 루트 노드가 다르면 연결해준다. import sys import math input = sys.stdin.readline def find(a): # 루트 노드 찾기 if a == parent[a]: return a parent[a] = find(parent[a]) return parent[a] def union(a, b): # 두 노드 합치기 a = find(a) b = find(b) if a .. 2023. 9. 18. [백준 2887번 ] 행성 터널 문제 풀이 (with Python) 입출력은 동일하나, 메모리 초과가 뜬다. N이 100,000인데 128MB이므로 info의 메모리를 줄여야한다. import sys input = sys.stdin.readline def find(a): # 루트 노드 찾기 if a == parent[a]: return a parent[a] = find(parent[a]) return parent[a] def union(a,b): a = find(a) b = find(b) if a < b: parent[b] = a else: parent[a] = b N = int(input()) arr = [] info = [] result = 0 parent = [i for i in range(N)] for _ in .. 2023. 9. 17. [백준 6497번] 전력난 문제 풀이 (with Python) 절약할 수 있는 최대 비용의 값은 (모든 길을 연결했을 때의 비용) - (왕래할 수 있는 경로가 있는 경우의 최소 비용)을 빼면된다. 따라서, 루트 노드를 비교해 루트노드가 다르면 연결한 후, 비용을 더해 result 값에 더해주면 (왕래할 수 있는 경로가 있는 경우의 최소 비용)이 된다. z값을 모두 더한값에서 위의 값을 빼주면 된다! import sys input = sys.stdin.readline def find(x): # 루트 노드 찾는 함수 if x == parent[x]: return x else: parent[x] = find(parent[x]) return parent[x] def union(x, y): x = find(x) y = fi.. 2023. 9. 13. [백준 1674번] 도시 분할 계획 문제풀이 (with Python) 모든 마을을 연결시키는 가장 최소의 값에서 가장 큰 유지비가 드는 마을의 연결을 자르면 두 마을이 되면서 최소 유지비를 만들 수 있다. 따라서, 유지 비용이 작은 순으로 정렬하고, 루트 노드가 다를 경우 두 노드를 연결시킨다. 모든 노드를 연결한 후 가장 마지막 유지비용( 가장 큰 유지비용 )을 빼서 결과값을 도출한다. import sys input = sys.stdin.readline def find(a): if a == parent[a]: return a parent[a] = find(parent[a]) return parent[a] def union(a,b): a = find(a) b = find(b) if a < b: parent[b] = a el.. 2023. 9. 13. [백준 1922번] 네트워크 연결 문제 풀이 (with Python) 1922번: 네트워크 연결 (acmicpc.net) 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net parent = [ i for i in range(노드 수 +1) ] 로 루트 노드를 저장하는 배열을 만든다. 루트 노드가 다른 것은 연결이 안되었다는 뜻이므로, 비용이 작은 순으로 정렬하고 루트 노드가 다른 경우 연결하였다. import sys input = sys.stdin.readline def find(a): # 루트 노드 찾기 if a == parent[a]: # 루트 노드가 자신인 경우, 자기 자신 반환 return a parent[a] .. 2023. 9. 13. 이전 1 ··· 8 9 10 11 12 13 14 ··· 25 다음
