[백준 14438번] 수열과 쿼리 17 (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] = data[start] else: mid = (start+end)//2 segtree[x] = min(makeseg(start,mid,x*2),makeseg(mid+1,end,x*2+1)) return segtree[x] def updateseg(i,v,start,end,x): if start == end: segtree[x] = v else: mid = (start+end)//2 if i
[백준 1275번] 커피숍2 (Python3)
import sys input = sys.stdin.readline N,Q = map(int,input().split()) data = [*map(int,input().split())] 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] def updateseg(n,dif,start,end,x): segtree[x] += dif if start == end: return mid = (start+end)//2 if n
[백준 1194번] 달이 차오른다, 가자. (Python3)
풀이법은 금방 생각이 났는데, 내가 기피하는 방식이 여럿 사용되어서 풀기 까다로웠던 문제다. 일단 이 문제는 비트마스킹 문제이다. 비트마스킹을 이용해서 현재 가지고 있는 Key를 저장해놓는 방식으로 풀 수 있다. 또, 3차원 visited 리스트를 이용해서 풀어야 한다. 하지만 나는 평소에 3차원 visited 리스트도 사용하기 꺼려하고 (보통 마킹하는 숫자를 바꾸는걸 선호), 비트마스킹은 공부하려다가 다음에 해야지 하고 미뤄뒀었다. 그러다 보니까 시간초과, 메모리초과, 틀렸습니다 아주 각양각색으로 제출을 실패한 끝에 겨우 성공하였다. import sys input = sys.stdin.readline from collections import deque dy = [1,-1,0,0] dx = [0,0,1..
[백준 1450번] 냅색문제 (Python3)
import sys input = sys.stdin.readline from bisect import bisect_right N,C = map(int,input().split()) data = [*map(int,input().split())] weight0 = data[:N//2] weight1 = data[N//2:] sum0 = [] sum1 = [] weight,sum = [weight0,weight1],[sum0,sum1] def DFS(s,last,i): for n in range(last+1,len(weight[i])): s += weight[i][n] sum[i].append(s) DFS(s,n,i) s -= weight[i][n] DFS(0,-1,0) DFS(0,-1,1) sum0.appe..
[백준 17472번] 다리 만들기 2 (Python3)
import sys input = sys.stdin.readline from collections import deque from heapq import heappush, heappop dy = [1,-1,0,0] dx = [0,0,1,-1] INF = 10**6 N,M = map(int,input().split()) board = [] boundary = {} for i in range(N): board.append([*map(int,input().split())]) def BFS(y,x,n): boundary[n] = [] dq = deque([(y,x)]) while dq: y,x = dq.popleft() if board[y][x] == n: continue board[y][x] = n for i..
