흙금이네 블로그

아이디어 덱을 이용하여 범위 내에서의 최솟값을 찾는다. 풀이 for문에서 현재 값이 덱 queue에서 가장 작은 값이 되도록 현재 값보다 큰 값들은 pop하여 없앤다. 범위를 벗어나는 값들은 popleft로 제거하는데, pop하여 남아 있지 않은 값이 있을 수 있으므로 A의 해당 값과 비교한다. res에 queue의 맨 앞에 있는 값을 문자열로 추가한 후, join 메서드로 공백으로 구분한 결과값을 출력한다. from collections import deque def solution(): N, L = map(int, input().split()) A = tuple(map(int, input().split())) queue = deque() res = [] for i in range(N): while q..

아이디어 동적 계획법으로 각 상담이 끝나는 시점의 최대 수익을 갱신해 나간다. 풀이 #1 (Python) N+1 크기의 0으로 채워진 리스트 dp를 생성하는데, dp[i]에는 i일째의 최대 수익을 저장한다. for문에서 T와 P를 입력 받아 어제 수익 dp[i]가 오늘 수익 dp[i+1]보다 큰 경우 오늘 수익에 어제 수익을 저장한다. 이번 상담이 끝나는 T-1일 후가 퇴사 전이고, 상담으로 얻는 수익이 T-1일 후의 예정 수익보다 더 크면 값을 갱신한다. import sys input = sys.stdin.readline def solution(): N = int(input()) dp = [0]*(N+1) for i in range(N): T, P = map(int, input().split()) if..

아이디어 세그먼트 트리로 구간 합을 저장해두고 변경이나 계산이 필요한 구간에 대해 빠르게 처리한다. 풀이 2042번 구간 합 구하기 문제와 유사하다. 구간 합을 계산하기 위해 N보다 크면서 가장 작은 2의 거듭제곱의 두 배 크기로 0으로 채워진 트리 리스트 tree를 만든다. 트리의 리프 노드들에는 순서대로 N개의 수를 입력 받고, for문에서 각 부모 노드에 두 자식 노드의 합을 저장한다. 이후 for문에서 x~y의 구간 합을 구하는 함수 sum_up을 호출하여 그 반환값을 출력하고, a의 위치에 해당하는 트리 리프 노드의 수를 변경한 후 함수 update를 호출한다. 이때 y에 더 큰 값이 오도록 x가 y보다 더 크다면 x와 y의 값을 서로 바꾼다. 함수 update에서는 while문을 반복하며 리프..