nsv2 codeforces #622 div2 C2 - Skyscrapers (nsv, dp) https://codeforces.com/contest/1313/problem/C2 skyscraper 최대 5e5개 세우려고 한다. 각 건물마다 최대 높이 한도가 주어진다. 그 어떤 건물도 그 건물 기준으로 왼편, 오른편에 더 높은 건물이 둘 다 존재하지 않도록 건물을 올리려고 한다. (전체적인 모양 : non-descending - nod-increasing) 높이의 합이 최대일 때 건물들의 높이를 모두 출력하라 a[i] : 입력값. 건물의 최대 높이 한도 f[i] : 1번~i번까지 건물을 올리는데, i번 건물을 최대 높이로 하는 건물들의 높이 합. g[i] : n번~i번까지(거꾸로) 건물을 올리는데, i번 건물을 최대 높이로 하는 건물들의 높이 합. f[i]+g[i] - a[i]가 최대인 i를 가장.. 2020. 2. 25. CSES PS - nearest smaller values(NSV) https://cses.fi/problemset/task/1645/ 하나의 새로운 알고리즘, O(n) 카르테시안 트리라는 자료구조 구현의 기본 아이디어라고 함. https://wcipeg.com/wiki/All_nearest_smaller_values 영어설명 monotonic stack이라고도 함. https://www.acmicpc.net/problem/17298 다른 기본문제 최대 2e5개의 숫자를 입력받으면서, 처음부터 입력받은 그 시점까지 입력받은 숫자보다 작은 수 중에 가장 가까운 값의 인덱스를 반환하라. 1. k> n; stack s; s.push(0); for (int i = 1; i > a[i]; //입력받은 배열의 값보다 큰 값들은 없애버림 while (a[s.top()] >= a[i].. 2020. 1. 16. 이전 1 다음