MolaMola팀 팀노트

MolaMola 팀 팀노트입니다. (링크) (18년 10월 3일 수정. docx 파일로 복사-붙여넣기가 가능합니다.)

5년 전 kcm님 팀노트에서 시작되어 조금씩 수정하던 것 같습니다. 감사합니다.

0. Algorithm Checklist

• 풀이 생각할 때 도움이 되라고 쓴 겁니다. 안 풀릴 때 한번씩 읽으려고 했는데, 아직 도움이 된 적은 없네요.

1. JavaIO, Set k-th element

• 지금보니 목차가 잘못되어있네요.. BigInteger 사용 용도와 std::set에서 k번째 원소 찾는 방법을 넣어둔 것입니다.
• Java는 그렇다고 하고, std::set은 쓸 때 실행시간에 주의하시기 바랍니다. 저번 코포에서 틀린 적이 한 번 있어서..

2. Splay tree, link-cut tree

• Splay tree와 lazy propagation, link-cut 트리와 lazy propagation을 지원하는 버전입니다. 잘 만들어보려고 노력했지만, 최선은 코드를 이해하고 문제마다 알아서 수정하는 것이 가장 낫다는 결론을 내렸습니다.

3. Graph Algorithm

• Dominator tree는 검색하서 찾아보시기 바랍니다. 방향그래프와 소스노드 S가 있을 때, 모든 노드 v에 대해 S->v의 모든 경로에서 나타나는 노드들을 구할 때 씁니다. 
• Arborescence는 방향그래프에서, 소스 S에서 나가는 방향의 트리들 중 가중치 합이 최소인 것을 찾을 때 씁니다. 역추적도 있고, 코드를 짧게 짜려고 노력했습니다.
• Maximum matching과 Dinic은 보고 쓰려고 넣은거지만, 정작 도토리는 안봅니다. 
• Vizing은 생각하고 짜기에는 너무 귀찮아서 어떻게든 줄여서 팀노트에 넣었지만, 쓸 일이 있을지는 모르겠습니다.
• Hungarian Method는 대회 직전에 급하게 우겨넣은 코드입니다. 기본적으로 최대 매칭을 구하는 알고리즘입니다만, 그것 말고도 D_ij가 주어질 때, A_i + B_j + D_ij >= 0으로 만드는 최소 sum(A_i, B_j)를 구하는 데에도 사용됩니다.
• Maximum clique는 심심하면 탑코더에 크기 50짜리 그래프로 clique 찾는 문제가 나오는데, 모든 maximal clique를 O(3^N/3) 정도에? 구해줍니다.
• Stoer Wagner는 그래프를 두동강내는 최소 가중치를 구할 때 씁니다. 그냥 장식으로 넣었습니다. 

4. Mathmatical stuff

• 키르히호프는 악명 높아서 다들 알고 있겠지만, 그래프의 spanning tree 개수를 계산할 때 씁니다. 
• Simplex는 Linear Programming 문제 풀 때 씁니다. 시간복잡도가 지수인데, 놀랍게도 N=100일 때도 나온다고 전해집니다.
• LP는 Simplex 문제를 뒤집을 때 씁니다. 쓸 일이 거의 0이지만, 알면 신기한 내용입니다.
• Polynomial multiplication은 다들 알다시피 FFT입니다. 특히 NTT는 대회 직전에 코드를 복붙해 넣었습니다.

5. Geometry

기하 라이브러리는, 몇 번 고민을 해봤는데, 그대로 적기에는 무리가 있고 참고하면서 조금씩 바꿔서 써야 합니다. 때문에 이해하고 쓰는 것을 추천합니다.

• Delaunay 삼각분할은 쓴 적이 없는데, 넣어놓고 있습니다.
• Header는 빼도 되는데 귀찮아서 넣었습니다. 저는 pair<int,int>나 pair<double, double>을 x, y좌표로 씁니다.
• 연산지 중에, *는 내적, /는 외적을 의미합니다. 나머지 함수는 읽어보시면 뭐하는 함수인지 아실 것 같습니다.
• 직선 표현은 벡터 2개로 표현하는데, a+kb (k는 실수) 형태로 표현하는 것이 제일 편합니다.
• Tangent Series에는 두 원의 접선 4개와, 볼록 다각형 접선이 있습니다. 원은 x축을 기준으로 반시계 방향으로 몇 도인지 반환하고, 다각형은 점을 반환합니다. 이것도 나중에 코드를 봐야 될 것 같습니다. (주석을 보시기 바랍니다)
• Intersect Series는 각종 것들의 교차점을 구합니다. 인자와 내용을 보시면 될 것 같습니다.
• Distant는 점과 선분의 거리입니다.
• Make circle은 점 2개와 반지름, 혹은 점 3개를 지나는 원입니다.
• 3D Header는 3차원 점 표현과 사원수 표현, 회전변환 설정을 정의합니다.
• 3D Intersect Series는 각종 것들의 교차점을 구합니다. 인자와 내용을 보시면 될 것 같습니다.
• Convex Hull은 귀찮아서 안뺐습니다.
• Intersect area series는 삼각형과 삼각형 교집합, 원과 삼각형 교집합 넓이를 구합니다. 저번에 이거로 문제가 안풀렸던 경험이 있어서 다시 봐야됩니다.
• smallest enclosing circle은 평균 O(N)으로 모든 점을 포함하는 가장 작은 원을 구합니다.
• 3D convex hull은 O(N^2)에 3차원 convex hull을 구합니다. 지금은 까먹어서 다시 봐야됩니다.
• Dynamic convex hull은 점 추가와, 특정 기울기에 대해 가장 극단에 있는 점을 찾는 구조체입니다.
• Halfplane intersection은 반평면 교집합입니다. 주석을 보시면 될 것 같습니다.
• Polygon raycast는 다각형에 직선을 그었을 때 나타나는 이벤트를 모두 찾아 저장한 것입니다. 그림과 state에 있는 주석에 써진 이벤트를 모두 확인하시기 바랍니다. (다각형은 일직선 상의 세 점이 없다는 것을 가정합니다.)

6. Miscellaneous

• Root Finder는 쓴 적 없고 뭔지도 모릅니다. 그리고 안쓸 것 같습니다.
• Pollard rho + miller rabin은 O(N^1/4) 소인수분해 알고리즘입니다.
• Gauss Quardrature Table은 적분할 때 쓰는 값인데, 수치적분을 이미 저거로 한 번 틀려먹어서.. 수치적분 테크닉은 잘 모르겠습니다.

끝!