one Book a Day

떨어진 단어가 있나 없나 체크하는 문제. 단어 바뀌면 체크해주고 나중에 똑같은거 또나오면 멈춰주면 된다. 약간 구현스러운 문제 import sys input = sys.stdin.readline N = int(input()) cnt=0 for _ in range(N): chr_set = {i:0 for i in range(97,123)} word = input().rstrip() for i in range(len(word)): if chr_set[ord(word[i])]==1: break if i

처음엔 같은 레벨에 있으면 사촌인줄 알고 BFS돌렸었는데 그냥 할아버지 노드가 같으면 사촌인걸 알고 트리로 쉽게 품. import sys input = sys.stdin.readline from collections import defaultdict while 1: n,k = map(int,input().split()) if not n and not k: break arr = list(map(int,input().split())) parents = defaultdict(int) idx=0 for i in range(1,n): parents[arr[i]] = arr[idx] if i

먼가 리팩토링할 수 있을 것 같지만 이하생략.. 평범한 구현문제입니다. import sys input = sys.stdin.readline from collections import deque dx=[0,1,0,-1] dy=[1,0,-1,0] N = int(input()) K = int(input()) snake=deque() board = [[0 for _ in range(N)] for _ in range(N)] for _ in range(K): a,b = map(int,input().split()) board[a-1][b-1]=1 L = int(input()) # 최초 뱀 0,0 방향 오른쪽 snake.append([0,0]) dir=0 board[0][0]=2 t=0 commands=[] for _..

처음 진입시 area[r][c]=2.. ctrl+z누르다 없어져서 한참틀렸다. import sys input =sys.stdin.readline from collections import deque def BFS(r,c,d): queue =deque() queue.append([r,c,d]) cnt=1 # 현재 위치를 청소한다. areas[r][c]=2 while queue: x,y,dir = queue.popleft() for n_dir in ((dir-1)%4,(dir-2)%4,(dir-3)%4,dir): # 현재위치에서 왼쪽부터 차례대로 인접한 칸을 탐색한다. nx=x+dx[n_dir] # 왼쪽에 청소할공간 없다면 다시 회전 ny=y+dy[n_dir] if not areas[nx][ny]: # 청소..

절차대로 구현하는 구현문제이다. 이런게 난이도 책정은 낮게되어이쓴데 실제로 좀 그림그리는게 필요해서 체감상 어려웠다 앞으로 구현문제 많이 풀어봐야겟다는 생각을 했다 import sys input = sys.stdin.readline from collections import deque N, K = map(int, input().split()) conveier = deque() conveier.extend(list(map(int, input().split()))) robot = deque() robot.extend([0]*N) K_cnt = conveier.count(0) ans=0 while K_cnt

마지막 비교때 parent[v]==parent[u]로 썼다가 한참 틀렸다. 부모는 한칸위고 find가 루트를 찾는거라 find비교를 했어야했는데 두개의 차이에 대해 고민을 안해봤던 것 같아서 이런 문제가 생겼던 것같다. 오늘 확실히 알고간다. import sys input = sys.stdin.readline def union(a,b): #집합이 다를경우 합침 a=find(a) b=find(b) if a

매번 dp로 풀엇지만 브루트포스로도 풀린다고 한다. 처음부터 더해서 최댓값갱신. 다음 기회에는 풀어보는걸로, import sys input = sys.stdin.readline N = int(input()) T = [] P = [] dp = [] for i in range(N): a, b = map(int, input().split()) T.append(a) P.append(b) dp.append(b) dp.append(0) for i in range(N - 1, -1, -1): if i + T[i] > N: dp[i] = dp[i + 1] else: dp[i] = max(dp[i + 1], P[i] + dp[i + T[i]]) print(dp[0])

정석적인 다익스트라 문제 import sys input = sys.stdin.readline from heapq import heappop,heappush def dijkstra(start): min_dists[start] = 0 heap = [] heappush(heap,[0,start]) while heap: cur_dists, cur_node = heappop(heap) for next_node,next_dist in graph[cur_node]: if min_dists[next_node] > cur_dists + next_dist: min_dists[next_node] = cur_dists + next_dist heappush(heap,[min_dists[next_node],next_node]) ..

백준 선생님이 세그멘트트리 연습문제로 소개해주신 대표문제이다. segtree를 생성 후 구간탐색을 통해 구간합을 구한다. import sys input = sys.stdin.readline # 세그먼트 트리 생성 def init(node, start, end): # node가 leaf 노드인 경우 배열의 원소 값을 반환. if start == end : tree[node] = l[start] return tree[node] else : # 재귀함수를 이용하여 왼쪽 자식과 오른쪽 자식 트리를 만들고 합을 저장. tree[node] = init(node*2, start, (start+end)//2) + init(node*2+1, (start+end)//2+1, end) return tree[node] # 구..

이분탐색으로 종료시간을 구하고 역산해서 N직전까지 계산 후 하나씩더해주며 답을 찾는다. import sys input = sys.stdin.readline def isPossible(mid): cnt=0 for i in range(M): cnt += mid//amusement[i] + 1 if cnt >=N: return True return False # N명의 아이들 한줄 # M개의 1인승 놀이기구 # 운행시간 지나면 탑승하고 있던 아이 내리고 줄 맨앞에 있던 아이가 빈 놀이기구로 들어감. # 동시에 비어있으면 제일 앞에있는 놀이기구. N,M=map(int,input().split()) amusement = list(map(int,input().split())) start=0 end = 6e10 an..