본문 바로가기

분류 전체보기

(402)
[백준 14428번] 수열과 쿼리 16 (Python3) import sys input = sys.stdin.readline N = int(input()) data = [*map(int,input().split())] segtree = {} def makeseg(start,end,x): if start == end: segtree[x] = start else: mid = (start+end)//2 seg1 = makeseg(start,mid,x*2) seg2 = makeseg(mid+1,end,x*2+1) if data[seg1] < data[seg2]: segtree[x] = seg1 elif data[seg2] < data[seg1]: segtree[x] = seg2 else: segtree[x] = min(seg1,seg2) return segtree[x..
[백준 11689번] GCD(n, k) = 1 (Python3) import sys input = sys.stdin.readline from math import sqrt N = int(input()) root = int(sqrt(N)) rootroot = int(sqrt(root)) sieve = {i:1 for i in range(1,root+1)} prime = [] for i in range(2,root+1): if sieve[i] == 0: continue prime.append(i) if i > rootroot: continue n = 2 while i*n
[백준 11505번] 구간 곱 구하기 (Python3) import sys input = sys.stdin.readline mod = 1000000007 N,M,K = map(int,input().split()) data = [0]*(N+1) for i in range(N): data[i] = int(input()) segtree = {} def makeseg(start,end,x): if start == end: segtree[x] = data[start] else: mid = (start+end)//2 segtree[x] = makeseg(start,mid,x*2) * makeseg(mid+1,end,x*2+1) %mod return segtree[x] makeseg(0,N-1,1) def editseg(n,c,start,end,x): if start =..
[백준 2357번] 최솟값과 최댓값 (Python3) import sys input = sys.stdin.readline N,M = map(int,input().split()) data = [0]*N for i in range(N): data[i] = int(input()) maxsegtree = {} minsegtree = {} def makemaxseg(start,end,x): if start == end: maxsegtree[x] = data[start] return maxsegtree[x] else: mid = (start+end)//2 maxsegtree[x] = max(makemaxseg(start,mid,x*2),makemaxseg(mid+1,end,x*2+1)) return maxsegtree[x] def makeminseg(start,end..
[백준 2042번] 구간 합 구하기 (Python3) import sys input = sys.stdin.readline N,M,K = map(int,input().split()) data = [0]*(N+1) for i in range(N): data[i] = int(input()) segtree = {} def makeseg(start,end,x): if start == end: segtree[x] = data[start] else: mid = (start+end)//2 segtree[x] = makeseg(start,mid,x*2) + makeseg(mid+1,end,x*2+1) return segtree[x] makeseg(0,N-1,1) def editseg(n,dif,start,end,x): segtree[x] += dif if start == ..
[백준 11437번] LCA (Python3) import sys input = sys.stdin.readline from collections import deque N = int(input()) graph = {i:[] for i in range(1,N+1)} for i in range(N-1): x1,x2 = map(int,input().split()) graph[x1].append(x2) graph[x2].append(x1) parent = {} check = {i:0 for i in range(1,N+1)} depth = {i:0 for i in range(1,N+1)} check[1] = 1 dq = deque() dq.append((1,0)) while dq: x,d = dq.pop() depth[x] = d for child in gr..
[백준 1019번] 책 페이지 (Python3) import sys input = sys.stdin.readline def page(N,n): c = len(str(N))-1 a = int(str(N)[0]) if c == 0: if n > a: return 0 else: return 1 result = a*c*10**(c-1) + page(N-a*10**c,n) if n > a: return result if n == a: return result + (N-a*10**c+1) if n == 0: return result + (c-len(str(N-a*10**c)))*(N-a*10**c+1) + 10**c return result + 10**c def zeropage(N): c = len(str(N))-1 result = 0 for i in range..
[백준 16565번] N포커 (Python3) import sys input = sys.stdin.readline mod = 10007 def cal(x,n): if n == 1: return x cal2 = cal(x,n//2) if n%2: return cal2*cal2*x return cal2*cal2 def div(x,y): return x*cal(y,mod-2)%mod def combination(n,k): numor = 1 denom = 1 for i in range(k): numor = numor*(n-i)%mod denom = denom*(i+1)%mod return div(numor,denom) def Ncard(N): result = 0 for i in range(1,N//4+1): result += combination(52-i*..