one Book a Day

최초풀이 : 브루트포스. 시작지점, 종료지점 정해놓고 안에 0있으면 연산 포기 개선풀이 : stack이용 열, 행순회하며 기록해둔 높이값을 기반으로 해 높이가 높은 직사각형부터 연산. 최초풀이 import sys input = sys.stdin.readline def find_rectangle(x,y): max_size = 100 for i in range(100): if x+i >100: break for j in range(100): if y + j > 100: break max_size = max(max_size,calculate_area(x,y,x+i,y+j)) return max_size def calculate_area(x,y,h,w): cnt = 0 for i in range(x,h+1): ..

처음에 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

결국 플로이드 워셜은 어떤 경로를 통해 움직이는가? 갱신은 어떤식으로 가능한가? 결국 최초의 움직임은 직접 간선으로부터 나온다. 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()) 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

똑같이 분할정복. 출력 방식만 다름 import sys input = sys.stdin.readline def check(n,s_x,s_y): pivot = matrix[s_x][s_y] for i in range(s_x,s_x+n): for j in range(s_y,s_y+n): if matrix[i][j] != pivot: return False return True def compress_video(n,s_x,s_y): pivot = n//2 if n==1: q_tree.append(str(matrix[s_x][s_y])) return if check(n,s_x,s_y): q_tree.append(str(matrix[s_x][s_y])) return q_tree.append('(') for i i..