algoshipda의 블로그

http://gyuha.tistory.com/157

문제 : https://www.acmicpc.net/problem/1006 DP[i][j] : i 번째 열, j타입일 때 남은 열을 적절히 놓아서 만들 수 있는 최소 침투 소대수라고 정의하고 다이나믹 프로그래밍으로 풀면 된다. 이 문제에서 까다로운 점은 구역이 원형으로 연결돼 있다는 점인데, 이는 처음과 끝에 이미 몇개의 소대를 보내 놨다고 생각 (이러면 선형구조로 생각할 수 있음) 하고, 그 경우에 대해 모두 돌려보면 된다. 길이 N에 처음과 끝을 가정하는 경우의 수는 상수번 이므로 O(N)에 풀린다. 코드 : http://ideone.com/XPpr2X 비슷한 문제 (이 문제를 푸는데 동원된 아이디어와 비슷한) : https://www.acmicpc.net/problem/9465 https://www.acmicpc.net/problem/2133 https://www.acmicpc.net/problem/2482 https://www.acmicpc.net/problem/4017

문제 : https://www.acmicpc.net/problem/1007 점이 n 개 있으면 n / 2개의 벡터를 만들 수 있다. 이 n / 2개의 합벡터를 생각해보면, n / 2개의 점은 더해지고, 나머지 n / 2개의 점은 빼진다(벡터 하나를 u - v로 표현). 즉, 이 문제는 n개의 점에서 합벡터를 만들 때 더해질 점을 n / 2개 고르는 문제로 생각 할 수 있다. n이 20이라 완전탐색을 짜도 n C n/2 만큼 탐색하게 되므로 시간안에 들어올 수 있다. 소스 : http://ideone.com/ctYs2L

https://www.acmicpc.net/problem/1005 문제에서 주어지는 테크트리대로 문제 예제와 비슷하게 그래프를 그려보면 DAG 형태가 된다. 이 문제는 DAG(directed acyclic graph, 사이클이 없는 방향 그래프)에서 가장 긴 경로의 길이를 구하는 문제인데, 다이나믹 프로그래밍으로 풀 수 있다. T[i] = i 번째 건물이 지어지기 위해 게임시작부터 걸리는 최소 시간이라고 하자. 최소 시간이라고 했지만, 사실 T[i]는 i번째 건물에서 끝나는 가장 긴 경로의 길이이다.. C[i] = i 번째 건물'만'을 짓는데 걸리는 시간이라고 하자. T[i]는 i번째 건물을 짓기 위해 지어야하는 선행 건물 j들의 T[j] + C[i]의 최대값이 된다. 이런 종류의 문제를 반복적 DP로 풀려고 하면, 상태의 의존 관계에 따라 테이블의 계산 순서를 정해줘야 한다. 이 문제의 경우는 그래프를 위상정렬 한 순서대로 테이블을 채워주면 된다. (재귀로 풀면 의존관계를 고려하지 않아도 돼서, 훨씬 속편합니다.) 코드 : http://ideone.com/tR0Wb1 비슷한 문제 : https://www.acmicpc.net/problem/1948 http://codeforces.com/problemset/problem/615/B https://www.acmicpc.net/problem/2631

구간 쿼리를 처리해야 하는 문제에서 구간 트리나 인덱스 트리를 대신해서 쓸 수 있는 방법입니다. (따라서 구간 트리나 인덱스 트리로 풀 수 있는 문제의 대부분을 평방 분할로 풀 수 있습니다.) 핵심은 길이가 N인 배열에서 sqrt(N) 길이의 구간마다 대표값을 구해 놓는다는 것입니다. 이렇게 대표값을 구해놓으면 Q개의 구간 쿼리를 O(Q * sqrt(N))의 시간복잡도로 처리 할 수 있습니다. 관련 문제 :  https://www.acmicpc.net/workbook/view/346 예제 :  https://www.acmicpc.net/problem/1275 - 문제 http://ideone.com/I7vkPa - 코드 (구간합을 다뤘지만 최소값, 최대값 등등 응용 가능합니다.) 심화 :  Mo's Algorithm (평방 분할 + 쿼리 정렬) http://blog.anudeep2011.com/mos-algorithm/

