HTD

https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net import sys input = sys.stdin.readline def getMinAbsIndices(): left, right = 0, N-1 minAbsSum = 2000000001 minAbsIndices = [-1, -1] while left < right: curSum = nums[left] + nums[right] curAbsSum = abs(curSum) if minAbsSu..

https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net import sys input = sys.stdin.readline def getZeroPositions(): zeroPositions = [] for i in range(9): for j in range(9): if nums[i][j] == 0: zeroPositions.append((i, j)) return zeroPositions def dfs(zeroIndex): if zeroLength

https://www.acmicpc.net/problem/2166 import sys input = sys.stdin.readline def getPolygonArea(): polygonArea = 0 x0, y0 = x[0], y[0] for i in range(1, N-1): polygonArea += ( (x[i] - x0) * (y[i+1] - y0) - (x[i+1] - x0) * (y[i] - y0) ) / 2 return abs(polygonArea) if __name__ == '__main__': N = int(input()) x, y = [], [] for _ in range(N): curX, curY = list(map(int, input().split())) x.append(curX)..

https://www.acmicpc.net/problem/2098 2098번: 외판원 순회 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j www.acmicpc.net import sys input = sys.stdin.readline def getMinCost(index, isVisited): # Base Case # 모든 곳을 방문했을 경우 if isVisited == MAX_BINARY: if W[index][START_INDEX] != 0: return W[index][START_INDEX] else: return I..

https://www.acmicpc.net/problem/1806 1806번: 부분합 첫째 줄에 N (10 ≤ N = S: minLength = min(minLength, end-start) curSum -= nums[start] start += 1 elif ..

https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net import sys import itertools input = sys.stdin.readline def setValidSetCount(): global validSetCount leftSums = [] for i in range(N//2 + 1): for s in itertools.combinations(nums[:N//2], i): leftSums.app..

https://www.acmicpc.net/problem/1197 import sys input = sys.stdin.readline def find(x): if parents[x] == x: return x parents[x] = find(parents[x]) return parents[x] def union(x, y): x, y = find(x), find(y) if x < y: parents[y] = x else: parents[x] = y def getMinSpanningTreeWeight(): minSpanningTreeWeight = 0 for a, b, c in vertices: if find(a) != find(b): union(a, b) minSpanningTreeWeight += c r..

https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net import sys input = sys.stdin.readline INF = 100001 def floydWarshall(n): dp = [[INF*100]*(n+1) for _ in range(n+1)] # 초기화 for i in range(1, n+1): for j in range(1, n+1): if graph[i][j] != INF: dp[i][j] = graph[i][j] # 플로이드 ..

https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net import sys input = sys.stdin.readline def getFarthestNodeAndPrefixWeight(start, n): todo = [(start, 0)] isVisited = [False]*(n+1) farthestNode = start maxWeight = 0 while todo: node, weight = todo.pop(0) isVisite..

https://www.acmicpc.net/problem/11444 11444번: 피보나치 수 6 첫째 줄에 n이 주어진다. n은 1,000,000,000,000,000,000보다 작거나 같은 자연수이다. www.acmicpc.net import sys sys.setrecursionlimit(100000) input = sys.stdin.readline fibonacci = {0: 0, 1: 1, 2: 1} def getFibonacci(n): if not fibonacci.get(n): if n % 2 == 1: fibonacci[n] = (getFibonacci((n+1)//2)**2 + getFibonacci((n+1)//2-1)**2) % 1000000007 else: fibonacci[n] = ..