구사과

1. Fenced In (Platinum)독특한 형태의 그래프에서 최소 스패닝 트리를 구하는 문제이다. 일반적으로 최소 스패닝 트리는 크루스칼 알고리즘을 사용해서 해결하지만, 여기서 그러한 해결 방법을 택하면, 간선의 개수가 너무 커서 시간 제한을 초과하기 때문에, 더 좋은 아이디어가 필요하다.아이디어는 크루스칼 알고리즘과 동일하다. 최소 비용으로 합쳐줄 수 있다면 합쳐주는 식이다. 다만 이 때, 하나 하나 일일이 합쳐준다기 보다는 한꺼번에 한 행 / 열을 합쳐준다는 점을 주목할 필요가 있다. 같은 행 (내지는 열) 에서 좌우로 인접한 셀들을 합치는 비용은 모두 똑같기 때문에 한 번에 생각할 수 있기 때문이다. 한 행과 한 열을 한번에 처리해 주면, O(n+m) 개의 이벤트만이 존재하기 때문에 정렬 한번..

1. Digit DivisionSi = 주어진 숫자의 i자리 prefix를 mod M으로 나눈 나머지라고 하자. Si 배열은 선형 시간에 쉽게 계산할 수 있다.주어진 숫자들을 적당히 나눈 partition이 대충 [i1 + 1, i2] / [i2 + 1, i3] / [i3 + 1, i4] / ... / [i_{k-1} + 1, i_k] 와 같이 생겼다고 하자. 물론 i1 = 0, i_k = N이다. 이 partition이 올바르려면, 모든 1 이상 k 미만의 idx에 대해서 S_{i_{idx + 1}} = S_{i_ idx} * 10 ^ (i_{idx + 1} - i_idx) (mod M)을 만족해야 한다. 이 때, S_{i1} = 0 (mod M)임을 알 수 있다. 고로 S_{i2} = 0 (mod ..

https://docs.google.com/spreadsheets/d/1-kY6uiLOo1AKSBCSjbpGRBZbIldO_3dg6oTRKIJzT-g/edit#gid=0주요 OI 문제들을 연도별로 정리해서, Google Docs 문서로 정리해 보았다. 저렇게 표까지 만든 건 IOI 2017 멘토 / 합숙 교육에서 사용하기 위함이었고, 추후 교육에서도 사용될 수 있을 것 같다. 이 표가 가장 유용할 만한 타겟은 IOI를 국가 대표 레벨에서 대비하는 학생들이라고 생각한다. 하지만, ICPC 세계 대회 등 굳이 정보올림피아드를 준비하지 않는 입장에서도 충분히 풀어볼만한 문제들이라고 생각한다. 나의 경우만 해도 여전히 저러한 문제들을 ICPC 문제들보다 우선해서 공부하고 있다.공부에 유용한 자료가 되길 바란다...