sgc109   5달 전

대략 (40000 + 39999) * 10000 으로 대략 8억번정도 돌것같은데 2초안에 무리겠죠..?

알고리즘을 좀더 개선시키기위해 어떤방법이있나요?

(LCA)Lowest Common Ancestor  라는 알고리즘을 이용해서 푸시면 됩니다.

https://en.wikipedia.org/wiki/Lowest_common_ancest...

https://www.topcoder.com/community/data-science/da...

sgc109   5달 전

orange4glace 이 문제에서는 따로 부모자식관계가 없지않나요?

이 문제의 데이터는 트리 데이터이기 때문에 1번 정점을 ROOT 노드라고 생각하여 높이가 0이라고 보면,

1번 노드부터 DFS를 돌리면, 1번 노드에 연결된 노드들은 1번 노드의 자식이 되고, 그 노드들의 높이는 1이라고 볼 수 있습니다.

결과적으로 DFS 탐색을 마치게되면 1번 노드가 ROOT 노드인 트리 데이터를 parent 배열 등을 통해 표현할 수 있게 됩니다.

sgc109   5달 전

orange4glace  그러니까 부모 자식관계가 명시되어있지않으므로 여러가지 모양의 트리가 가능한데 그냥 1번을 루트로 삼아서 만든 트리로 푼다는거죠??

넵 그렇습니다

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