Dev_Diary

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) ..

https://www.acmicpc.net/problem/10254지난번에 포스팅한 문제와 같은 알고리즘을 사용하지만 이번에는 단순 계산으로는 시간초과가 발생하므로 회전하는 캘리퍼스 알고리즘으로 문제를 풀었습니다. 회전하는 캘리퍼스는 특정한 도형에서 가장 먼 두 꼭지점을 찾는데 아주 유용한 알고리즘입니다.어떠한 점 A 에서 가장 먼 점 B 를 구할 때 점 A 를 지나는 직선 A' 를 정하면 그 직선과 평행하고 점 B 를 지나는 직선 B' 는 항상 존재합니다. 또한 직전의 점 B- 와 점 B 를 잇는 벡터 B'- 와 점 B 와 직후의 점 B+ 를 잇는 벡터 B'+ 는 각각 B' 와 이루는 외적값의 부호가 반대입니다.즉 (B-, B) : B'- / B' 와 B' / (B, B+) : B'+ 가 이루는 외적값..

https://www.acmicpc.net/problem/9240볼록껍질 + 회전하는 캘리퍼스 문제이지만우선 볼록껍질만 구하면 단순 계산으로 모든 볼록껍질에 속하는 점들 사이의 거리를 비교해도 풀 수 있습니다. 볼록껍질의 경우 C++" data-og-description="https://www.acmicpc.net/problem/1708 1708번: 볼록 껍질 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 점의 x좌표와 y좌표가 빈 칸을 사이에 두고 주어진다. 주어지는 " data-og-host="dev-diary-0717.tistory.com" data-og-source-url="https://dev-diary-0717.tistory.com/141..