본문 바로가기

전체 글110

TopCoder Marathon Match 99 후기 거의 7년 만에 탑코더 마라톤 매치(Marathon Match, MM)를 해 보았습니다. MM은 Single Round Match(SRM)와 달리 정해진 정답을 빠르고 정확하게 계산하는 대회가 아니라, 문제에서 요구하는 최적해를 30초 ~ 1분 정도의 다소 넉넉한 수행시간을 가지고 계산할 수 있는 알고리즘을 고안하는 대회입니다. 대회를 치르는 시간도 SRM은 1시간 15분인 것에 비해 MM은 최소 1주 ~ 2주의 긴 시간 동안 이루어집니다.이번 MM 문제 내용을 한 문구로 요약하면 '슬롯 머신을 이용한 도박'이라고 할 수 있습니다. 문제 본문은 다음 링크( MM 99 Problem Statement )에서 보실 수 있습니다. 대회 결과는 다음 링크 ( MM 99 Standings )에서 보실 수 있습니다.. 2018. 3. 25.
Heavy Light Decomposition N개의 정점을 가진 트리가 있다고 하자. 이 때 임의의 두 정점에 대해 이들을 잇는 경로는 O(N)개의 간선을 가진다. Heavy light decomposition(HLD)은 트리의 간선들을 적절히 일자 경로인 “묶음”들로 잘라, 임의의 두 간선 사이 경로를 O(lg N)개의 묶음으로 표현할 수 있게 해 준다. 이것을 세그먼트 트리 등의 일차원 자료 구조와 결합함으로써, 임의의 두 정점 사이의 경로에 대한 연산을 O(lg2N)에 할 수 있다. 간선들을 묶음으로 잘 나누는 방법은 다음과 같다. 1. 임의의 정점을 루트(R)로 지정하여, DFS 탐색을 한다. DFS 탐색을 하면서 각 정점에 대해 다음의 2가지를 계산한다. 1) 루트 노드와의 거리 2) 해당 정점이 루트 노드인 subtree의 크기 2. R.. 2018. 2. 15.
ACM-ICPC related materials - hongjun7 팀노트 - ntopia님 팀노트- KAIST 더불어민규당(koosaga, hyea, alex9801) 팀노트- SNU MolaMola(cki86021, dotorya, zigui) 팀노트- csehydrogen님 팀노트- kcm1700님 팀노트- KTH Royal Institute of Technology in Stockholm 대학교 팀노트 - NUS RR Watameda(I_love_Hoang_Yen, flashmt, nguyenhungtam) 팀노트- E-Maxx Algorithms 2018. 2. 14.
2015 ACM-ICPC Asia Phuket Regional Contest 5시간 대회인데, 창수랑 둘이 개인전으로 인터넷 예선처럼 3시간 동안만 했다. 2017. 9. 17.
2015 ACM-ICPC Asia Taiwan Online Programming Contest 2017. 9. 17.