The Way

겨울의 메이플이라는 글을 쓰고도 벌써 1년이 다 되어간다 1년 전에는 간신히 노말 루시드를 잡았었다. 1년이 지난 지금은 과연 어떨까? 루시드를 잡고 한동안 무료한 일상이 이어졌다. 노말 스우는 100번을 잡아서 더 이상 잡을 필요가 없어졌고... 루시드는 패턴 버그가 고쳐지고 다소 익숙해지면서 10번 뚝딱 해치웠다. 이러한 무료한 일상은 2021년 6월 17일 클라이언트 1.2.349에서 리부트 월드가 개편되면서 큰 격변을 맞게 된다. 리부트 패시브 데미지가 최종뎀으로 바뀌고, 렙차뎀뻥이 추가되면서 기존보다 약 30~50% 정도 더 강해지게 되었다. 8월 12일에는 가디언 엔젤 슬라임이 새로 추가됐다. 9월쯤 되며 슬슬 다들 뭔가 템이 조금씩 갖추어지는 것 같자 하드 보스를 슬슬 트라이해보았다. 의외로..

*.. .*. *.. 와 같은 식으로 n * n 크기의 board가 주어질 때, manhattan distance를 기준으로 정삼각형을 이루는 세 쌍의 *의 수를 구하는 문제이다. 모든 쌍을 다 해보려면 시간 복잡도는 $O(n^6)$이고, 점을 두 개만 고르면 나머지 한 점의 가능한 위치는 정해지므로 이 방법을 사용한다 해도 시간 복잡도는 $O(n^4)$이다. n = 300이므로, 조금 더 나은 방법을 찾을 필요가 있다. 먼저 적절한 관찰을 통해 정삼각형이 가지는 특징을 알아낼 필요가 있다. 한 변의 길이가 d인 정삼각형은 적절한 90도 단위의 회전을 통해, 좌표가 $(p, q), (p + x, q + (d - x)), (p + y, q + (d - y))$ $(0 \le x \le d, 0 \le y ..

2차원 평면에 검은 점과 하얀 점이 각각 N개씩 찍혀 있다. (으레 기하 문제가 그렇듯 임의의 세 점이 한 직선 위에 있지는 않다고 치자) 이제 우리는 각각의 검은 점에 하얀 점 하나씩을 선분으로 이어 주려고 한다. 단, 선분끼리 교차하지 않아야 한다. 총 N개의 선분을 그어 모든 하얀 점과 검은 점들을 이어줄 수 있을까? 대충 이어보면 생각보다 잘 이어지긴 한다. 하지만 모든 점들을 이어주는 것이 항상 가능할까? 예를 들어서 N = 10만 정도이고 검은 점과 하얀 점이 복잡하게 얽혀 있는 경우에도 가능할까? 결론을 먼저 말하면 가능하다. 이를 증명하는 방법은 여러 가지가 있는데, 이 중 매우 깔끔하면서 재미있는 방법을 하나 소개한다. 많은 내용의 출처는 SW Expert Academy - Learn -..