구사과

(첨부 자료는 발표에 사용한 슬라이드이다.) 이론전산학에서 논의되는 가장 주된 문제 중 하나는 어떠한 문제가 "쉽다" (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..

BOJ 26410. Intersection of Tangents 답은 $(min(x_i), min(y_i))$ 입니다. 이 점에서는 $x$ 축에 평행한 접선과 $y$ 축에 평행한 접선을 그을 수 있습니다. 자명하다고 볼 수도 있고, 이런 저런 복잡한 접근이 정수 점을 잘 못 찾는다는 점에서 착안할 수도 있겠습니다. BOJ 26408. Game 쿼리당 $O(n)$ 먼저, 최적 전략에서 캐릭터는 최대 한번 이동함을 관찰할 수 있습니다. 어떠한 시나리오에서 두 명 이상이 이동을 선택했다고 합시다. 전략에 의해 마지막으로 이동을 선택한 사람이 그 게임의 승자가 됩니다. 그 경우, 그 전에 이동을 선택한 사람은 본인이 결론적으로 게임을 짐에도 불구하고 이동을 선택했기 때문에 가정에 모순입니다. 두 번째로, 승자는..