Dev_Diary

https://www.acmicpc.net/problem/18870좌표 압축 문제입니다.우선 제한시간이 2초이고 N 합니다. sort 함수의 시간 복잡도는 O(NlogN) 이기 때문입니다.다만 중복되는 수가 있을 수 있으므로 중복 제거 처리를 해준 뒤 정렬해 앞에서부터 오름차순으로 번호를 붙여 출력만 해주면 됩니다.import sysfrom collections import defaultdictinput = sys.stdin.readlinedef solution(N, nums): # 중복 수 제거 comp_nums = list(set(nums)) # 정렬 comp_nums = sorted(comp_nums) # 순회하며 압축 comp_dict = defaultdict(in..

https://www.acmicpc.net/problem/1854다익스트라 알고리즘 문제입니다. 사실 다익스트라 알고리즘보다는 우선순위 큐 문제라고 할 수 있을 것 같습니다.다익스트라의 핵심 아이디어인 '다음 노드까지 도달 시간이 현재 최단시간보다 길면 큐에 삽입하지 않는다' 를 제외하기 때문입니다. 이는 당연히 k 번째 최단 시간을 구하기 위해서는 적어도 K 번은 같은 노드를 반복해서 방문해야 하기 때문입니다.그렇게만 진행하면 우리는 크게 두 가지 해결해야 하는 과제가 생깁니다. 1. 만약 순환이 생긴다면 모든 노드를 큐에 집어넣었을 때 종료 조건이 존재하지 않습니다.좋은 예시가 바로 예제입니다.우리는 탐색을 진행하며 2 - 3 - 5 의 순환이 무한히 반복될 수 있음을 알 수 있습니다. 그렇다면 모든..

https://www.acmicpc.net/problem/13905최소 스패닝 트리 문제..인데 그보다는 크루스칼 알고리즘 문제라고 하겠습니다.최소 스패닝 트리가 아닌 최대 스패닝 트리를 구하는 과정이 포함되기 때문입니다. 크루스칼 알고리즘을 통해 최대 스패닝 트리를 구하며 s 노드와 e 노드가 연결되는 순간 병합을 중단하고 s 노드에서 e 노드로 운반할 수 있는 최대 코스트를 그래프 탐색을 통해 구해주면 됩니다.import sysfrom collections import dequeinput = sys.stdin.readline## Union-Find# Finddef Find(group_list, node): # 루트 노드가 아니면 if group_list[node] != node: ..

https://www.acmicpc.net/problem/1368최소 스패닝 트리 문제입니다. 그냥 크루스칼 알고리즘을 돌리면 되는데, 우물을 파는 비용을 고려해주어야 하기 때문에 한 가지 수정이 필요합니다. 인덱스가 N+1 인 가상의 노드를 생성한 뒤 이 노드는 '우물을 파는 가격' 에 대한 노드로 설정해줍니다. 즉 크루스칼 알고리즘을 이 N+1 노드를 포함해서 돌리게 되면 다른 노드와 연결하는 비용과 우물을 파는 비용들을 모두 합쳐 비교해 최소 비용을 계산할 수 있습니다.import sysinput = sys.stdin.readline## Union-Find# Finddef Find(group_list, node): # 루트 노드가 아니면 if group_list[node] != node:..

https://www.acmicpc.net/problem/13418최소 스패닝 트리 문제입니다.다만 그닥 추천드리고 싶지 않은 문제입니다. 문제 자체는 그냥 크루스칼 알고리즘을 두 번 사용해 풀면 되기에 어렵지는 않지만 입력과 조건이 이상하다고 생각됩니다.분명 도로의 개수 M 이라고 작성되어 있지만 당장 입력에는 M+1 개의 도로가 주어집니다.다 풀어놓고도 입력 오류를 이유로 틀린 사람이 많을 것 같습니다. 코스트와 피로도가 반전되어 있다는 점과 입력이 이상하다는 점만 유의하면 쉽게 풀 수 있습니다.import sysinput = sys.stdin.readline## Union-Find# Finddef Find(group_list, node): # 루트 노드가 아니면 if group_list[..

