가계부(백준12837)
전형적인 세그먼트 트리 문제이다 특정 날짜에 대한 수입 혹은 지출을 입력으로 받을 때 유의해야 한다. 배열의 값을 아예 변경하면 안 되고 변화량을 더해야 한다. import sys input = sys.stdin.readline n,q =map(int, input().split()) tree = [0 for _ in range((4*n)+1)] arr = [0 for _ in range(n+1)] def change(idx, s,e,place, value): if place e : return if s==e : tree[idx]=arr[s] return mid= (s+e)//2 change(idx*2, s,mid,place, value) change(idx*2+1, mid+1,e..
음주 코딩(백준 5676)
쿼리를 통해서 곱셈의 결과를 내야하는 것이 아닌 부호만 확인하면 된다. 그래서 시간 단축을 위해서 배열의 값들을 1,-1,0으로 변경 해주면 된다. (다른 풀이를 참고 ) 그 이후의 코드는 다른 수열과 쿼리 문제들과 유사하다. import sys input = sys.stdin.readline def pon(num): if num>0: return 1 elif num e : # continue return if s==e : tree[idx] = value return mid =(s+e)//2 change(idx*2 ,s,mid, place,value) change(idx*2+1, mid+1,e,place,value) tree[idx] = tree[idx*2] * tree[idx*2+1] def find(..
수열과 쿼리37(백준 18436)
init 함수를 이용해 tree를 형성합니다. change 함수를 이용해서 tree의 수정할 부분을 수정합니다. find 함수를 이용해서 구간에 해당하는 홀수 짝수 개수를 구합니다. import sys input =sys.stdin.readline n= int(input()) originarr = [0]+ list(map(int, input().split())) arr = [[0,0,0]] for i in range(1, len(originarr)): odd,even = 0,0 if 1 : if originarr[i]%2 == 1: odd += 1 else: even += 1 arr.append((originarr[i],even,odd)) tree = [[0,0,0]for _ in range((4*n)+..
두 단계 최단 경로1(백준 23793)
파이썬의 heapq를 사용하고 다익스트라 알고리즘을 사용했다. inf로 정의된 수가 무한대가 아니기 때문에 중간 경유지를 거치고 종착지에 도달한 거리가 inf보다도 길 수가 있다는 점을 주의해야 한다. import heapq import sys input = sys.stdin.readline inf = int(2e9) n,m = map(int, input().split()) gra = [[]for i in range(n+1)] for i in range(m): a,b,c = map(int, input().split()) gra[a].append((b,c)) start,middle,end = map(int, input().split()) # print(gra) def dijk(start,middle , e..
세 번 이내에 사과를 먹자(백준 26169)
from collections import deque gra= [] for i in range(5): oneline =list(map(int, input().split())) gra.append(oneline) # print(gra) x,y= map(int, input().split()) cnt= 0 dx =[1,-1,0,0] dy =[0,0,1,-1] q =deque([]) visited =[] for i in range(5): onelines=[0,0,0,0,0] visited.append(onelines) visited[x][y]= 1 flag =0 def find(move,x, y,count): if(move==3): if(count>=2): print(1) flag = 1 # return exi..