one Book a Day

대놓고 bfs import sys input = sys.stdin.readline from collections import deque def bfs(start): visited[start] = True q = deque() q.append([start,'']) while q: cur_register, commands = q.popleft() if cur_register==target: return commands for command in 'DSLR': if command=='D': next_register = (cur_register*2)%10000 elif command=='S': next_register = (cur_register-1)%10000 elif command=='L': next_reg..

3차원 6방 탐색으로 바뀐 토마토 import sys input = sys.stdin.readline from collections import deque def bfs(red_tomatoes, tomato_cnt): day = -1 while red_tomatoes: n = len(red_tomatoes) for _ in range(n): x,y,z = red_tomatoes.popleft() for dx,dy,dz in d: nx = x + dx ny = y + dy nz = z + dz if 0

cnt >= N 조건 안넣어서 좀 걸 import sys input = sys.stdin.readline N = int(input()) M = int(input()) S = input().rstrip().replace('IO','*') + 'F' flag = 0 cnt = 0 ans = 0 for char in S: if flag: if char=='*': cnt += 1 else: if cnt >= N: if char=='I': ans += 1 ans += cnt - N cnt = 0 flag = 0 else: if char=='*': flag = 1 cnt += 1 print(ans)

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

트리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..

오일러 경로. 한붓그리기는 홀수인 경로가 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

최초풀이 : 브루트포스. 시작지점, 종료지점 정해놓고 안에 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): ..