unordered_map이 PS하는 블로그

특정 DP 문제에서 다음과 같은 꼴의 식을 접할 수 있다. 보통의 경우, 각 (i, j)에 대해 모두 계산해 최솟값을 찾아줘야하므로 시간복잡도는 O(n^2)이다. 하지만 모든 j에 대해 B[j]>B[j-1]인 경우에는 시간복잡도를 O(nlogn)까지 줄일 수 있고 만약 모든 i에 대해 A[i]j이상인 모든 n에 대해서 A[i]B[j]+C[j]를 계산하는 과정은 f(x)=B[j]x+C[j]라는 고정된 일차함수의 A[i]에 대한 함숫값을 계산하는 과정과 같다는 것이다. j번째 직선을 나타내는 함수를 f_j(x)라고 하자. f_j(x) 들의 기울기인 B[j]가 점점 감소하므로 직선들은 아래와 같이 그려진다. 우리는 각각의 x에 대해 최솟값을 구해주고 싶으므로, 위 그래프에서 빨간 부분만 고려하면 된다. 빨간 ..

단절선 [BOJ 11400] (P5 & Class 6) https://www.acmicpc.net/problem/11400 11400번: 단절선 첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A www.acmicpc.net 단절선이란? 하나의 컴포넌트로 구성된 무방향 그래프에서 특정 간선을 제거했을 때 두 개 이상의 컴포넌트로 나누어지는 간선 DFS Spanning Tree 단절점을 구하는 알고리즘과 상당히 비슷하다. DFS Spanning Tree에 대한 기본적인 내용은 단절점 글을 참고! https://unorderedmap.ti..

단절점 [BOJ 11266] (P5 & Class 6) https://www.acmicpc.net/problem/11266 11266번: 단절점 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B www.acmicpc.net 단절점이란? 하나의 컴포넌트로 구성된 무방향 그래프에서 특정 정점을 제거했을 때 두 개 이상의 컴포넌트로 나누어지는 정점 위 그래프에서 빨간색 정점이 1, 6, 7이 단절점이다. 1, 6, 7 중 하나를 없애면 그래프가 2개 이상의 덩어리로 분리되기 때문이다. DFS Spanning Tree 한 그래프에서 특정 정..

경기과학고등학교 38기 서울대학교 통계학과 23학번 solved.ac : vector codeforces : unordered_map / gs20028 koistudy.net : gs20028 수상 이력 KMO 2017 중등부 1차 동상/2차 동상 KMO 2018 중등부 1차 은상/2차 은상 KMO 2020 고등부 1차(가우스부) 4등급/2차 미응시 KMO 2022 고등부 1차(가우스부) 금상/2차 미응시 KOI 2016 초등부 1차 금상/2차 은상 KOI 2020 고등부 1차 은상/2차 장려상 KOI 2021 고등부 1차 은상/2차 동상 KOI 2022 고등부 1차 은상/2차 동상 NYPC 2021 1519부문 특별상(레벨업상) NYPC 2022 1519부문 동상(9위) KPhO 2019 중등부 은상 ..