구사과

Dropbox 링크

저번에 스타트링크에서 잠깐 강의했을 때 사용했던 자료입니다. 만든 시간이 길지 않아서 자료의 질이 그렇게 좋지는 못하네요. (발표 이후 수정은 없었습니다 ㅠ)일반적인 분할 정복의 사용 예를 떠올리면서, Centroid를 지나는 전체 경로를 한번에 처리하는 것이 도움이 되는 경우가 있는지, 그러한 문제는 어떤 것들이 있는지 생각해 보시는 게 도움이 될 것 같습니다. (사실 이거는 많이 풀어봐야 압니다 ㅋㅋ)추천 문제는 딱히 생각이 안나는데 난이도 순으로 적자면 http://codeforces.com/contest/321/problem/C https://www.acmicpc.net/problem/5820 http://codeforces.com/gym/100570/problem/Fhttp://codeforce..

.. 다 정리할 생각은 없다. 그냥 어젯밤에 풀었던 문제들 정리. https://github.com/koosaga/olympiad/tree/master/POI 에서 ontak10_으로 시작하는 cpp들이 풀이이다. Highways https://www.acmicpc.net/problem/8476 결국 dfs traversal로 나타내면 2차원 평면상에 몇개의 점이 있는지를 세는 문제로 환원할 수 있다. 전형적인 2D Query 문제. main.edu.pl에서 실험해 봤을 때 O(qlg^2n)은 TLE가 났었음. O(n + (m + q)lgn)에 짜야 한다. 요 근래 2D Query는 거의 상식이 되어 가는 것 같다. 잘 해야 한다. Excursion https://www.acmicpc.net/proble..

https://sio2.mimuw.edu.pl/c/wiekuisty_ontak2015/dashboard/ http://zimpha.github.io/2015/09/23/ontak-2015-translation/ 풀 수 있는 거 다 풀어서 종결했습니다. 아인타가 paint 못푼다고 놀려서 올클 도전하기로 했습니다. 올클했습니다. 푼건 이 색깔로 표기합니다. 구현은 https://github.com/koosaga/olympiad/tree/master/POI 에서 ontak15_ 로 시작하는 파일들입니다. Day 1 cie 풀이 설명은 귀찮으니 생략. 요약하자면 왼쪽 오른쪽으로 슥슥 긁으면 풀리는데 구현은 조금 까다롭다. 굉장히 많이 틀렸었는데 이유를 알고 보니 0을 leading zero라고 무시하고 있었다..

ACM ICPC Daejeon Regional 2016에 다녀왔습니다. 당연하지만 고등학생이니 경기하러 간 건 아니고 그냥 놀러 갔습니다. 대학생이 아니라 처음에는 대회를 치르는 사람들이 정말 부러웠지만, 지금 다시 생각해보면 스트레스 안 받고 2층에서 편하게 팝콘뜯으면서 입풀이하고 중계하는게 더 꿀인거 같네요. 아는 얼굴들도 워낙 많았고 재밌는 일도 많아서 오랜만에 정말 즐거운 시간 보낼 수 있었습니다. 특히 zigui님의 코스프레가 정말 인상 깊었습니다. 대전 리저널에 새 역사를 쓰신... 총 12문제가 출제됐는데, 중계석에서 풀면서 느꼈던 점은 어렵고 재미있다는 점이었습니다. 생각에 조금 더 비중이 맞춰졌고, 재미있는 아이디어도 많았던 좋은 세트라고 생각했습니다. 물론 잘 풀었다는 건 아니고, 알고..

(OK Computer, 1997) (쓰고 싶은 건 참 많은데 요즘 너무 바쁘네요. 곧 일이 정리되면 돌아오겠습니다.)

https://granta.com/why-were-post-fact/ As his army blatantly annexed Crimea, Vladimir Putin went on TV and, with a smirk, told the world there were no Russian soldiers in Ukraine. He wasn’t lying so much as saying the truth doesn’t matter. And when Donald Trump makes up facts on a whim, claims that he saw thousands of Muslims in New Jersey cheering the Twin Towers coming down, or that the Mexica..

https://speakerdeck.com/wookayin/fast-fourier-transform-algorithmhttp://cubelover.tistory.com/12 내가 개념을 설명하기에는 위의 링크로도 충분한 것 같아서 따로 설명을 하지는 않겠다. 특히 맨 처음 인용한 ppt 슬라이드가 엄청나게 이해하기가 쉬우니 보면서 따라가는 것이 좋을 것이다. 다만 생각의 흐름 정도를 정리하자면 * 다항식을 표현하는 데 있어서는 sigma(ai * x^i) 형태의 coefficient representation과, {(x1, f(x1)), (x2, f(x2)), .. (xn, f(xn))} 형태의 point-value representation이 있다. lagrange interpolation theore..

https://www.acmicpc.net/problem/3419격자 그래프가 주어질 때, 갔던 정점을 다시 들리지 않는 조건으로 First와 Second가 번갈아 움직인다. 움직일 수 없는 사람이 질 때, 각각의 정점을 시작점으로 했을 때, 각각의 정점에서 누가 이기는지를 출력하면 된다.격자 그래프는 이분 그래프다. 정점을 두 집합으로 쪼개서, 현재 정점이 속한 집합을 A, 반대 집합을 B라고 하자. 이 문제의 답은 이분 그래프의 최대 매칭과 관련이 있다.설명을 돕기 위해, 먼저 매칭 크기 == |A| 인 경우를 생각해 보자. 이 때는 First가 A에서 매칭된 B의 정점으로만 움직여주면, 항상 이길 수 있다. B가 어떻게 움직이든간에, A 집합에 있는 정점으로 다시 가게 될 것이고, 그 정점은 매칭에..

(Single, 1985) 유투브 연관 동영상으로 엮여서 들었는데.. 하이라이트 부분의 마성의(?) 신디 소리에 빠져서 무한반복 중이다. 취향저격..