글을 읽기 전에 SCC와 절점 절선 개념을 배우고 오길 추천함. 간단히 요약하자면 그래프에서 사이클 비슷한 건 정점 하나로 묶어버리고 트리라 치는 알고리즘이다.이러한 점에서는 SCC랑 엄청 비슷하다. 실제로 SCC의 무향 버전이라고 생각해도 좋음. SCC는 사이클을 정점 하나라고 묶어버리고 DAG로 만드는 방법이면 BCC는 사이클을 간선 하나라고 묶어버리고 트리로 만드는 방법이다. 결국은 다 사이클이 싫어서 하는 짓임. 사용 용도도 SCC랑 상당히 비슷하다. BCC에는 두가지 종류가 있다. SCC는 하나만 있는데 얘는 좀 다르다. * Vertex-disjoint biconnected component : 그래프에서 절점을 제거함으로써, 컴포넌트를 나눔 * Edge-disjoint biconnected c..
https://www.acmicpc.net/problem/1859 O(N^2lgN)Ti / Pi 증가 순으로 정렬된 시험 결과들을 토대로 avg(D)를 정의하자. avg(D)는 그리디 전략으로 D개의 과목을 드랍했을 때 베시의 점수이며, (T(N-D+1) + .... T(N)) / (P(N-D+1) + ... P(N)) 이다.이 때 베시가 더 좋은 점수를 낼 조건은 Sum(T) / Sum(P) > avg(D) 를 만족하는 크기 D의 집합이 있다는 조건이다. 비슷한 유형을 풀어보면 알겠지만, 이는 Sum(T - avg(D) * P) > 0 을 만족하는 크기 D의 집합이 있다는 것과 동치이다. Sum(T - avg(D) * P) > 0을 만족하는 집합이 있는지... 는 굳이 말 안해도 다들 알겠지만, 1 ~..
https://www.acmicpc.net/problem/6007 O(N^4)Maximum Toll Cost의 경우의 수가 O(N)이니. 이걸 고정시키고 O(N^3) Floyd Warshall을 돌리면 된다. Toll cost T보다 값이 크면 그 근처에 있는 에지들을 몽땅 날려버리고 플로이드. 반복 반복... 시간 복잡도는 O(N^4). TLE다. O(N^3)플로이드 와셜의 루프. For(i, j, k) dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);를 생각해 보자.맨 바깥쪽 루프에서 도는 것은 중간 경유지이다. 2차원 배열에 중간 경유지를 모두 돌면서 업데이트하는 것이다.그러면, 어떠한 j , k에 대해서, j -> k로 가는 최단 경로가, i까지 경..
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-18-shortest-paths-ii-bellman-ford-linear-programming-difference-constraints/30분 정도부터 보면 된다. 간략히 말하자면 변수 x1 ... xn N개와, xj - xi
http://www.koistudy.net/?mid=prob_page&NO=2058 재밌는 문제.. 텔레포터를 타고 여기저기 옮겨나간다는 문제의 개념이 상당히 당황스러울 가능성이 높다. 막히지 않으려면 "그래프"라는 사실을 빠르게 파악해야 한다. 나뉘어진 선분 구간은 정점이고. 텔레포트는 간선이라는 것을 관찰하면 * 경로 간선의 개수를 최대화 * indegree와 outdegree는 모두 1이다 (시작 끝점 빼고) * 텔레포터의 설치는 두 정점 i, j의 나가는 간선의 교환이다 이 사실을 파악하면 문제가 상당히 깔끔해진다. 먼저 그래프의 성질을 관찰하자. * 컴포넌트 내의 indeg / outdeg가 모두 1이면 컴포넌트는 사이클을 이룬다. * 고로 그래프는 사이클 컴포넌트들의 집합이다.. 근데 시작 끝..
https://www.acmicpc.net/problem/3323 일전에 한번 멘붕이라고 언급한 적이 있었는데 (http://amugelab.tistory.com/entry/201573-2015723-problem-solving) 제대로 접근하면 아주 어렵지는 않다. 먼저 삼각형 쿼리를 뜯어보자. 한 점이 원점인 삼각형이면, 각도 범위 안에 있는 점들 중에서, 해당 선분 아래에 있는 점이 존재하는가? 를 묻는 문제가 됨을 알 수 있다.그러면 각도 범위를 무력화하면 어떨까..? 그러면 꽤 유명한 문제다. (https://www.acmicpc.net/problem/7057) 들어오는 점 집합을 Convex Hull만 남겨두고, 이진 탐색을 하면 풀 수 있다. 복잡한 설명은 생략.. 문제는 쿼리가 구간으로 들..
https://www.acmicpc.net/problem/2434http://koistudy.net/?mid=prob_page&NO=375 모든 점을 통괄하는 경로는 교차할 수 없기 때문에, 윗바닥과 아랫바닥을 먹는 두 선이 갈린다고 생각할 수 있다. 두 선의 상태는 그렇게 많지는 않아서, 이 "두 선"을 바탕으로 점화식을 세우는 것이 좋을 것이다. 나의 경우에는 다음과 같은 세개의 상태가 나왔다. * U[i] = i번 줄까지의 원소들을 다 봤고, i+1번째 줄의 위에서 1 - 2번째 원소에 발을 내린, 그 외에는 전혀 건들지 않은 상태 * M[i] = i번 줄까지의 원소들을 다 봤고, i+1번째 줄의 위에서 1 - 3번째 원소에 발을 내린, 그 외에는 전혀 건들지 않은 상태 * D[i] = i번 줄까지..
https://www.acmicpc.net/problem/2584 1. O(N^3)dp[node][k][state] 라는 N^2 점화식을 생각해보면 서브 트리에 대해서 http://amugelab.tistory.com/entry/CCC14-Stage-2-Werewolf 의 해법으로 풀 수 있다. 복잡도는 O(N^3). 2. O(N^2)이 문제에서 두 DP값은 DP[i] = min(DP1[j] + DP2[i-j]) 라는 방식으로 합쳐지는데, 내가 아는 한에서는 이는 O(N^2)보다 빠르게 계산할 수 없다. 아마 실제로도 계산할 수 없을 것이다. 증명은 못하지만...고로, 뭔가 다른 걸 궁리해야 한다 생각하기 쉬운데 답은 의외로 가까이에 있다. 두 서브트리 사이즈가 A, B이고 여기서 DP배열을 O(AB)에..
https://www.acmicpc.net/blog/view/10
nCr = n! / (n-r)! * r! 일 때, nCr mod prime을 빠르게 계산하는 방법에 대해서 얘기하려 한다. nCr 한 쿼리는 O(1)에 처리되어야 한다고 가정한다. (즉 전처리 한번 한 이후 nCr을 하나 계산하는데 O(1)) 1. O(n^2)위에 저 식을 그냥 구현만 해도 O(n) 인데..! 하지만 컴퓨터의 메모리는 한정되어 있으니 수를 그대로 들고 갈 수는 없고, mod p는 나눗셈을 하기 썩 좋은 상황은 아니다.그래서, nCr = (n-1)C(r-1) + (n-1)Cr 이라는 점화식(파스칼의 삼각형)을 사용해서 n^2에 계산하는 게 잘 알려져 있다. N^2 크기의 배열을 잡고 서서히 계산해 나가는 것이다. 이 방법은 나눗셈을 완전히 우회하는 방법으로써 사실 여러모로 제일 안정적인 방..
- Total
- Today
- Yesterday