10. 16

• 저번 Weekly Challenge 11문제들을 곱씹고 있는데, 정말 좋은 문제들이란 걸 새삼 느낀다. 개념을 정확하게 이해해야만 풀 수 있는 문제들! 그렇다고 너무 꼬거나 복잡한 작업은 없고 깔끔하게 풀리는 문제들! 딱 지금의 내 수준에 맞는 문제들인듯. 거기다가 자세한 Editorial+해답코드+다른사람코드까지! 이정도면 운명적 만남이라고까지 할 수 있지 않을까ㅠ.ㅠ 나의 발전에 지대한 공헌을 해주고 있다..
• <Tree Pruning>은 신박한 DP를 보여줬다. 기본적으로 DP를 위해서는 데이터가 가지런히 있어야 한다. 하나하나씩 데이터를 추가해가며 계산하는 게 기본이기 때문이다. 내가 골머리를 썩힌 부분도 Tree구조에서의 DP를 어떻게 구현할까 하는 문제였는데.. 이걸 전위순회한 결과를 토대로 DP설계를 해서 풀어냈다. 유용한 스킬!
• <Two Array Problem>은 문제를 읽을 때 아.. 이건 내가 모르는 자료구조에 모르는 기하알고리즘이구나-_-하고 일찌감치 포기했는데.. 둘다 어중간하게 아는 것들이었다. 하나는 트립이었고, 다른 하나는 Welzl's Algorithm이었다. 트립은 알고 있었지만T_T 애초에 트리구조에 대한 이해가 밝지 않은 나는 이렇게 활용할 수 있을줄은 상상도 못했다. 트립의 split연산과 merge를 통해서 구간swap을 구현해내고, lazy propagation을 통해서 구간reverse를 구현했다. 모두 O(lgN)에.. 애초에 선형 데이터 구조를 트리구조로 어떻게 바꾸는지 상상이 안됐던 나는 코드를 보고서도 머리를 싸맬 수밖에 없었다-_-; 중요한 아이디어는 트리구조의 중위순회결과가 대응하는 배열의 값이 된다는 것.. split과 merge를 아무리 하더라도 중위순회의 결과는 달라지지 않는다.
• Welzl's Algorithm은 이 문제를 보고 "유명한 문제"다 싶어서 찾아봤더니 나온 알고리즘. smallest enclosing disk문제에 대한 해법이 여러가지 있는데.. 이 알고리즘은 O(N)만에 계산한다. 순서를 랜덤화한 정점을 하나하나 추가해가면서 Circle을 업데이트하는데, 기존 원을 벗어난 정점을 발견하면 원의 가장자리에 꼭 포함된 점으로 추가하고 recursion으로 원을 업데이트해준다. recursion은 총 O(N)이 걸리는 것 같은데.. 발생확률이 1/N이므로 추가작업은 O(1)이 된다. N개 정점을 추가하므로 O(N)..
• Treap+Welzl's Algorithm 구현 소스를 봤는데 머리가 터지는 줄 알았다-_-