6. 2

• 오전에 잠도 푹 잤고, 오늘은 열심히 문제나 풀어야징!
• <A Knapsack Problem>을 풀었다. central node를 통한 divide and conquer의 아이디어가 <Race>와 정말 다를 게 없이 적용됐다. root가 정해진 경우 \(O(N)\) solution은 이미 생각했던 DP였고.. 다만 central node를 구하는 데 있어서, <Race>의 ainta님 답안을 따라서 그냥 크기가 N/2이상인 최소크기노드를 탐색했다. 노드에 연결된 모든 엣지를 체크할 필요가 없으니 계산량이 반으로 줄어든 듯... 이런 문제 재밌다 ㅋ_ㅋ # 못풀었지만 Weekly Challenge의 5번째 문제치고는 조금 쉬운듯 하다. W3의 <GCD Product>를 생각하면..-_-
• <GSS3>은 쉬운 문제였고, # <GSS4>를 풀면서 이 튜토리얼을 봤다. 지금까지 고생해서 모은 segment tree에 대한 조각조각들이 하나로 꿰어지는 튜토리얼이다! 자세하게 읽어야지... 근데 왜 WA세례가 나는가-_- 으 짜증나!! => 문제에 쿼리가 i<=j라는 말이 없었다... swap처리를 안했더니.. #
• <GSS5>도 어렵지 않은 문제.. 구간이 겹치는 경우를 분리하여 처리하면 된다. #
• <KGSS>도 쉽다. # <HELPR2D2>도 입력만 짜증나는 문제ㅡㅡ #