algoshipda의 블로그

http://codeforces.com/blog/entry/8219

http://community.topcoder.com/stat?c=problem_statement&pm=2989&rd=5869 http://community.topcoder.com/stat?c=problem_statement&pm=3994&rd=6532 http://community.topcoder.com/stat?c=problem_statement&pm=1848&rd=4675 (DP) http://community.topcoder.com/stat?c=problem_statement&pm=3510&rd=6527 http://community.topcoder.com/stat?c=problem_statement&pm=3509&rd=6528 http://community.topcoder.com/stat?c=problem_statement&pm=4450&rd=7217 http://community.topcoder.com/stat?c=problem_statement&pm=1954&rd=5006 풀고싶다 http://community.topcoder.com/stat?c=problem_statement&pm=1849&rd=4675

동전 https://www.acmicpc.net/problem/2293 https://www.acmicpc.net/problem/2294 https://www.acmicpc.net/problem/2624 https://www.acmicpc.net/problem/9084 https://www.acmicpc.net/problem/2294 게임 DP https://algospot.com/judge/problem/read/NUMBERGAME https://www.acmicpc.net/problem/11062 중간에 잘라서 하는거 https://www.acmicpc.net/problem/11066 https://www.acmicpc.net/problem/11049 트리 DP (시간복잡도 계산에 주의) https://www.acmicpc.net/problem/2213 https://www.acmicpc.net/problem/2533 http://codeforces.com/problemset/problem/581/F https://www.acmicpc.net/problem/2584 https://www.acmicpc.net/problem/9013 https://www.acmicpc.net/problem/11503 https://www.acmicpc.net/problem/2197 https://www.acmicpc.net/problem/1805 http://www.spoj.com/problems/VOCV/ http://www.spoj.com/problems/PT07F/ http://www.spoj.com/problems/PT07X/ LIS https://www.acmicpc.net/problem/1666 https://www.acmicpc.net/problem/2568 https://www.acmicpc.net/problem/2565 비트마스크 https://www.acm

https://www.acmicpc.net/problem/10937 https://www.acmicpc.net/problem/1657 https://www.acmicpc.net/problem/11111 https://www.acmicpc.net/problem/8992 https://www.acmicpc.net/problem/3640 https://www.acmicpc.net/problem/11493 위 3문제는 MCF를 찾는건데 bellman-ford나 SPFA돌리면서 sink로의 cost가 양수 일때 중지 하면 된다. 8992번 문제는 정점을 공유하지 않으면서 최소 비용인 경로 2개를 찾는건데 정점을 공유하지 않는다는 조건은 한 정점을 두개로 분리하여 중간에 capacity가 1인 간선을 넣어줘서 만족 시킬 수 있다. 3640번 문제는 전형적인 MCMF 문제이다. 11493 : ACM ICPC 2015 대전 리저널 A번 문제 https://www.acmicpc.net/problem/1210 http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1616  (min cut) http://poj.org/problem?id=3041 (이분 매칭) https://www.acmicpc.net/problem/1867 https://www.acmicpc.net/problem/11375 https://www.acmicpc.net/problem/11376 https://www.acmicpc.net/problem/11377 https://www.acmicpc.net/problem/11378 http://community.topcoder.com/stat?c=problem_statement&pm=1931&rd=4709 https://www.acmicpc.net/problem/1348 https://www.acmicpc.net/problem/11495 https://www.

https://www.acmicpc.net/problem/11000 https://www.acmicpc.net/problem/1666 https://www.acmicpc.net/problem/1933 https://www.acmicpc.net/problem/1379 https://www.acmicpc.net/problem/1374 https://www.acmicpc.net/problem/11108 https://www.acmicpc.net/problem/10672

어떤 테스크가 N개 주어진다. 각 테스크는 시작시간, 종료시간, 가중치를 가지고 있다. 같은 시간에 2개 이상의 테스크를 처리할 수 없을 때 최대로 얻을 수 있는 가중치의 합을 구하라 https://www.acmicpc.net/problem/11108 https://www.acmicpc.net/problem/1666 (2차원이지만 접근법이 비슷하다고 생각함) 방법: 간단히 dp로 n^2에 풀 수 있지만 nlgn으로 줄일 수 있다.  테스크들의 시작점과 끝점을 분리하고 인덱스를 같이 저장하여 시간 순으로정렬한다. (이때 시작점인지 끝점인지 알 수 있도록 한다.) 정렬한 데이터를 선형으로 보면서 시작점일 경우 이전에 구한 최대값과 같이 계산해서 저장해 놓는다.(최대값을 바로 갱신하지 않는다.) 끝점일 경우 최대값을 갱신한다. (binary search로 현재 보는 테스크와 겹치지 않고 인덱스가 가장 큰 테스크를 찾아도 될것 같다.)

https://www.acmicpc.net/problem/1533 최대 가중치 5인데 한 정점을 정점 다섯개로 치환하고 모든 간선의 가중치가 1인것처럼 만든다. 그런식으로 만든 인접행렬을 거듭제곱하면 답을 구할 수 있다. http://codeforces.com/problemset/problem/621/E