문제 링크

• http://icpc.me/16002

서론

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

문제 링크

• 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일동안 제가 이 문제를 풀기 위해 시도한 것들을 정리합니다.