제가 이번 학기에 고급 알고리즘 정도에 해당하는 대학원 과목을 듣고 있습니다. 이 과목의 기말 프로젝트 비슷한 걸로 논문 발표(및 구현)가 있습니다. 논문 주제는 알고리즘과 관련된 거라면 아무거나 좋은데요, 혹시 재밌는 논문이 있다면 추천 받고자 이렇게 글 올려봅니다~

기본적으로 다음 조건을 만족해야 합니다:

* 알고리즘이 구현 가능해야 합니다. 구현도 프로젝트의 일부이기 때문에..
* 발표 시간이 20분이기 때문에, 난이도가 적절해야 합니다.

추가적으로 다음 조건이 만족되면 좋습니다:

* 시간복잡도 분석이 재밌으면 좋습니다. 과목에서 제일 처음 배운 내용이 amortized analysis인데, 이런 식으로 약간 까다롭지만 재밌는 시간복잡도 분석이 있다면 교육적 효과가 클 것 같아서.. -_-;
* 구현 난이도가 적당하면 좋습니다. 저 개인적으로는 어려울수록 좋을 것 같은데, 그러면 발표하기도 힘들 것 같아서 적당히..
* 수업과 연관이 있으면 좋습니다. 수업 내용은 amortized analysis, string matching, suffix tree/array, randomized algorithm, online algorithm 이었습니다.

일단은 작년 서울 대회 J번 문제(Number) 논문을 주제로 잡아 보았습니다. 그런데 걱정인 것은, 이 논문이 생각보다 쉬운 것 같다는 것입니다-_-; 내용 자체는 수식 몇 개 보이는 식이라 난이도가 적당할 것 같은데, 구현은 몇 줄 안될 것 같아서 너무 쉽지 않을까 하는 걱정이 드네요. 2차적인 후보는 Lowest Common Ancestor 관련 논문인데, 이 부분에 대해서는 아직 자료를 찾아보진 않은 상황입니다. LCA는 수업 때 개념만 간단히 소개하고, 구체적인 방법은 배우지 않아서 적절한 주제일 것 같아서요.

아무튼 이런 상황인데, 혹시라도 재밌는 알고리즘 논문 있다면 추천 부탁드립니다~^^