one Book a Day

tree_dp 마지막 연습 우수마을. 기본형이다. import sys input = sys.stdin.readline sys.setrecursionlimit(10**5) def dfs(v): visited[v] = True dp[v][1] = citizen[v-1] for u in graph[v]: if not visited[u]: dfs(u) dp[v][0] += max(dp[u][0],dp[u][1]) dp[v][1] += dp[u][0] N = int(input()) citizen = list(map(int, input().split())) graph = {i: [] for i in range(1,N+1)} visited = {i: False for i in range(1,N+1)} for _ in..

브루트뽀쓰 벽좌표는 미리 담아서 검사 import sys input = sys.stdin.readline from collections import deque def move(x,y): q = deque() q.append([x,y,0]) visited[x][y] = True while q: x,y,cnt = q.popleft() if x==Fr-1 and y==Fc-1: return cnt for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0

파이썬 입출력 속도 비교. 입력속도 1 PyPy int(sys.stdin.readline()) 0.9229 2 PyPy map(int,os.read(0, 100000000).split('\n')) 1.1169 3 PyPy3 map(int,os.read(0, 100000000).decode('utf-8').split('\n')) 1.5408 4 PyPy int(raw_input()) 1.925 5 Python 3 map(int,os.read(0, 100000000).decode('utf-8').split('\n')) 4.4033 6 Python 3 int(sys.stdin.readline()) 4.4394 7 PyPy3 int(sys.stdin.readline()) 6.6291 8 Python 3 int(..

트리dp.. 아직 잘 익지는 않는다. 좀 더 연습해야할듯. import sys input =sys.stdin.readline sys.setrecursionlimit(10**6) # dp[u]는 노드 u가 루트인 subtree에서 u부터 다른 모든 노드 까지 가는 모든 경로들의 곱의 합. # 즉 (dp[v] * c) 들의 합. 그 값을 리스트 p에 저장해뒀다가 모든 값들에 대해 (dp[u] - dp[v]*c)*(c*dp[v])들의 합을 구해준다. # 그 후 중복을 제거하기 위해 나누기 2를 해줘야 하나 MOD의 반인 500000004를 곱하고 MOD로 나눔으로써 2로 나누는 것과 같은 효과를 얻을 수 있다. def dfs(u): global ans visited[u] = True p = [] for i i..

Tree DP subtree에서 구한 해를 이용해 전체 트리의 해를 구하는 방식으로 진행이 됨. dp[i] = i를 루트로 하는 서브 트리의 ~같은 식으로 DP Table을 정의. dp는 보통 선형구조에서 이루어지지만 tree는 비선형 구조기 때문에 탐색 순서를 미리 정해주는게 일반적이다. / 그래프에서 우리가 dp를 사용하듯 트리도 dp를 사용하기 충분. 탐색 순서는 보통 dfs를 돌면서 나오는 트리인 dfs트리를 기준으로 한다. 트리 dp도 대부분 상태 dp가 들어간다. ex.) dp/[i]/[j] = i는 i를 루트로하는 subtree에서 i의 상태가 j일때. 보통 i번째 노드를 루트로 하는 서브트리에서 i번째 루트 노드를 포함했을 때와 포함 하지 않았을 떄 조건 중 최적값을 가져온다. 기본 구조 ..

오일러 경로. 한붓그리기는 홀수인 경로가 2개(출발지, 도착지)거나 없어야함. dfs로도 풀수있다함. import sys input =sys.stdin.readline def find(x): if parent[x] ==x: return x parent[x] = find(parent[x]) return parent[x] def union(a,b): a = find(a) b = find(b) if level[a] >= level[b]: parent[b] = a if level[a]==level[b]: level[a] += 1 else: parent[a] = b V, E = map(int, input().split()) graph = {i: [] for i in range(1,V+1)} parent = {i:..

처음과 끝을 찾고 그 사이를 같은 간격으로 조사하는 방법. import sys input = sys.stdin.readline def check(string): l = len(string) for start_idx in range(l): if string[start_idx] == name[0]: for end_idx in range(start_idx,l): if string[end_idx]==name[-1]: avg_gap = (end_idx-start_idx)//(n-1) cnt = 0 while cnt < n: if string[start_idx+avg_gap*cnt]==name[cnt]: cnt += 1 continue break else: return 1 return 0 N = int(input(..

칠하고 지우는 방법 import sys input = sys.stdin.readline from collections import deque def remove(x,y): q = deque() q.append([x,y]) matrix[x][y] = 0 while q: x, y = q.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0

자꾸 시간초과나는데 왜 나는지 모루게따.. 알려주실분 댓글 달아주시면 감사하겠슴니다(꾸벅) idx1: color가 반환된 index idx2: nick_name이 반환된 역방향 index : n-1-index import sys input = sys.stdin.readline from collections import defaultdict class Node: def __init__(self): self.child = defaultdict(Node) self.word = False class Trie: def __init__(self): self.root = Node() def insert(self,word): node = self.root for char in word: node = node.child..

Trie 역방향, 정방향검색, 길이별 검색. class Node: def __init__(self): self.child = {} self.count = 0 class Trie: def __init__(self): self.root = Node() def insert(self,word): node = self.root for char in word: if char not in node.child: node.child[char] = Node() node.count += 1 node = node.child[char] def startswitch(self,prefix): node = self.root for char in prefix: if char=='?': return node.count if char n..