MOD2 [문제해결기법] 4. 자료구조2 1. 트리 지름 트리의 두 정점 u, v의 거리의 최댓값 (1) O(n^3) : brute force (2) O(n^2) : u를 고정하고 bfs한다. (3) O(n) 트리에서 임의의 정점 x를 선택하고 x에서 가장 먼 정점 y를 찾는다.(bfs) 이후 y에서 가장 먼 정점 z를 찾는다. 그러면 y와 z가 가장 멀리 떨어져있는 정점 쌍이다. 증명 원하는 답이 두 정점 u와 v이다. 그렇다면 3가지 가능성이 있는데, x에서 가장 먼 점이 y라고 하면 (1) x = u / x = v (2) y = u / y = v (3) x,y,u,v 모두 다른 경우 (1)과 (2)는 위 알고리즘의 답이 맞다는 것이 자명하다. (3)의 경우는 u~y 경로와 u~v 경로가 거리가 같은 경우 이외에는 없어야 한다. x,y,u,.. 2023. 4. 16. [문제해결기법] 2. 기초수학 1. 벡터의 외적 : cross product 2. 외적의 응용 : 부호 점검 3. CCW 알고리즘 : Counter-Clock Wise 세 점이 주어졌을 때 A->B와 A->C 두 벡터의 외적의 부호가 방향을 결정함. int ccw(int x1, int y1, int x2, int y2, int x3, int y3){ int tmp = x1*y2 + x2*y3 + x3*y1; tmp -= (y1*x2 + y2*x3 + y3*x1); if(tmp > 0) return 1; // a에 대해 b가 반시계 방향(왼쪽)에 있음 else if(tmp < 0) return -1; // a에 대해 b가 시계 방향(오른쪽)에 있음 else return 0; } 4. 응용 : 선분의 교차 여부 a-b를 이은 벡터 A에 .. 2023. 4. 16. 이전 1 다음 728x90 반응형
