Dev_Diary

https://www.acmicpc.net/problem/14938플로이드-워셜 알고리즘 문제입니다. 모든 노드에서 모든 노드로의 최단거리를 구해주기 위해 다익스트라가 아닌 플로이드-워셜 알고리즘을 사용합니다. 모든 최단거리를 구했다면 각 최단거리 중 도달할 수 있는 거리보다 작은 거리만 필터링해 해당하는 노드의 아이템 합을 구해 비교해주면 풀 수 있습니다.import sysinput = sys.stdin.readlinedef solution(n, m, r, items, edges): ## 플로이드-워셜 # 최단거리 리스트 min_dists = [[float('inf') for _ in range(n+1)] for __ in range(n+1)] for i in range(n+1):..

https://www.acmicpc.net/problem/14719구현 문제입니다. 해당 문제에서 가장 먼저 생각할 수 있는 풀이는 '가장 높은 위치를 찾는다' 인 것 같습니다.어차피 가장 높은 위치에는 빗물이 쌓이지도 않고, 다음으로 높은 위치와 그 사이에는 어차피 물이 가득 쌓이기 때문입니다. 즉 가장 높은 위치를 차례로 찾으면서 그 사이를 계산해주고 또 계산하지 않은 위치만 계산하면 모든 위치를 한번씩만 계산할 수 있습니다.import sysimport heapq as hqinput = sys.stdin.readlinedef solution(H, W, hs): # 높이 리스트 + 인덱스 hs_idx = [[-hs[h], h] for h in range(len(hs))] # 힙으로 만..

https://www.acmicpc.net/problem/2637위상정렬 문제입니다. 간단하게 생각해보면 DFS 나 BFS 를 사용해 한 부품씩 곱해 더해주면 될 것 같지만 단계나 부품의 수가 복잡해지고 배수가 늘어나면 시간이나 메모리가 부족해집니다. 그렇기에 조금 더 효율적으로 단계를 진행할 필요가 있습니다. 그렇기에 단계별로 개수를 병합해 한번에 곱하는 식으로 진행하면 비교적 효율적으로 진행할 수 있습니다.위 방법으로 진행할 때 모든 중간부품의 개수를 카운트하지 않았을 때 다음 단계를 계산해버리면 오류가 생기므로 중간부품의 개수가 모두 카운트 될 때 다음 단계로 넘어가야 하는데, 이 때 위상정렬을 사용할 수 있습니다. B 부품을 만들기 위해 A 부품이 필요하다고 할 때(A->B) 'B 부품 노드에 A..

https://www.acmicpc.net/problem/2638DFS / 그래프 탐색 문제입니다.주의할 점이 있다면 탐색과 동시에 치즈를 녹이는 작업을 병행하게 된다면 다음 탐색 시에 치즈가 녹은 위치를 바로 탐색하게 되어 실제 카운트에 영향이 있을 수 있습니다.import sysfrom collections import dequeinput = sys.stdin.readlinedef solution(N, M, cz_map): # 이동 방향 move_dir = [[0, 1], [0, -1], [1, 0], [-1, 0]] # 카운트 cnt = 0 # 치즈가 남지 않을 때 까지 순회 while any([any(cz) for cz in cz_map]): # 방문 ..

https://www.acmicpc.net/problem/5972단순한 다익스트라 문제입니다.준 먹이의 양을 기준으로 알고리즘을 실행하면 됩니다.import sysimport heapq as hqfrom collections import dequeinput = sys.stdin.readlinedef solution(N, M, edges): # 그래프 graph = [[] for _ in range(N+1)] for a, b, c in edges: graph[a].append([b, c]) graph[b].append([a, c]) # 최단여물 min_feeds = [float('inf') for _ in range(N+1)] min_feeds[1]..

https://www.acmicpc.net/problem/13913다익스트라 알고리즘으로 풀 수 있는 문제입니다.각 위치에서 이동할수 있는 범위와 조건에 따라 +1 / -1 / x2 중 선택해 큐에 넣어주며 최단거리를 찾아주면 풀 수 있습니다. 또한 최단시간을 구하며 경로도 기록해주어야 순회를 끝낸 후 역추적을 통해 이동 경로를 찾아낼 수 있습니다.import sysimport heapq as hqfrom collections import dequeinput = sys.stdin.readlinedef solution(N, K): # 최대 인덱스 max_idx = 150000 # 최소 도달 시간 min_times = [float('inf') for _ in range(max_idx+1..

https://www.acmicpc.net/problem/16957그냥 시뮬레이션으로 풀 수도 있지만 조금 더 효율적으로 풀 수 있는 방법이 존재합니다.생각해보면 모든 위치에 있는 공은 몇 개의 위치로 모일 수 밖에 없습니다. 울퉁불퉁한 콘크리트 바닥에 물을 뿌리면 물이 고이는 위치가 존재하는 것 처럼 다른 위치로 이동할 수 없는 위치로 공이 모두 고이게 됩니다. 해당 위치를 찾기 위해 조건에 따라 그래프를 만듭니다. 어차피 모든 노드에서 다른 노드로 이동할 수 있는 경로는 하나뿐입니다. 그러면 우리는 그래프를 사용해 공이 이동하는 경로를 알 수 있습니다. 또 B -> A 의 경로가 있고 C -> B 의 경로가 존재한다면 C -> A 의 경로로 병합된다는 점을 고려해 Union-Find 알고리즘을 사용한..

https://www.acmicpc.net/problem/11842차원 부분합 문제입니다.2차원 부분합 리스트의 값 subsum[i][j] 는 nums[0][0] ~ nums[i][j] 의 모든 수를 더한 값과 같습니다.그리고 nums[i][j] ~ nums[k][l] 까지의 합을 구하는 방법은 전체에서 부분을 빼고 겹치는 부분을 더해주는 방식으로 진행되는데 구체적으로는subsum[k][l] (전체)- subsum[k][j-1] (세로방향의 부분)- subsum[i-1][l] (가로 방향의 부분)+ subsum[i-1][j-1] (세로방향의 부분과 가로방향의 부분이 겹치는 부분) 입니다. 해당 방법을 사용해 이번 문제를 풀 수 있습니다. 우선 주어진 이익들로 부분합 리스트를 완성한 뒤 모든 겹치게 될 꼭..

https://www.acmicpc.net/problem/3671소수 판정 + 순열 문제입니다.우선 숫자가 7개까지 입력되니 10e8 이하의 소수를 모두 구해주면 됩니다.한계가 큰 만큼 에라토스테네스의 체 알고리즘을 사용하면 편하게 구할 수 있습니다. 그리고 그 중 조합할 수 있는 수를 구하는 경우는 permutation 을 통해 모든 조합을 구한 뒤 set 을 사용해 중복을 제거한 뒤 소수인지 판정해주면 되겠습니다.import sysfrom itertools import permutationsinput = sys.stdin.readline def solution(c, nums): # 7자리 이하 소수 모두 구하기 limit = 10000000 # 소수 판정 리스트 is_pri..

https://www.acmicpc.net/problem/32339최소 스패닝트리 문제입니다.엣지를 정렬할 때 도로 선호도에 따라 추가적으로 정렬을 해준 뒤 추가적인 카운트만 해주면 풀 수 있습니다. 다만 제출시에 reculson error 가 발생하니 sys.setrecursionlimit 을 이용해 적절한 수치로 제한을 조정해주어야 합니다.import syssys.setrecursionlimit(10000)input = sys.stdin.readline# union-finddef Union(group_list, n1, n2): # 그룹 g1 = Find(group_list, n1) g2 = Find(group_list, n2) # 두 그룹이 같으면 if g1 == g2: ..