unordered_map이 PS하는 블로그

총점 : 100/100/0/20=220 (동상, 16.10%, 33위) 1. 뇌절 및 구현장애가 많았던 시험... 2. 코이가 점점 온라인 시험에 적응하고 있다는 생각이 들었음... 감시 & 시스템 철저 bb 3. 문자열 시러 ㅡㅡ 1번 문제 - 헬기 착륙장 헬기 착륙장은 1~k의 반지름을 갖는 k개의 동심원으로 이루어져 있으며, 각각의 원은 빨간색 또는 파란색으로 칠해짐. 반지름 i인 원을 칠하는 데에는 정확히 페인트 i통이 필요함. 빨간 페인트 a통, 파란 페인트 b통이 있을 때 만들 수 있는 헬기 착륙장 종류의 수를 출력하시오! 1번을 보자마자 아무 생각도 나지 않았다. 그래서 고민하다가 내가 1번도 못 푼다는 사실에 금이 간 멘탈에 대충 테이프를 붙이고 2번으로 향했다. 경험상 아무리 쉬운 문제여..

최대 유량 문제 (Maximum Flow) 최대 유량 문제(Maximum Flow)란 방향 그래프에서 각 간선의 용량이 정해져 있을 때, 정해진 출발점에서 도착점까지 보낼 수 있는 최대의 유량을 계산하는 문제를 말한다. 위와 같이 생긴 방향 그래프의 1번 정점에서 7번 정점까지의 최대 유량인 상황은 아래 그림과 같다. 간선에 적힌 a/b는 용량이 b인 간선에 현재 a의 유량이 흐르고 있다는 것을 말한다. 이 경우의 유량은 11이다. 더 이상의 유량이 없다는 것은 어떻게 알 수 있을까? 최소 1의 유량이 흐를 수 있는 출발점에서 도착점까지 가는 경로를 증가경로(Augmented Path)라고 한다. 위 그래프에서 증가경로는 없다는 사실을 눈으로도 쉽게 확인할 수 있으며, 임의의 그래프에 대해서도 DFS/B..

특정 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 중등부 은상 ..