one Book a Day

처음에 lca인가 봤더니 그냥 BFS. 이진트리라면 lca써야했을지도. import sys input = sys.stdin.readline from collections import deque def bfs(start,target): visited = {i: 0 for i in range(n+1)} visited[start] = 1 q = deque() q.append(start) while q: cur_node = q.popleft() if cur_node==target: return visited[cur_node] -1 for next_node in graph[cur_node]: if not visited[next_node]: visited[next_node] = visited[cur_node] + ..

브루트포쓰 import sys input = sys.stdin.readline n = int(input()) mines = [list(input().rstrip()) for _ in range(n)] maps = [list(input().rstrip()) for _ in range(n)] di = [0,0,-1,1,1,1,-1,-1] dj = [1,-1,0,0,1,-1,1,-1] flag = False for i in range(n): for j in range(n): if maps[i][j]=='x': if mines[i][j]=='*': flag = True continue cnt = 0 for k in range(8): if 0

Type Ahead input form Filter for a city or a state form 태그로 검색창을 만듭니다. 자동완성을 구현할 것임. filter로 DB에 있는 모든 검색어 중 일치하는 prefix를 가진 모든 문자열을 나열. cities DB const endpoint = "https://gist.githubusercontent.com/Miserlou/c5cd8364bf9b2420bb29/raw/2bf258763cdddd704f8ffd3ea9a3e81d25e2c6f6/cities.json"; const cities = []; fetch(endpoint) .then((blob) => blob.json()) .then((data) => cities.push(...data)); fetch로..

결국 플로이드 워셜은 어떤 경로를 통해 움직이는가? 갱신은 어떤식으로 가능한가? 결국 최초의 움직임은 직접 간선으로부터 나온다. import sys input = sys.stdin.readline n, m = map(int, input().split()) dists = [[float('inf') for _ in range(n)] for _ in range(n)] pre_node = [[0 for _ in range(n)] for _ in range(n)] for _ in range(m): a, b, c = map(int, input().split()) dists[a-1][b-1] = min(dists[a-1][b-1],c) dists[b-1][a-1] = min(dists[b-1][a-1],c) pre_..

서브트리 지우고 위에 남은게 리프가 될때도 고려 import sys input = sys.stdin.readline N = int(input()) nodes = set([i for i in range(N)]) childs = {i: [] for i in range(-1,N)} parents = list(map(int, input().split())) parent_node = set() for i in range(N): childs[parents[i]].append(i) parent_node.add(parents[i]) leafs = nodes - parent_node del_node = int(input()) q = [del_node] while q: x = q.pop() if x in leafs: le..

투포인터로 진입순서와 비교 import sys input = sys.stdin.readline N = int(input()) deaguen = [input().rstrip() for _ in range(N)] check = {car: False for car in deaguen} youngsik = [input().rstrip() for _ in range(N)] idx = 0 cnt = 0 for last in youngsik: while check[deaguen[idx]]: idx += 1 if last == deaguen[idx]: idx += 1 else: cnt += 1 check[last] = True print(cnt)

문자열 길이에 따라 생략하는 문제 import sys input = sys.stdin.readline N = int(input()) s = input().rstrip() if N

저번엔 deque로 뽑았지만 요번엔 투포인터 import sys input = sys.stdin.readline for test in range(int(input())): p = input().rstrip() n = int(input()) xi = input().rstrip()[1:-1].split(',') if not n and 'D' in p: print('error') continue reverse_x = 0 left = 0 right = len(xi)-1 for command in p: if command == 'R': reverse_x ^= 1 else: if left

전꺼를 안밟고 올꺼냐 전전꺼를 안밟고 올꺼냐? import sys input = sys.stdin.readline n = int(input()) score =[0] + [int(input()) for _ in range(n)] dp=[0,score[1]] if n >= 2: dp.append(score[1]+score[2]) if n >= 3: for i in range(3,n+1): dp.append(max(dp[i-2]+score[i],dp[i-3]+score[i]+score[i-1])) print(dp[n])

그룹나누기BFS import sys input = sys.stdin.readline from collections import deque def BFS(x,y,cnt): queue = deque() matrix[x][y] = cnt count = 1 visited[x][y] = True queue.append([x,y]) while queue: x,y = queue.popleft() for i in range(4): nx = x+dx[i] ny = y+dy[i] if 0