알고리즘22 Divide and Conquer Square import sysinput = sys.stdin.readlinen = int(input())p = 1000000007def mul(A, B): n = len(A) Z = [[0] * n for _ in range(n)] for row in range(n): for col in range(n): e = 0 for i in range(n): e += A[row][i] * B[i][col] Z[row][col] = e%p return Zdef square(A, k): if k == 1: for x in range(len(A)): for y in rang.. 2024. 10. 14. Sieve of Eratosthenes import sysinput = sys.stdin.readlineM, N = map(int, input().split())n = Na = [False, False] + [True] * (n-1)primes = []for i in range(2, n + 1): if a[i]: primes.append(i) for j in range(2 * i, n + 1, i): a[j] = Falsefor num in primes: if num >= M: print(num) 2024. 10. 11. MST import sysinput = sys.stdin.readlinedef findParent(parent, x): if parent[x] != x: parent[x] = findParent(parent, parent[x]) return parent[x]def unionParent(parent, a, b): a = findParent(parent, a) b = findParent(parent, b) if a 2024. 10. 11. Prefix Sum, Prefix Sum of Matrix import sysinput = sys.stdin.readlineN, M = map(int, input().split())lst = list(map(int, input().split()))sum_lst = [0] * len(lst)sum_lst[0] = lst[0]for i in range(1, len(sum_lst)): sum_lst[i] = sum_lst[i - 1] + lst[i]for _ in range(M): i, j = map(int, input().split()) if i == 1: print(sum_lst[j - 1]) else: print(sum_lst[j - 1] - sum_lst[i - 2])'''2차원에서 (N1, M1) 부터 (N2, M2)까지 구간합 수식su.. 2024. 10. 11. Topology Sort from collections import dequeimport sysinput = sys.stdin.readlinev, e = map(int, input().split())indegree = [0] * (v + 1)graph = [[] for i in range(v + 1)]for _ in range(e): a, b = map(int, input().split()) graph[a].append(b) indegree[b] += 1def topology_sort(): result = [] q = deque() for i in range(1, v + 1): if indegree[i] == 0: q.append(i) while q: .. 2024. 10. 11. Segment Tree import sysinput = sys.stdin.readlineN, M, K = map(int, input().split())arr = []for _ in range(N): arr.append(int(input()))tree = [0] * (4 * N)minTree = [0] * (4 * N)maxTree = [0] * (4 * N)def init(node, start, end): if start == end: tree[node] = arr[start] return mid = (start + end) // 2 init(2 * node, start, mid) init(2 * node + 1, mid + 1, end) tree[node] = tree.. 2024. 10. 11. 이전 1 2 3 4 다음