백준34 BOJ 11003 - 최솟값 찾기 (monotonic queue) https://www.acmicpc.net/problem/11003 풀이참고 https://jason9319.tistory.com/346 길이 n의 배열이 주어질 때, 구간 크기가 L인 모든 구간에서 순서대로 구간 최소값을 구하라 ( $n> n >> l; for (int i = 0; i a[i]; while (!dq.empty() && dq.back().first >= a[i]) dq.pop_back(); dq.push_back({ a[i], i + l }); cout 2020. 8. 12. BOJ 3392 - 화성지도 (세그트리 응용) https://www.acmicpc.net/problem/3392 코드는 다음 블로그의 코드를 많이 참조했습니다. https://jason9319.tistory.com/58 일반적인 세그트리의 형태를 따르지 않고, 세그먼트트리의 구조를 이용하여 풀 수 있는 문제. 좌표가 최대 30000인 2차원 평면 상에 최대 1e4개의 직사각형이 주어질 때, 직사각형들이 이루는 영역의 크기를 구하라 x좌표가 증가하는 순서대로 막대기들을 볼 때, "이전 x좌표와의 차 dx"와 "y좌표들의 psum이 1이상인 곳의 개수"를 곱해나가면 된다. 지금 막대기가 [y1,y2)일 떄 이 막대기가 시작 막대기인 경우 해당구간을 모두 +1, 끝 막대기인 경우 해당구간을 모두 -1해주며 배열을 유지해 나간다고 생각해야 한다. 이걸 la.. 2020. 6. 6. BOJ 1967 - 트리의 지름 https://www.acmicpc.net/problem/1967 제목이 곧 내용인 문제 트리의 지름을 구하라 https://suuntree.tistory.com/171아이디어에 대한 추가설명 임의의 점에서 제일 먼 점 u와 u에서 제일 먼 점 v사이의 길이를 구하면 된다. 어떤 점에서 제일 긴 곳까지의 길이는 어떻게 구할까? 가중치가 없는 트리에선 dfs의 깊이가 곧 길이가 된다. 이 문제는 가중치가 있는 그래프이므로 1대신 w 더해주면 된다. 모든 정점에서 이 길이의 최대를 찾으면 된다. dfs 깊이를 효과적으로 유지하려면 함수에 깊이를 의미하는 파라미터를 추가해주면 된다. dfs(u, prv, d)꼴로 한 번의 dfs로 가장 먼 점과 그때의 거리를 구할 수 있다. int n, dst, st; vec.. 2020. 2. 8. BOJ 12003 - Diamond Collector (전처리) https://www.acmicpc.net/problem/12003 유사코엔 전처리문제가 많이나온다 보석의 크기가 최대 5e4개 주어진다. 이 보석들을 두 개의 케이스에 나눠 담고 싶은데, 같은 케이스에 있는 보석의 크기 차이가 최대 K가 되도록 나누고 싶다. 최대한 보석을 전시한다면 몇개를 전시할 수 있을까? p[i] : 보석들중 크기가 a[i]~a[i]+k인 것들의 개수 pmx[i] = i~n-1번 보석 중 p[i]값의 최대 i번 보석을을 1번 케이스에 넣을 때 최대 전시 보석 수 = p[i] + pmx[i+p[i]] #include #include #define FAST ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); u.. 2020. 2. 7. 이전 1 2 3 4 ··· 9 다음
