Dev_Diary

https://www.acmicpc.net/problem/2110매개 변수 탐색 문제입니다. 어떠한 규칙에 따라 요소를 배치하고 답을 계산하는게 일반적인 풀이라면 해당 문제는 우선 답을 미리 정해놓고 이 답이 문제에 적합한지 확인하는 풀이 절차를 갖습니다. 일반적으로 길이가 L 인 선분 위에 C 개의 점을 배치하되 인접한 점들의 거리의 최솟값이 최대가 되게 하려면 L / (C-1) 이 그 답일 것입니다. 하지만 해당 문제의 경우 점들의 위치 후보군이 정해져 있기 때문에 이러한 방법을 사용하기는 어렵습니다. 우선 L // (C-1) 을 인접한 점들의 거리의 최솟값의 최대값이라고 가정 하겠습니다. 어떻게 배치해도 이 값을 넘을 순 없기 때문입니다. 그 뒤 최소 해당 거리만큼 떨어진 점들을 주어진 인덱스 내에..

https://www.acmicpc.net/problem/2493스택의 성질을 이용해 풀 수 있는 문제입니다. 임의의 위치에서 탑이 신호를 쏘았을 때 신호를 받는 탑은 [높이가 신호를 쏜 탑의 높이 이상이고, 신호를 쏜 탑보다 왼쪽에 위치한] 탑입니다. 그러므로 해당 조건 중 하나라도 해당하지 않는다면 문제를 푸는 데 필요가 없습니다. 즉 왼쪽에 위치한 탑 부터 하나씩 추가하고 추가될 탑의 바로 왼쪽에 있는 탑 == 가장 마지막에 추가된 탑부터 조건에 맞는지 확인하며 하나씩 제거해도 문제를 푸는데 지장이 없습니다. 점차적으로 비교 대상을 줄여가며 주어진 시간과 메모리 내에서 문제를 해결할 수 있게 됩니다.import sysinput = sys.stdin.readlinedef solution(N, heig..

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