구사과

(2017.10.06 초판)(2017.10.07 Weeping Fig 문제의 해설을 보완해서 다시 작성했다.) 전대프연 2016. 분단의 슬픔최소 비용을 구하고자 한다 -> min cut과 최소 비용이 동치임을 찾는다 -> min cut으로 풀린다 류의 문제 중에서 제일 쉬운 것 같다. 이유는 간단하다. 그런 문제는 보통 풀 수 없거든source와 sink를 만들고, 그 사이에 사람들을 정점과 간선으로 적절히 이어서, source쪽 cut에 속한 정점을 A 진영 / 그렇지 않은 정점을 B 진영으로 둘 것이다. 방법은 간단하다. Min cut에 속하는 정점 집합을 $S$라 하고, 그렇지 않은 정점 집합을 $T = V\setminus S$ 라 하면, * 무조건 $S$에 들어가는 정점은 source와 $\in..

[2016.11.02 초판][2017.10.05 트리와 쿼리 7/11 추가]https://www.acmicpc.net/contest/scoreboard/195 시간이 남을때마다 하긴 했는데... 너무 힘든 연습이었다 ㅠㅠ 아주 간략하게 풀이를 설명한다. 트리와 쿼리 2 Sparse table로 level ancestor를 빠르게 구할 줄 안다면, 간단한 케이스 분석으로 풀 수 있다. 트리와 쿼리 1 / 3 Heavy Light Decomposition으로 풀 수 있다. 1번의 경우 range max segment tree, 3번의 경우 std::set으로 해결 가능하다. 어렵지 않고 개념도 유용하니 모른다면 배워보자. https://blog.anudeep2011.com/heavy-light-decompo..

(9/30 초판) (9/30 ~ 10/10 PDF 연습 문제 17/22개 해결. 나머지는 시험 끝나고 시작할 것 같습니다.) (자료 출처는 이 사이트 내부 어딘가. 난 혜아한테 받아서 잘 모른다) 수학적 귀납법이란? 어떠한 명제 $P(1), P(2), P(3), \cdots$ 가 다음 두 성질을 만족한다고 하자. * (기저 조건) $P(1)$ 이 참이다. * (귀납 조건) $n \geq 1$ 일 때, $P(1), P(2), \cdots P(n)$이 참이면, $P(n+1)$이 참이다. 그렇다면 $P(1), P(2), P(3), \cdots$가 모두 참이다. 왜? 사실 위에 적은 수학적 귀납법을 "강한 수학적 귀납법" 이라고 부르고, 조금 더 약한 폼의 수학적 귀납법을 "수학적 귀납법" 이라 한다. 진짜 "..