https://www.acmicpc.net/problem/11403플로이드-워셜 알고리즘을 사용해 풀 수 있습니다.시작 노드와 중간 노드가 연결되어있고, 중간 노드와 끝 노드가 연결되어 있으면 시작 노드와 끝 노드도 연결되어 있음을 알 수 있습니다.import sysinput = sys.stdin.readlinedef solution(N, mat): ## 플로이드-워셜 # 중간 노드 for c in range(N): # 시작 노드 for f in range(N): # 끝 노드 for b in range(N): # 시작 - 중간 / 중간 - 끝 이 이어져 있으면 if mat..

https://www.acmicpc.net/problem/16562Union-Find 알고리즘을 사용해 풀 수 있는 문제입니다. 알고리즘을 사용해 그룹을 나눈 뒤, 각 그룹에서 가장 싼 가격을 가진 친구를 선택하기만 하면 됩니다.import sysinput = sys.stdin.readline## Union-Find# Finddef Find(group_list, node): # 자신이 그룹의 대표가 아니면 if group_list[node] != node: # 재귀적으로 재탐색 group_list[node] = Find(group_list, group_list[node]) return group_list[node]# Uniondef Union(group_l..

https://www.acmicpc.net/problem/2665다익스트라 알고리즘을 사용해 풀 수 있는 문제입니다. 이동 가능한 방향을 탐색할 때, 이동할 노드가 벽이 아니라면 해당 노드를 바꿀 필요가 없기 때문에 그대로 큐에 넣어주지만, 해당 노드가 벽이라면 우선 바꾸고 이동한 것으로 간주해 큐에 넣어줍니다. 이런 식으로 탐색을 진행하면 모든 노드를 최소 변환 횟수와 함께 탐색할 수 있습니다. 큐를 최소힙으로 사용하는 이유는 바꾼 횟수가 적은 순서로 탐색을 해주기 위함인데, 바꾼 횟수가 더 많고 같은 위치를 탐색할 경우 더 적은 횟수로 먼저 탐색했기 때문에 자동으로 걸러주기 때문입니다. 최소힙이 아닌 데크를 사용할 경우, BFS처럼 풀 수도 있지만 바꾼 횟수가 높은 탐색경우가 먼저 같은 위치에 도달하..

https://www.acmicpc.net/problem/11265워셜-플로이드 알고리즘 문제입니다. 매번 다른 노드에서 다른 노드로 최단거리를 알아내야 하는 문제를 접했을 때, 다익스트라를 여러 번 사용하기 보다 한번에 모든 노드에서 모든 노드로 향하는 최단거리를 구할 때 보다 효율적인 경우가 있습니다. 그런 경우에 벨만-포드 알고리즘이나 워셜-플로이드 알고리즘을 활용할 수 있습니다.import sysinput = sys.stdin.readlinedef solution(N, M, edges, querys): ### 최단거리 업데이트 ## 플로이드-워셜 # 거쳐갈 노드 for mid in range(N): # 출발 노드 for start in range(N)..

https://www.acmicpc.net/problem/2261해당 문제는 전형적인 Closest Pair 알고리즘에 관한 문제입니다. 일반적으로 아래의 과정을 거치게 됩니다. 0. 점들을 x 값 기준으로 정렬1. 범위를 분할  1.1. 범위 내에 점이 1개면 max 를 리턴  1.2. 범위 내에 점이 2개면 해당 길이를 리턴 2. 범위 내에 점이 3 개 이상이면 위의 과정에서 나온 최솟값 + 분할된 두 범위 사이의 교차 길이 계산  2.1 교차길이는 현재 최솟값보다 길면 계산한 필요가 없음        -> 중앙에서 최솟값을 더하고 빼준 x 범위 외부의 점은 계산할 필요가 없음        (x 범위가 해당 값 외부면 무조건 교차 길이가 최솟값보다 길기 때문)  2.2 해당 범위의 값들을 y 값 기준..