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
https://en.wikipedia.org/wiki/Karger's_algorithm 그래프에서의 Minimum Cut은 그래프의 컴포넌트를 2개로 쪼개는 데 삭제해야 하는 간선의 개수를 뜻한다. (가중치를 붙여서 일반화한 경우도 있다. 지금 소개하는 알고리즘은 그 경우는 해결하지 못하는 걸로 알고 있음)이 중 정점 S와 T의 Minimum Cut을 구하는 것은 (즉, S와 T를 서로 다른 컴포넌트로 쪼개는 데 필요한 간선수) 알고리즘이 알려져 있다. (http://amugelab.tistory.com/entry/%EC%9C%A0%EB%9F%89-%EA%B4%80%EB%A0%A8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%A0%95%EB%A6%AC) Minimum Cut의..
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