one Book a Day

처음에 dfs하려다 숫자 처리하기 귀찮아서 그냥 단계별로 파싱함. eval쓸수있었으면 4줄로 끝나는데 0으로 시작하는 숫자있어서 int처리 해줘야함. import sys input = sys.stdin.readline # eval쓸라그랬는데 0으로 시작하는 숫자있어서 실패.. expression = input().split('-') new_expression = [] for ex in expression: nums = ex.split('+') sum_n = 0 for num in nums: sum_n += int(num) new_expression.append(sum_n) print(2*new_expression[0] - sum(new_expression))

대놓고 플로이드 워셜이라 풀었는데 카테고리는 bfs.. bfs로 풀수있나? import sys input = sys.stdin.readline # 플로이드 워셜 탐색 N, M = map(int, input().split()) graph = [[float('inf') for _ in range(N+1)] for _ in range(N+1)] for _ in range(M): a, b = map(int, input().split()) graph[a][b] = 1 graph[b][a] = 1 for k in range(1,N+1): graph[k][k] = 0 for i in range(1,N+1): for j in range(1,N+1): if graph[i][j] > graph[i][k] + graph[k..

그냥 돌리면서 경로 담아주면되됨 import sys input = sys.stdin.readline from collections import defaultdict def DFS(v): path.append(v) check[v] = True for i in graph[v]: if check[i]==False: DFS(i) def BFS(v): queue = [v] path.append(v) check[v] = True while queue: v = queue.pop(0) for i in graph[v]: if check[i] ==False: queue.append(i) path.append(i) check[i] = True N,M,V = list(map(int,input().split())) graph ..

set정렬후 이분탐색. 그냥 정렬로도 풀수있나? import sys input = sys.stdin.readline from bisect import bisect_left N = int(input()) arr = list(map(int, input().split())) arr2 = sorted(list(set(arr))) for num in arr: print(bisect_left(arr2,num),end=' ')

dfs or bfs or disjoint-set 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 N, M = map(int, input().split()) parent = {i: i for i in range(1,N+1)} level = {i:0 for i in range(1,N+1)} for ..

가중치 기준 내림차순 정렬하고 마지막날부터 거꾸로 먹는다. import sys input = sys.stdin.readline N, T = map(int, input().split()) w_ps = [list(map(int, input().split())) for _ in range(N)] w_ps.sort(key = lambda x: x[1],reverse=True) answer = 0 for w, p in w_ps: answer += (w + p*(T-1)) T -= 1 print(answer)

다익스트라로 찾습니다. 최소거리는 늘 다익스트라 import sys input = sys.stdin.readline from collections import deque def dijkstra(start): queue = deque() queue.append([0,start]) visited = {i: float('inf') for i in range(1,N+1)} visited[start] = 0 while queue: cur_dist,cur_node = queue.popleft() for next in graph[cur_node]: if visited[next] > cur_dist+1: visited[next] = cur_dist+1 queue.append([visited[next], next]) r..

분기있는 bfs. 벽을 뿌순 횟수에 따라 분기를 나눠준다. import sys input = sys.stdin.readline from collections import deque def bfs(x,y): queue = deque() queue.append([x,y,0]) visited = [[[0]*(K+1) for _ in range(M)] for _ in range(N)] visited[x][y][0] = 1 while queue: x,y,b_cnt = queue.popleft() if x==N-1 and y==M-1: return visited[x][y][b_cnt] for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0

다익쓰 다익써야한느 이유는 최소 거리로 갱신시키면서 가야 최대한 멀리 갈 수 있기 때문. import sys input = sys.stdin.readline from heapq import heappop,heappush def dijkstra(start): heap = [] heappush(heap,[start,0]) visited = {i: float('inf') for i in range(1,n+1)} visited[start] = 0 item_check = {i: False for i in range(1,n+1)} item_check[start] = True item_cnt = items[start] while heap: cur_node, total_dist = heappop(heap) for ne..

그냥 방향 바뀌는 부분만 체크해주면 댄당 import sys input = sys.stdin.readline N = int(input()) maps = input() cnt = 1 for i in range(1,N): if maps[i]=='E': if maps[i-1]=='W': cnt +=1 print(cnt)