olenmg   3년 전

'공통 조상'의 정의로 "두 노드를 모두 자손으로 가지면서 깊이가 가장 깊은(즉 두 노드에 가장 가까운) 노드를 말합니다."가 주어졌는데, 여기에 "단, 어떤 노드의 자손에는 해당 노드 자신도 포함됩니다." 정도의 표현이 추가되어야 할 것 같습니다.

사실 LCA 문제들은 일반적으로 노드의 자손/조상에 자기 자신을 포함한다는 것을 깔고 가는 경향이 있는 것 같고 실제로 BOJ에 있는 LCA문제들은 위와 같은 내용을 언급하지 않고있어 이 요청 넣는게 맞는건지 고민을 많이 했는데.. 자손 및 조상에 대한 정의를 구글링해보아도 명확한 정의도 없을뿐더러, 어떤 유명 대학 강의노트에서는 오히려 ancestor의 정의로 'An ancestor of a node is any other node on the path from the node to the root.'를 제시하고있습니다.

ICPC 문제 원문에도 'Remember that a node is an ancestor of itself.'라는 문구가 존재합니다.
실제 문제에도 언급되고 있는 것으로 보아, 저정도의 조건 추가는 필요할 것으로 보이는데 검토 부탁드립니다.

**LCA문제를 처음 접해보는데 여러번 오답 받고 뒤늦게 찾아보고 알게되어 말씀드립니다. 처음 접하는 사람들에게는 '조상' 표현에 모호함이 있는 것 같아요ㅠㅠ

** 위 ancestor의 정의에 대한 내용은 http://www.cs.columbia.edu/~allen/S14/NOTES/trees.pdf에서 발췌했습니다.

댓글을 작성하려면 로그인해야 합니다.