문제 :  http://codeforces.com/contest/629 A. 각 열과 행마다 C의 개수를 세고 kC2 만큼 더해주면 된다. O(n^2) 코드 :  http://ideone.com/8i1SUj B. 모든 날짜에 대해 돌면서 세보면 된다. O(n * 366) 코드 :  http://ideone.com/I7k54a C. DP[open][len] = 안 닫힌 열린 괄호 수가 open이고 길이가 len인 경우의 수 라고 정의하고 왼쪽과 오른쪽에 놓을 수 있는 열린(닫힌) 괄호의 수를 계산해서 답에 더해주면 된다. O((n - m)^2) 코드 :  http://ideone.com/jo81en D. LIS와 비슷하다. DP[i] = i번째 케이크를 제일 밑에 깔고 그 위에 적절히 쌓아서 만들 수 있는 최대 케이크의 부피라고 정의하자. 주어진 케이크 n개의 초기 인덱스와 부피를 계산해서 저장해놓고 부피순으로 정렬하고, 정렬된 순서대로 DP테이블을 채워 나간다. 이렇게 하면 해당 DP테이블을 채울 때 필요한 테이블의 값은 언제나 정확하게 들어가 있게 된다. DP[i]를 채울 때 j < i 이면서 DP[j]가 최대인걸 찾아야 하는데, 이는 세그먼트 트리같이 구간 최대 쿼리를 처리할 수 있는 자료구조를 사용하면 찾을 수 있다. 부피가 같은 케이크는 같이 쌓을 수 없다는 점만 주의해서 처리하면 풀 수 있다. O(nlgn) 코드 :  http://ideone.com/WrdiFa E. r(u, v) = 정점 u와 v의 길이 기대값 일단 r(u, v)에는 u와 v의 거리가 언제나 더해진다.(u에서 v로 가는 경로에 속하는 정점에 간선을 놓는 경우에는 u, v를 포함하는 사이클이 생기지 않는다.) size(u, v) = u에서 출발하여, u에서 v로 가는 경로를 경유하지 않고 도달할 수 있는 정점의 개수 sum(u, v) = u에서 출발하여, u에서 v로 가는 경로를 경유하지 않고 도달할 수 있는 정점들과 u간

애니 티버가 서로 봤을 때 좌우 관계가 반대인 쌍의 수를 세는 문제이다. 각도로 정렬하면 답이 되는 경우는, 정렬된 배열 상에서 애니가 기준으로 보는 별의 왼쪽에 있는 별이 티버 배열에선 오른쪽에 있는 경우이다. 이는 inversion의 수와 같다. 머지소트를 짜거나, 구간합을 계산할 수 있는 자료구조를 쓰면 된다. https://algospot.com/judge/problem/read/ANNIETIBBER http://ideone.com/mRtIr4

N개의 행성의 좌표가 주어진다. 그리고 M개의 미사일이 있는데, 이 미사일은 행성을 공격하면 행성의 좌표가 (x, y) 라 할 때 (0, 0) ~ (x + T, y + T) 의 사각형에 있는 모든 행성을 없앤다. 문제는 M개의 미사일로 N개의 행성을 모두 파괴하기 위해 필요한 최소 T이다. 생각해보면 어떤 행성 a가 다른 행성 b의 x, y 좌표가 모두 이하라면 a 행성보다 b 행성을 쏘는게 무조건 이득이다. 이를 바탕으로 실제로 고려대상이 되는 행성만 추려낼 수 있다. (정렬 후 스택을 써서 추려냈다.) 추려내고 나면 답을 t로 가정했을 때, 가능한지 안한지를 O(N)으로 구할 수 있다. 만약 어떤 t에서 가능했으면 t보다 큰 값에 대해선 무조건 가능하니깐 파라매트릭 서치를 쓸 수 있다. 요약 : 고려해야 하는 행성만 추려낸 뒤, 파라매트릭 서치 https://community.topcoder.com/stat?c=problem_statement&pm=13373 http://ideone.com/LNXnwt