알고리즘/메모44 그래프 크기 구하기 int sz[MAX]; //따로 초기화 해둘 필요 없음 bool vst[MAX]; void dfs(int curr) { vst[curr] = true; sz[curr] = 1; for (int next : adj[curr]) { if (!vst[next]) { dfs(next); //빠져나오면 curr의 next방향 서브트리의 sz모두 초기화 sz[curr] += sz[next]; } } } * 메인함수에서 dfs(rootNode)로 수행해야 모든 정점에 대해 구할 수 있음 * 양방향/단방향(부모->자식) 간선을 사용한 트리 모두에 대해 사용 가능 bool vst[MAX]; int dfs(int curr){ vst[curr]=true; int ccnt=1; for(int next: adj[curr]){ .. 2020. 1. 7. 머지소트 #include using namespace std; const int MAX = 1e5; int n, a[MAX], b[MAX]; void msort(int st, int en) { if (st == en) return; int mid = (st + en) / 2; msort(st, mid); msort(mid + 1, en); int i = st, j = mid + 1, k = 0; while (i a[i]; msort(0, n - 1); for (int i = 0; i < n; i++) cout 2020. 1. 2. 라인스위핑 새로운 유형 만날때마다 업데이트 예정 최대로 교차하는 선분의 개수. O(nlogn) https://suuntree.tistory.com/103 2번유형 (그리디) 모든 교차하는 두 쌍의 선분에 대한 질의. O(n^2) https://suuntree.tistory.com/112 어떤 선분에 포함되는/포함되지 않는 선분의 개수. 정렬후 O(n) https://suuntree.tistory.com/190 2019. 12. 29. 그리디 1. 그리디로 항상 최적해를 구할 수 있다면, 그리디는 dp보다 훨씬 빠르다. (그리디로 풀리면 보통 dp로도 풀린다) 2. 시공간 제약으로 인해 최적해를 찾는 것이 극히 제한되는 경우, 근사해를 찾아준다. ps에선 1번 용도로만 사용된다. 근사해 찾기는 조합탐색이나 메타휴리스틱을 사용한다. 탐욕적 선택 속성(greedy choice property) : dp처럼 답의 모든 부분을 고려하지 않고 탐욕적으로만 선택하더라도 최적해를 구할 수 있는 속성 최적 부분 구조(optimal substructure) : dp처럼 부분 문제의 최적해에서 전체 문제의 최적해를 만들수 있는지 ->대부분 자명해서 증명할 필요가 없는 경우가 많다. 하지만 예외 존재 알고리즘이 위 두 속성을 만족하는지 검증해야 한다. 1. 활동.. 2019. 12. 18. 이전 1 ··· 3 4 5 6 7 8 9 ··· 11 다음
