Dev_Diary

https://www.acmicpc.net/problem/2357세그먼트 트리 문제입니다.세그먼트 트리를 이용해 부분합을 구할 때 처럼 범위를 나누어 해당 범위의 부분적인 최소 / 최댓값을 구해 점차적으로 병합하며 큰 범위의 최소 / 최댓값을 구해주면 됩니다.import sysinput = sys.stdin.readline# 세그먼트 트리class SegTree: def __init__(self, nums): # 정수 리스트 self.nums = nums # 세그먼트 트리 self.segtree = [[] for _ in range(len(nums)*4)] self.partision_segtree(1, 0, len(nums)-1) ..

https://www.acmicpc.net/problem/1185최소 스패닝 트리 응용 문제입니다.크루스칼 알고리즘을 위해 엣지를 정렬할 때 기준이 되는 비용을 재설정 해주어야 합니다. 기존 알고리즘에서는 엣지의 비용만을 생각하지만 해당 문제에서 다음 노드로 갈 때 고려해야 할 비용은A -> B 엣지의 비용 + B 노드 방문비용 + B -> A 엣지의 비용 + A 노드 방문비용이기 때문에 이를 기준으로 정렬해 알고리즘을 돌리면 해결할 수 있습니다.import sysinput = sys.stdin.readline# Union-Finddef Union(root_list, node_1, node_2): # 각 노드의 루트 root_node_1 = Find(root_list, node_1) ro..

https://www.acmicpc.net/problem/9251LCS 알고리즘 기본 문제입니다. 두 문자열을 교차해 배열을 만들어준 뒤, 각 문자가 일치하는지 체크해줍니다. [i, j] 에서 문자가 일치한다면 각 문자열의 해당 문자들의 직전 문자까지의 최대 일치 수에 1 을 더해주어야 합니다. 즉 memo[i-1, j-1] + 1 이 됩니다. [i, j] 에서 문자가 일치하지 않는다면 각 문자열의 해당 문자들의 최대 일치 수 중 큰 값을 골라 적어줍니다. 즉 max(memo[i-1, j], memo[i, j-1]) 이 됩니다. 이는 공통 부분을 찾는 문제이기 때문에 단순히 일치하지 않아서 0 으로 초기화되지 않기 때문입니다.import sysinput = sys.stdin.readlinedef solu..

https://www.acmicpc.net/problem/12931단순한 계산 문제입니다.나누기는 모든 원소를 나누므로 가장 많이 나누는 경우를 구해 그 최댓값만 사용하면 됩니다.또 빼기는 각 원소마다 따로 카운트 하므로 빼는 경우를 모두 더해주면 됩니다.import sysinput = sys.stdin.readlinedef seq(num): # 카운트 div_cnt = 0 sub_cnt = 0 # 순회 while num: # 2 로 나누어 떨어지면 if not num%2: num //= 2 div_cnt += 1 # 나누어떨어지지 않으면 else: num..

https://www.acmicpc.net/problem/2042제목만 보면 부분합 알고리즘을 사용할 것 같지만 어떻게 보면 비슷한 세그먼트 트리 기본 문제입니다.세그먼트 트리는 부분합과 비슷한 부분이 있습니다. 바로 부분의 값을 미리 계산해 놓고 필요할 때 적은 계산만으로 값을 도출하는 방법이라는 점 입니다. 다만 세그먼트 트리는 중간에 수를 바꾸는 등의 작업도 보다 빠르게 할 수 있어 좀 더 유연하게 사용할 수 있다는 장점이 있습니다. 기초 세그먼트 트리는 모습은 이진트리와 유사하며 각 노드는 해당하는 범위의 합 / 곱 등 사용자가 원하는 선형 계산의 값을 보유합니다. 또 각 노드의 자식 노드의 범위는 부모 노드의 범위의 절반씩에 해당합니다.또한 세그먼트 트리의 루트 노드는 1 로 설정하는 편이 편합..

https://www.acmicpc.net/problem/15662시뮬레이션 문제입니다.주어진대로 구현만 하면 풀 수 있습니다. 회전을 용이하게 구현하기 위해 데크를 사용했습니다.회전을 시작한 톱니바퀴부터 왼쪽, 오른쪽으로 확장하며 함께 회전하는지 여부를 체크한 뒤 마지막에 회전시키는 작업을 반복해주면 풀 수 있습니다.import sysfrom collections import dequeinput = sys.stdin.readlinedef solution(T, cogs, k, rotates): # 톱니바퀴 데크로 치환 cogs = list(map(deque, cogs)) # 회전 쿼리 순회 for idx, query in rotates: # 톱니 번호 치환 ..

https://www.acmicpc.net/problem/14950전형적인 최소 스패닝 트리 알고리즘입니다.추가 비용을 계속 갱신해주며 더해주면 됩니다.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_list, n1, n2): # 그룹 g1 = Find(group_l..

https://www.acmicpc.net/problem/2381|a-c| + |b-d| 은 각 절댓값 기호 안의 부호에 따라  (a+b) - (c+d) (a>=c and b>=d) (c+d) - (a+b) (a(a-b) - (c-d) (a>=c and b(c-d) - (a-b) (a=d)로 나눌 수 있습니다. 또 이들을 관찰하면 모든 수식이 (a+b) (c+d) (a-b) (c-d) 로 이루어져 있음을 알 수 있습니다.그렇다면 모든 좌표에 대해 x+y 와 x-y 를 계산해놓고 정렬한 뒤 두 계산값들에 대한 각각의 (최댓값과 최솟값의 차) 중 큰 값을 출력하면 해답을 도출할 수 있습니다. import sysinput = sys.stdin.readlinedef solution(N, idxs): sum..

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