Dev_Diary

https://www.acmicpc.net/problem/1456소수 판정 문제입니다.주어진 범위에서 소수를 판정해 차례로 n 승해 범위내에 존재하는지 판단하면 됩니다.다만 n 은 2 이상이므로 주어진 범위의 최댓값의 제곱근까지의 소수만 판정해도 됩니다.그 이상의 소수는 거의 소수가 아닌 그냥 소수이기 때문입니다.import sysimport mathinput = sys.stdin.readlinedef soltuion(A, B): # 소수 판정 범위 right = math.ceil(pow(B, 1/2)) ## right 이하의 소수 찾기 # 소수 판별 리스트 is_primes = [False, False] + [True for _ in range(right-1)] # 소수..

https://www.acmicpc.net/problem/10423최소 스패닝 트리 응용 문제입니다.노드끼리 연결할 때 각 노드에 순환이 생길 때 뿐만 아니라 각 노드의 그룹에 발전기가 속해있는지 체크해주고 두 그룹에 모두 발전기가 속해있다면 연결하지 않으면 됩니다.import sysinput = sys.stdin.readline## Union-Find# Finddef Find(group_list, n): # 자신이 그룹의 대표가 아니면 if group_list[n] != n: # 재귀적으로 업데이트 group_list[n] = Find(group_list, group_list[n]) return group_list[n]# Uniondef Union(gro..

https://www.acmicpc.net/problem/2023소수판정 + 백트래킹 / DP 문제입니다.우리는 한 자리 소수가 2, 3, 5, 7 이라는 것을 알고있습니다.그렇다면 두 자리 신기한 소수는 2, 3, 5, 7 로 시작할 것을 알고 있고 그 수들만 소수인지 판정하면 됩니다.그런 식으로 N 자리 신기한 소수는 N-1 자리 신기한 소수로 시작하므로 점차적으로 자릿수를 늘려가며 탐색하면 됩니다. 소수를 판정할 때 모든 수로 나누어가며 판정하는 것은 비효율적이고 에라토스테네스의 체 알고리즘을 통해 최적화를 할 수 있습니다. N 자리 신기한 소수를 찾을 때 N-1 자리 소수를 보고 탐색할 필요가 없는 수를 가지치기할 수 있으므로 백트래킹 알고리즘이라고 할 수 있고, N 자리 소수를 N-1, ... ..

https://www.acmicpc.net/problem/4179BFS 로 그래프를 탐색하는 문제입니다.다만 불과 사람이 동시에 움직이는데, 같은 위치에 동시에 있으면 사람은 이동 불가이므로 불 먼저 이동시켜주면 되겠습니다.import sysfrom collections import dequeinput = sys.stdin.readlinedef solution(R, C, labyr): # 불 데크 fire_dq = deque() # 사람 데크 hum_dq = deque() # 사람 방문 목록 hum_visited = [[True for _ in range(C)] for __ in range(R)] # 미로 탐색하며 위치 체크 for i in range(R): ..

https://www.acmicpc.net/problem/7662우선순위 큐를 두 개 사용해서 풀 수 있는 문제입니다.최대힙, 최소힙 두 개를 사용해 풀 수 있는데, 문제는 이 두 힙을 동기화 시키는 것 입니다. 가장 작은 수를 최소힙을 통해 제거했다고 가정하겠습니다. 최대힙에서는 이 수를 제거한 사실이 자동으로 업데이트 되지 않습니다. 그렇다고 최대힙에서 해당 수를 찾아 제거하는 방식은 우선순위 큐를 사용하는 이점을 살릴 수 없습니다. 그렇기에 우리는 다른 방식을 찾아야 합니다. 일반적인 방법으로 쿼리의 순서를 기억해 삭제했는지 체크하는 방법이 있습니다.그래프를 탐색할 때 탐색여부를 체크하기 위해 visited 를 만드는 것 처럼 삭제한 쿼리를 기억해 최대힙 / 최소힙 에서 해당 데이터를 삭제 시 이미..

https://www.acmicpc.net/problem/14284기초 다익스트라 문제입니다.간선을 정리해 다익스트라 알고리즘을 통해 최단 거리를 찾아주면 됩니다.import sysimport heapqinput = sys.stdin.readlinedef solution(n, m, edges, s, t): # 그래프 graph = [[] for _ in range(n+1)] for a, b, c in edges: graph[a].append([b, c]) graph[b].append([a, c]) # 최소 가중치 리스트 min_weights = [float('inf') for _ in range(n+1)] # 큐 hq = [[0, s]] ..

https://www.acmicpc.net/problem/14621최소 스패닝 트리 문제입니다.Union 을 진행하기 전에 엣지의 양끝에 있는 노드가 다른 성별을 이루고 있는지만 추가적으로 확인하면 풀 수 있습니다.import sysinput = sys.stdin.readline## Union-Find# Uniondef Union(group_list, node1, node2): # 그룹 g1 = Find(group_list, node1) g2 = Find(group_list, node2) # 같은 그룹이면 if g1 == g2: # 변합하지 않음 return False, group_list # 다른 그룹이면 작은 그룹으로 병합 if g1 > ..

https://www.acmicpc.net/problem/1715먼저 합친 카드패를 연속해서 더하게 되는 방식이므로 작은 패부터 더해주는 것이 최적의 수가 되는 전형적인 그리디 알고리즘 문제입니다.다만 여러 패들 중에 더한 패를 들고 계속 더하는 것이 아닌 더한 패를 다시 패들 속에 섞고 그들 중 가장 작은 패 두개를 더하는 방식으로 여러 번 진행해야 합니다.즉 추가하고 뽑고를 반복해야 하니 효율적인 진행을 위해 우선순위큐를 사용하는 것이 합리적입니다.import sysimport heapqinput = sys.stdin.readlinedef solution(N, bundles): # 번들 리스트 힙으로 치환 heapq.heapify(bundles) # 카운트 cnt = 0 #..

https://www.acmicpc.net/problem/18405구현 문제같지만 사실 단순한 계산 문제입니다.n 초가 지난 뒤 전염될 수 있는 칸은 각 행 / 열의 위치값 차이의 합이 n 인 인덱스입니다.즉 주어진 X, Y 와 초기에 바이러스가 존재하는 칸들 중 어느 칸과 가장 가까운지 알면 무조건 해당 칸과 같은 바이러스로 감염됩니다.다만 S 초 동안은 S 칸 만큼만 바이러스가 이동할 수 있으므로 행 / 열의 위치값 차이의 합이 S 이상일 경우 바이러스가 도달할 수 없음을 주의해야 합니다.import sysinput = sys.stdin.readlinedef solution(N, K, informs, S, X, Y): # 바이러스 위치 탐색 v_idxs = [[] for _ in range..

https://www.acmicpc.net/problem/1759조합 문제입니다.문자를 정렬 후 조합시키면 조합된 문자열이 나오니 이들 중 조건에 맞는 것을 필터링하면 됩니다.import sysfrom itertools import combinationsinput = sys.stdin.readlinedef solution(L, C, chr): # 조합 for comb in combinations(chr, L): # 한 개의 모음과 두 개의 자음 m = 0 j = 0 for c in comb: if c in 'aeiou': m += 1 else: j +=..