구사과

A 단순 구현 문제. 물어보는게 복잡해서 약간의 전처리를 했다. 모든 자연수의 진약수의 합을 전처리하면 짧게 할 수 있었다. B 물어보는 게 모든 가방의 평균 중 몇 번째의 어쩌구 같은 아주 복잡한 무언가였다. 특히 가방의 개수가 많으면 사실상 관리가 불가능한 수치이다. 그런데 가방의 개수가 많으면 첫 번째 / 두 번째로 큰 가방만 남겨두고 나머지는 그냥 다 합쳐주면 된다. 그러니까 최적해에서 가방이 많지 않을 거라고 짐작할 수 있고 그 원리에 입각해서 생각하면 된다. 그런 식이었다. 더 정확하게는 기억이 나지 않는다 (...) $(K+1)/2$ 를 올림하고 내림하는 걸 헷갈려서 한번 틀렸다. C 애드혹 문제도 기출 패턴이 있고 웰노운이 있다. 이 문제 와 비슷하게 해결할 수 있다. D 재밌게 풀었다. ..

(첨부 자료는 발표에 사용한 슬라이드이다.) 이론전산학에서 논의되는 가장 주된 문제 중 하나는 어떠한 문제가 "쉽다" (algorithm) 내지는 "어렵다" (hardness) 는 논의이다. 쉽다는 것을 증명하려면, 효율적인 알고리즘을 찾아 빠르게 해결하면 된다 (constructive proof). 대단히 명료하고, 알고리즘 대회를 통해서 많이 연습되는 방법이기도 하다. 어렵다는 것을 증명하는 것은 쉽다를 증명하는 것만큼 명료하지 않다. $P=NP$ 가설이 오랜 난제로 남아있는 것도 "어려움을 증명하는" 쉬운 방법을 찾지 못해서라고 볼 수 있다. 통상적으로는, 가장 대표성있는 문제를 잡아서 "어떠한 문제는 풀 수 없다" 라는 가설을 만들고, 이 문제가 풀렸을 때 다른 문제를 풀 수 있는 알고리즘을 고안..

이 글에서는 Monika Henzinger, Andrea Lincoln, Stefan Neumann, Virginia Vassilevska Williams의 Conditional Hardness for Sensitivity Problems 라는 논문을 요약한다. 이론 전산에서 Dynamic algorithm은, 입력 데이터에 작은 변화가 점진적으로 가해지더라도 데이터에 대해 물어볼 수 있는 특정한 문제들의 답을 그대로 보존하는 알고리즘을 뜻한다. 예를 들어서, 그래프의 "연결성" (connectivity) 를 보존하는 dynamic algorithm은 입력 그래프에 간선 추가와 제거가 이루어질 때 $s - t$ 간에 경로가 있는지 여부의 쿼리를 반환할 수 있다. 최근 이루어진 여러 연구를 통해서 Dyna..