Dev_Diary

https://www.acmicpc.net/problem/16398최소 스패닝 트리 문제입니다.두 행성을 잇는 간선을 정리해 크루스칼 알고리즘으로 풀었습니다. import sysinput = sys.stdin.readline# union-finddef Union(group_list, n1, n2): # 그룹 g1 = Find(group_list, n1) g2 = Find(group_list, n2) # 두 그룹이 같으면 if g1 == g2: # 병합하지 않음 return False, group_list # 다르면 그룹이 작은쪽으로 병합 if g1 > g2: group_list[g1] = g2 else: ..

https://www.acmicpc.net/problem/17412네트워크 플로우 기본 문제입니다.에드몬드 카프 알고리즘으로 해결했습니다.import sysfrom collections import dequeinput = sys.stdin.readlinedef solution(N, P, edges): # 네트워크 플로우 # 1, 2 가 싱크, 소스 # 그래프 graph = [[] for _ in range(N)] # 흐를 수 있는 유량 flowable = [[0 for _ in range(N)] for __ in range(N)] for n1, n2 in edges: # 그래프 graph[n1].append(n2) graph[n..

https://www.acmicpc.net/problem/1916오랜만에 다익스트라 기초 문제입니다.노드만 잘 정리해서 다익스트라 알고리즘으로 풀면 됩니다.import sysimport heapqinput = sys.stdin.readlinedef solution(N, M, edges, s, e): ## 다익스트라 # 그래프 graph = [[] for _ in range(N+1)] for a, b, c in edges: graph[a].append([b, c]) # 최소 비용 min_cost = [float('inf') for _ in range(N+1)] min_cost[s] = 0 # 큐 q = [[0, s]] # 순회 ..

https://www.acmicpc.net/problem/5430단순한 구현 문제입니다.리스트를 뒤집는 함수를 여러 번 호출하기보다 뒤집는 함수를 호출한 횟수에 따라 앞이나 뒤에서 수를 제거해주는 편이 빠르기 때문에 deque 로 구현했습니다.import sysfrom collections import dequeinput = sys.stdin.readlinedef solution(p: str, n: int, arr: list) -> None: # 데크로 치환 arr = deque(arr) # 바뀐 횟수 R_cnt = 0 # 함수에 RR 이 있으면 원상태므로 삭제 p.replace('DD', '') # 함수 작동 for chr in p: # R ..

https://www.acmicpc.net/problem/2107정렬 문제입니다.시작하는 점 / 끝나는 점 중 하나의 점을 기준으로 정렬하면 변수가 선택하지 않은 점만 남게 되므로 수월하게 문제를 풀 수 있게 됩니다.import sysinput = sys.stdin.readlinedef solution(N, parts): # x 기준으로 정렬 parts = sorted(parts, key=lambda x: x[0]) # 가장 큰 카운트 max_cnt = 0 # 순회 for i in range(len(parts)-1): # 기준 구간 origin_e = parts[i][1] # 구간에 포함되는 수 cnt = 0 ..

https://www.acmicpc.net/problem/6497최소 스패닝 트리 문제입니다.크루스칼 알고리즘으로 풀었습니다.import sysinput = sys.stdin.readline## Union-Find# Uniondef Union(group_list, n1, n2): # 각 그룹 g1 = Find(group_list, n1) g2 = Find(group_list, n2) # 두 그룹이 같으면 if g1 == g2: # 병합하지 않음 return False, group_list # 두 그룹이 다르면 # 작은 쪽으로 병합 if g1 > g2: group_list[g1] = g2 else: ..

https://www.acmicpc.net/problem/4225볼록 껍질 문제의 응용입니다.도형이 통과할 수 있는 구멍의 최솟값을 구하라는 것은 도형의 폭 중 가장 작은 값을 찾으라는 말과 같습니다.그렇다면 도형의 폭의 최솟값은 어떻게 구해야 할까요? 1. 볼록 껍질에 속해있는 점들 사이의 거리?결론부터 말하자면 아닙니다.붉은 선이 점들을 이은 선입니다.붉은 선도 폭들의 하나이긴 하지만 하늘색 선에 비하면 길이가 긴 것을 알 수 있습니다. 2. 변에서 점 사이의 거리그림에서 힌트가 나와있습니다.볼록 껍질에 속하는 변에서 볼록껍질에 속하는 점 까지의 거리들 중 최댓값이 해당 변에서 측정한 도형의 폭 이라고 할 수 있습니다.  즉 변에서 점 사이의 거리들의 최댓값 중 최솟값을 찾으면 폭의 최솟값을 찾을 수..

https://www.acmicpc.net/problem/1774최소 스패닝 트리 문제입니다.먼저 연결된 엣지들은 미리 같은 그룹으로 묶어놓은 뒤 크루스칼 알고리즘을 돌리면 풀 수 있습니다.import syssys.setrecursionlimit(1000)input = sys.stdin.readline## Union-Find# Uniondef Union(node1, node2, group_list): # 각 노드의 그룹 group1 = Find(node1, group_list) group2 = Find(node2, group_list) # 두 그룹이 같으면 if group1 == group2: # 병합하지 않음 return False, group_lis..

https://www.acmicpc.net/problem/2887최소 스패닝 트리의 응용 문제입니다.해당 문제의 가장 큰 문제는 최소 스패닝 트리를 찾는 알고리즘 자체보다는 어떤 엣지를 타겟으로 삼아야할지 정하는 것 입니다. N==100,000 이라고 한다면 모든 엣지를 탐색하기에는 시간이 부족하거나 메모리가 부족할 것이기 때문입니다.그렇다면 어떤 엣지가 최소 스패닝 트리를 구성하는 엣지가 될 수 있는지 생각해보아야 하는데, 단순히 생각해보면 가장 인접해있는 점이 그 후보에 가장 가깝다는 것을 알 수 있습니다. 가장 거리가 가까울테고, 가장 가까운 점은 하나일테니 어떤 두 점이 연결되었다면 다른 점에 연결될 가능성이 없어 순환이 발생하지도 않습니다.다만 해당 문제에서 엣지의 코스트는 두 점의 절대적인 거..

https://www.acmicpc.net/problem/1197최소 스패닝 트리의 기초 문제입니다.크루스칼 알고리즘으로 풀었습니다.다만 ReculsionError 가 발생할 수 있으니 sys.setrecursionlimit() 함수를 사용해 재귀 제한을 올려준 뒤 메모리 제한을 대비해 Pypy 대신 Python 으로 채점하면 되겠습니다.import syssys.setrecursionlimit(100000)input = sys.stdin.readline## Union-Find# Uniondef Union(node1, node2, group_list): # 각 노드의 그룹 group1 = Find(node1, group_list) group2 = Find(node2, group_list) ..