서론

알고리즘 문제를 풀 때 랜덤을 사용해 문제를 해결하는 경우가 있습니다.
최악의 시간 복잡도와 평균 시간 복잡도가 많이 차이나는 알고리즘을 사용하는 경우에 최악의 상황을 피할 때 사용하기도 하고, 무작위 선택을 여러 번 시도하는 것으로 틀릴 확률을 줄이는 용도로 사용하기도 합니다.
이 글에서는 랜덤을 이용해 여러가지 문제를 통해 문제 풀이에 랜덤을 적용하는 방법을 다룹니다.

문제 링크

• http://icpc.me/5257

문제 링크

• http://icpc.me/16124

문제 링크

• http://icpc.me/18798

문제 링크

• http://icpc.me/10066

문제 링크

• http://icpc.me/8235

문제 링크

• http://icpc.me/16910

문제 링크

• http://icpc.me/12008

서론

august14님께서 BOJ에서 이벤트를 개최하셨습니다. (이벤트 공지)
다항시간 안에 해결하지 못하는 문제를 적절히 잘 풀어나가는 이벤트로, 재미있어 보이길래 참가했습니다. 이벤트가 2일만에 끝나서 아쉽긴 하지만, 여러가지 시도를 많이 해봤고 오랜만에 재밌게 문제를 풀 수 있었습니다.
3월 16일에 이벤트가 끝나면 올릴 생각이었지만 일찍 끝났길래 지금 올립니다.
이 글에서는 2일동안 제가 이 문제를 풀기 위해 시도한 것들을 정리합니다.

서론

어떤 자료구조가 “persistent하다”라는 것은, 상태의 변화가 생기더라도 과거 상태를 모두 보존하고 있다는 것을 의미합니다.
Persistent Segment Tree(PST)는 세그먼트 트리의 갱신 과정을 모두 저장하고 있는 자료구조입니다.