leejk9592   3년 전

질문들을 읽어보니 N개의 노드들이 주어졌을 때, 최대 log_2_N개의 색깔을 사용해

DP를 수행하면 답이 나온다는 것을 알게되어 정답을 맞추게 되었는데,


왜 log_2_N개의 색깔을 사용하면 정답이 나오는지에 대한 원리를 알고 넘어가고 싶습니다.

간략하게 힌트 만이라도 주시면 정말로 감사 드리겠습니다.

koosaga   3년 전

T(N) = N개의 색깔을 사용했을 때 답이 나오는 트리의 최소 크기

라고 정의합니다.


1. 자명히 T(1) = 1입니다.

2. T(i) >= T(i-1) + T(i-2) ... T(1) + 1입니다. 최소의 트리 T(i) 를 생각해봅시다. 해당 트리에는 i번 색의 노드가 하나 존재할 것입니다. 이 트리에 인접한 노드들은 i-1, i-2, i-3 .... 1의 색깔을 가집니다. 서브트리들의 크기는 최소 T(i-1) 이상입니다.


이를 통해 T(N) >= 2^(N-1) 임을 증명할 수 있습니다. 

shfshfdl   3년 전

koosaga 님 조금만 더 자세히 설명해주실 수 있나요?

T(i-1) 도 N개의 서브트리를 가질수있고 T(1)도 그런거같은데

어째서 이게 2^(N-1)이 되는지 궁금합니다.

지식없이 여쭤봐서 죄송합니다.

koosaga   3년 전

N개의 서브트리를 가진다는 게 무슨 말씀인지 모르겠습니다. 질문을 조금 더 정확히 해 주실 수 있나요?

shfshfdl   3년 전

음 제가 처음부터 이해를 잘못했는지 정확히 여쭙질 못하겠네요..ㅠ


2. T(i) >= T(i-1) + T(i-2) ... T(1) + 1입니다. 최소의 트리 T(i) 를 생각해봅시다. 해당 트리에는 i번 색의 노드가 하나 존재할 것입니다. 이 트리에 인접한 노드들은 i-1, i-2, i-3 .... 1의 색깔을 가집니다. 서브트리들의 크기는 최소 T(i-1) 이상입니다.

이를 통해 T(N) >= 2^(N-1) 임을 증명할 수 있습니다.


라고 하셨는데 2번에서 결론이 2^(N-1)이 도출되는게 이해가 안되서요..


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