아래 셋은 하는 일이 거의 동일하므로 아무거나 골라 쓰면 됩니다. 개인적으로 Index Tree을 추천합니다.Fenwick (BIT, Binary Indexed Tree)https://www.acmicpc.net/blog/view/21Index Tree (정식 명칭 없음) int N = 15; int l = 3; int r = 8; int left = N+l; int right = N+r; while(left

우선순위 큐다음 세 연산을 O(lg n)에 지원한다.insert(x)get_min()remove_min()이런 연산들을 지원하는 자료구조들로는 다음이 있다. 취향에 맞게 선택하면 된다.코딩 쉬움: heap코딩 어려움: AVL, Red-black tree 등의 Balanced Binary Search Trees최소공통조상우선 root를 정한다.d[node][0] = parent[node] d[node][i] = d [ d[node][i-1] ] [i-1] // node로부터 2^i 올라간 정점은 2^(i-1) 올라가고 2^(i-1) 올라간 것과 같다.int goUpward(int A, int depth) // A로부터 depth만큼 올라간 정점 { int power=0; for(int i=1;i depth..

Union Find2가지 연산이 있다.group(A): 정점 A가 속한 그룹의 대표int r[1000]; int group(int node) { if(!r[node]) return node; return r[node] = group(r[node]); }join(A, B): 정점 A가 속한 그룹과 정점의 B가 속한 그룹을 합친다.void join(int A, int B) { int ga = group(A); int gb = group(B); if(ga==gb) return; // do nothing r[ga]=gb; }Kruskal최소 신장 트리 (Minimum Spanning Tree)를 구하는 알고리즘. 간선들을 가중치 오름차순으로 정렬한 후, 첫번째 간선부터 보면서 현재 간선이 사이클을 만들지 않으면..

선분교차선분의 끝점이 만나면 어떻게 처리해야 하는가?1. box_checking(A,B,C,D) 2. ccw_checking(A,B,C,D)= ccw(A,B,C)*ccw(A,B,D) 0 ? 1 : -1;}int main() {int x3, y3;scanf("%d %d", &x1, &y1);scanf("%d %d", &x2, &y2);scanf("%d %d", &x3, &y3);printf("%d", CCW(x3, y3));} 4. 2166 5. 6439 6. 1708 7. 10254 8. 2261

qsort 구현 연습 (같은 원소 처리에 주의) + 자신만의 rand()오일러 피 함수 구현 연습 ( pi(1)부터 pi(n)까지 구하기 ) -> 익힌 후 10438 풀어보기ccw 함수 = 신발끈 공식 (shoelace)http://cookyworld.tistory.com/49Utopia, 분수 찾기 생각해보기 - 학습내용1. CCW(CounterClockWise)를 통한 2차원 좌표에 order를 부여하고, 정렬하기. atan 를 이용하는게 제일 쉽지만, 라이브러리를 못쓰므로 CCW로 정렬.CCW라는게 사실 외적인데, 외적의 부호로 결정한다.두점으로 만든 선분을 기준으로 나머지 한점이 시계방향인지, 반시계방향인지, 일직선위에 있는지를 판별. 2. Euler Phi function을 통한 서로소 찾기 서..