algospot.com :: 질문과 답변: 재밌는 논문 추천해주세요~

재밌는 논문 추천해주세요~

lewha0
제가 이번 학기에 고급 알고리즘 정도에 해당하는 대학원 과목을 듣고 있습니다. 이 과목의 기말 프로젝트 비슷한 걸로 논문 발표(및 구현)가 있습니다. 논문 주제는 알고리즘과 관련된 거라면 아무거나 좋은데요, 혹시 재밌는 논문이 있다면 추천 받고자 이렇게 글 올려봅니다~
기본적으로 다음 조건을 만족해야 합니다:
- 알고리즘이 구현 가능해야 합니다. 구현도 프로젝트의 일부이기 때문에..
- 발표 시간이 20분이기 때문에, 난이도가 적절해야 합니다. 추가적으로 다음 조건이 만족되면 좋습니다:
- 시간복잡도 분석이 재밌으면 좋습니다. 과목에서 제일 처음 배운 내용이 amortized analysis인데, 이런 식으로 약간 까다롭지만 재밌는 시간복잡도 분석이 있다면 교육적 효과가 클 것 같아서.. -_-;
- 구현 난이도가 적당하면 좋습니다. 저 개인적으로는 어려울수록 좋을 것 같은데, 그러면 발표하기도 힘들 것 같아서 적당히..
- 수업과 연관이 있으면 좋습니다. 수업 내용은 amortized analysis, string matching, suffix tree/array, randomized algorithm, online algorithm 이었습니다. 일단은 작년 서울 대회 J번 문제(Number) 논문을 주제로 잡아 보았습니다. 그런데 걱정인 것은, 이 논문이 생각보다 쉬운 것 같다는 것입니다-_-; 내용 자체는 수식 몇 개 보이는 식이라 난이도가 적당할 것 같은데, 구현은 몇 줄 안될 것 같아서 너무 쉽지 않을까 하는 걱정이 드네요. 2차적인 후보는 Lowest Common Ancestor 관련 논문인데, 이 부분에 대해서는 아직 자료를 찾아보진 않은 상황입니다. LCA는 수업 때 개념만 간단히 소개하고, 구체적인 방법은 배우지 않아서 적절한 주제일 것 같아서요. 아무튼 이런 상황인데, 혹시라도 재밌는 알고리즘 논문 있다면 추천 부탁드립니다~^^
  [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]
16년 전

12개의 댓글이 있습니다.

Kyungryeol

볼만한 LCA 논문 링크 알려드릴게요.
개인적으로, 그렇게 어려운것도 아니고 딱 적당한 수준이라고 생각합니다.
http://www.ics.uci.edu/~eppstein/261/BenFar-LCA-00.pdf

16년 전 link
Taeyoon_Lee

저는 치킨집 문제의 해법인 min-ball에 대한 논문이 꽤 좋았습니다.
우선 시간복잡도 분석이 재밌어요. 난이도도 너무 어렵지도, 쉽지도 않은 게 딱 좋은 것 같아요.

16년 전 link
@,.@

sallest enclosing discs 라는 논문 추천합니다. 말그대로 모든 포인트를 포함하는 가장 작은 디스크를 구하는 방법이에요. 계산기하 논문이구요. randomized algorithm을 사용하고 O(n) expected time에 풀수 있는 문제에요.
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.46.1450

16년 전 link
JongMan

http://portal.acm.org/citation.cfm?id=225173&dl=GUIDE&coll=GUIDE&CFID=10487797&CFTOKEN=31130692 오래된 논문이지만 'ㅅ'

16년 전 link
JongMan

이거 논문 제목이나 링크를 알 수 있을까요? ^^;

16년 전 link
kcm1700

Tadao Takaoka의 Efficient Algorithms for the Maximum Subarray Problem by Distance Matrix Multiplication
http://www.cosc.canterbury.ac.nz/tad.takaoka/cats02.pdf 어떤가요? 전 재밌게 공부한 기억이 납니다.

16년 전 link
고글

Fast Smallest-Enclosing-Ball Computation in High Dimensions
http://people.inf.ethz.ch/fischerk/pubs/seb.pdf

16년 전 link
pedant

눈팅만 하다 슬쩍 리플을 ^^;
계산 기하에 좀 관심있으시면 Timothy Chan의 Convex hull algorithm도 재밌죠.
http://www.cs.uwaterloo.ca/~tmchan/conv23d.ps.gz
Convex hull의 complexity가 O(h)이면 이를 O(n log h)(O(n log n)이 아닌)에 구해버리는 알고리즘입니다.
output sensitive algorithm 중에서는 고전 중 고전이지요

16년 전 link
Being

k-dense corridorsbest fitting rectangle(largest empty rectangle)
k-center problems
같은 주제가 떠오르네요.

16년 전 link
wookayin

잠시 지나가다가 기억을 더듬어 보자면.. (구체적인 논문이 아니라 주제만 적어보자면)
Rotating Calipers (-_-)나 다양한 Fast LCS/LIS/LCIS Algorithms 들도 생각이 나네요(...)

16년 전 link
lewha0

답변해주신 분들, 그리고 해주실 분들[?]에게 감사의 말씀 올립니다 ^^;
발표 잘 되면 발표 자료라도 올리거나 해서 다른 분들과도 공유할 수 있도록 하겠습니다 !

16년 전 link
Taeyoon_Lee

제가 봤던 논문은 아래 @,.@님이 올려주신 거랑 같네요..

16년 전 link
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.

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

알고리즘이 구현 가능해야 합니다. 구현도 프로젝트의 일부이기 때문에..
발표 시간이 20분이기 때문에, 난이도가 적절해야 합니다. 추가적으로 다음 조건이 만족되면 좋습니다:
시간복잡도 분석이 재밌으면 좋습니다. 과목에서 제일 처음 배운 내용이 amortized analysis인데, 이런 식으로 약간 까다롭지만 재밌는 시간복잡도 분석이 있다면 교육적 효과가 클 것 같아서.. -_-;
구현 난이도가 적당하면 좋습니다. 저 개인적으로는 어려울수록 좋을 것 같은데, 그러면 발표하기도 힘들 것 같아서 적당히..
수업과 연관이 있으면 좋습니다. 수업 내용은 amortized analysis, string matching, suffix tree/array, randomized algorithm, online algorithm 이었습니다. 일단은 작년 서울 대회 J번 문제(Number) 논문을 주제로 잡아 보았습니다. 그런데 걱정인 것은, 이 논문이 생각보다 쉬운 것 같다는 것입니다-_-; 내용 자체는 수식 몇 개 보이는 식이라 난이도가 적당할 것 같은데, 구현은 몇 줄 안될 것 같아서 너무 쉽지 않을까 하는 걱정이 드네요. 2차적인 후보는 Lowest Common Ancestor 관련 논문인데, 이 부분에 대해서는 아직 자료를 찾아보진 않은 상황입니다. LCA는 수업 때 개념만 간단히 소개하고, 구체적인 방법은 배우지 않아서 적절한 주제일 것 같아서요. 아무튼 이런 상황인데, 혹시라도 재밌는 알고리즘 논문 있다면 추천 부탁드립니다~^^
[이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

16년 전

SINCE 2007

다가오는 이벤트들

재밌는 논문 추천해주세요~

12개의 댓글이 있습니다.