[일반] 트리의 지름 퓰이를 어떻게 발상할까

[익명(211.36)]

가능한 경우들 나눠서 규칙을 찾는건가? 증명은 이해하겠는데 어떻게 이런걸 떠올릴까 싶음

하긴 퀵소트같이 유명한 알고리즘들 만든 사람들 보면 파인만, 다익스트라같은 천재들이 대부분이더라 최소 대학 교수들

- dc official App

[익명(119.207)]

내가 아는 트리의 지름 문제면 그냥 한점 잡고 가장 먼 점 찾고 그 점에서 다시 가장 먼 점 찾으면 되는거 아님?

[익명(211.36)]

그 풀이를 몰랐을 때 어떻게 떠올리는걸까 - dc App

[익명(119.207)]

나는 처음에 못 떠올렸던 거 같은데 트리 지름 문제는 아마 Ps러들 중에 자력으로 떠올린 사람들 많을 거 같음

[익명(211.36)]

역시 대단한 사람들 많어 - dc App

[익명(211.208)]

그냥 이러면 왠지 맞지 않을까? 생각하고 풀어서 proof by AC 한 사람들은 꽤 있을듯한데, 엄밀히 말하는 증명까지 하면서 푼 사람들은 극소수이긴 할거같음

[흑화뉴비(coderhs)]

그래프론 공부하면 그냥 연습문제로 나와

[익명(211.36)]

이산수학 공부해야겠다 - dc App

[흑화뉴비(coderhs)]

난 douglas west 책으로 공부함 학부책이지만 연습문제에도 논문 찾아봐야하는게 종종 나오더라

[익명(211.36)]

오 rosen 책 살려고했는데 이것도 알아볼게 ㄱㅅㄱㅅ - dc App

[흑화뉴비(coderhs)]

로젠은 이산수학 책인데 저건 진짜 그래프“만” 나옴 이산수학 다 보고도 그래프가 재밌으면(보통 재미없어서 거름) 보면 된다

[익명(220.123)]

먼점 찾는 방식은 떠올리는게 불가능하다고 보고, dp로 푸는건 떠올릴 수 있지

[익명(59.11)]

나는 트리dp로 자력으로 떠올림

[익명(61.74)]

트리의 지름 문제는 모든 정점 다 돌려도 풀림

[익명(1.245)]

충분히 자력으로 풀수 있다고 봄

[익명(39.7)]

난 반대로 dp 방식보다 먼점 방식을 혼자 떠올림. 그때부터 ps ㅈㄴ 재밌었다