PS 이야기

문제: HackerRank 이 문제는 초기 배열 [1, 2, 3, ..., n]에서 구간을 flip 하는 연산과 i번째 위치에 있는 수를 구하는 연산, 수 i의 위치를 구하는 연산에 대해 처리 빠르게 처리해야되는 문제다. Balanced Binary Search Tree라는 것이 있다. 잘 알려진 것으로는 AVL tree, Red-black tree 등등이 있다. 이러한 자료구조로 구현 된 것으로는 STL container의 set과 map이 있다. STL의 응용으로 Balanced BST를 이용해야 풀 수 있는 문제는 거의 존재하지 않는데, 이 문제는 Balanced BST 중 Splay tree라는 자료구조를 이용하면 쉽게 풀린다. Splay tree에 대한 자세한 설명은 여기를 참고한다. 간단히 소..

문제: HackerRank or hongjun7's blog 이 문제는 $N$개의 정점과 그들 사이를 잇는 $M$개의 간선이 있는 무방향성 그래프에서 $K$번째 간선 상에 임의의 점 $P$를 잡아 $P$에서 각 정점으로 가는 최단 거리들 중 최대를 최소화 시키는 문제다. 우선 직관적으로 답의 소수점은 x.0 혹은 x.5 꼴임을 알 수 있다. 실수 연산을 피하기 위해 각 간선의 길이에 2를 곱해서 처리한다. 답(최단 거리들 중 최대 값)을 정하여, 가능한지 불가능한지 결정 문제로 바꾸어 이분 검색(혹은 Parametric search)를 통해 해결한다. 답을 $d$라 정했다고 가정하고, 각 지점으로 가는 최단 거리가 $d$ 이하가 될 수 있도록 점 $P$를 잡을 수 있는지 결정하는 방법을 설명하겠다. 문제..

포함-배제의 원리(Inclusion-Exclusion Principle)란 유한 집합들의 합집합의 크기를 계산하는 기법 중 하나이다. Topcoder나 Codeforces에서 문제들을 풀다보면 포함-배제의 원리를 이용해야 시간안에 해결할 수 있는 문제들이 존재한다. 이 외에도 여러 수학적 지식을 요구하는 문제들이 종종 출제된다. 포함-배제의 원리는 원리 자체로는 중학교 수학에서 공부하여 잘 알려져 있는 편인데, 벤 다이어그램에서가 아닌 실제 문제에서 이를 응용하는 것은 꽤 까다롭게 느껴질 수 있다. 1) 집합이 두 개인 경우$|A|$를 유한 집합 $A$의 크기라고 하면, 두 유한 집합 $A$, $B$의 합집합의 크기 $|A \cup B|$는 아래와 같다. 2) 집합이 세 개인 경우세 개의 유한 집합 $A..