algoshipda의 블로그

문제 :  https://www.acmicpc.net/problem/13208 전에는 못 풀었는데 드디어 풀었다~ $state[a][b]$ : 조승현13이 $a$에 있고 조승현16이 $b$에 있는 상태 를 정점으로 하고 $c[a] * c[b]$를 정점의 비용으로 가지는 그래프를 생각해보자. 우리가 해야 할 것은 $state[a][b]$에서 $state[b][a]$로 가기 위해서 지나가는 정점들의 비용의 최대값을 최소화 하는 것이다. 만약에 문제가 정점의 비용을 최소화하는게 아니라 간선의 비용을 최소화하는 문제였다면 MST를 만들어서 구할 수 있을 것 같았다. 비슷한 아이디어로 정점의 비용이 작은 것부터 큰 것 순으로 보면서 트리를 만들어보기로 했다. 과정은 대략 다음과 같다 1. 정점을 비용순으로 정렬하고 비용이 작은 것 부터 본다. 2. 현재 보고 있는 정점이 $u$라고 하자 3. $u$와 인접한 정점들을 본다. 인접한 정점은 $v$라고 하자. 4. 만약 $u$와 $v$가 다른 집합에 속하는데 $v$의 비용이 $u$의 비용보다 작거나 같다면 $u$와 $v$를 같은 집합으로 합친다. 그리고 간선$(u, v)$를 따로 저장한다. 위 과정을 반복해서 나오는 간선들을 모으면 트리가 된다. 또한 이 트리상의 경로로만 이동하면 문제에서 요구하는 답을 찾을 수 있다. 직관적으로 이해할 수 있으므로 증명은 생략한다. 이제 문제는 트리에서 두 정점을 연결하는 경로상에 있는 정점의 비용 중 최대값을 찾는 문제로 바뀐다. 이건 LCA 를 이용하면 각 쿼리를 $O(lgN)$에 처리할 수 있다. 문제를 푸는 총 시간 복잡도는 시간 복잡도는 아마 $O(N(N+M)+QlgN)$이 될 것 같다. (먼저 맞은 사람들 코드를 보니깐 더 빠른 방법이 있나 보다.) 코드 :  http://ideone.com/eBn2sQ

길이 $N$인 문자열 $S$의 서로 다른 부분 문자열의 개수를 세는 문제이다. 방법 1) Suffix Array + LCP $O(NlgN)$에 해결할 수 있다. 다른 곳에서 많이 볼 수 있는 풀이이다. 방법 2) 트라이 $O(N^2)$에 해결할 수 있다. 트라이에 $S$의 ${N(N + 1)} \over 2$개 부분 문자열을 모두 넣으면 최종적으로 트라이에 존재하는 노드의 수 - 1(루트 제외)이 답이 된다. 방법 3) 해싱 $O(N^2lgN)$에 해결할 수 있다. $S$의 ${N(N + 1)} \over 2$개 부분 문자열을 해싱하면서 유니크한 해싱값들의 수를 세면 된다. 코드 (트라이) :  http://ideone.com/bugbDy 코드 (해싱) :  http://ideone.com/hkjw5n

일반적인 구간 업데이트 쿼리 처리 문제는 Lazy propagation을 구현한 세그먼트 트리로 풀 수 있다.  좀 더 특수한 경우의 문제로 먼저 구간 업데이트 쿼리가 쭈~욱 주어지고, 업데이트 쿼리의 중간에는 다른 쿼리를 처리할 필요가 없는 문제를 생각할 수 있다. 이런 경우의 문제는 구간 업데이트 쿼리를 각각 $O(1)$에 처리할 수 있다. 길이 $N$인 배열 $A$가 주어졌다고 하자. 편의상 인덱스를 $1 \sim N$으로 쓰고 $A[0]$에는 $0$이 들어있다고 생각하자. 그리고 다른 배열을 정의하겠다. $S[i]$ : 구간 업데이트 쿼리에 의해 $A$의 $[l, \infty]$에 일정하게 더해진 값 $P[i]$ : $A[0]$ ~ $A[i]$의 구간합 만약 $S$를 알고 있다고 하면 $P[0] = 0$ $P[i] = P[i - 1] + S[i] + A[i]$ 가 된다. $S$는 구간 쿼리가 구간 $[l, r]$에 $x$를 일정하게 더해라는 식으로 들어오면 $S[l]$에 $x$를 더하고 $S[r + 1]$에 $x$를 빼서 처리할 수 있다. 설명하려고 $S$와 $P$를 따로 썼지만 실제 구현에서는 하나의 배열로 처리해도 무방하다.  -------------------------------------------------------------- 관련 문제 http://codeforces.com/gym/100571/problem/B https://www.acmicpc.net/problem/12746

문제 :  https://www.acmicpc.net/problem/2401 각각의 짧은 문자열들이 긴 문자열에서 어디에 등장하는지만 알 수 있다면, 이 문제는 전형적인 다이나믹 프로그래밍 문제가 된다. 그러니깐 KMP를 돌리면서 테이블을 채우면 된다. 시간 복잡도는 긴 문자열 길이 $S$, 짧은 문자열 길이 $T$, 짧은 문자열의 수 $N$이라 할때 $O(N * (S + T))$가 된다. 코드 :  http://ideone.com/zloOUb

문제 :  https://www.acmicpc.net/problem/1034 램프에 $K$번의 조작을 다 하고 나서 최종적으로 몇 개의 행의 불이 완전히 켜져있다고 생각해보자. 불이 완전히 켜져있는 행들은 초기에 서로 켜져있는 불의 상태가 완전히 같았어야한다. 왜냐하면 램프에 가해지는 조작은 열 단위로 가해지기 때문이다.  위 사실을 알고나면, 문제를 이렇게 생각할 수 있다. $K$번의 조작을 해서 어떤 행의 불을 완전히 켤 수 있는가? 만약에 켤 수 있다면 그 행과 똑같이 생긴 행의 수를 답으로 고려해 볼 수 있고, 최종 답은 그러한 행의 수 중 최대가 된다. 이제 $K$번의 조작을 해서 어떤 행의 불을 완전히 켤 수 있는지를 알 수 있으면 되는데, 이는 처음에 꺼져있는 열의 수보다 $K$가 크거나 같을 때 홀짝만 잘 따지면 알 수 있다. 코드 :  http://ideone.com/tcrFIU

문제 : https://www.acmicpc.net/problem/1727 더 쉬운 문제로 남녀 모두 $k$명이 있는 문제를 생각해보자. 이 경우는 두 집합을 각각 정렬한 뒤 그 순서에 맞게 매칭을 시키면 최적이 된다. 본 문제는 남자 $n$명, 여자 $m$명 $($$n >= m$ 이라 가정$)$이라 할때, 매칭될 남자 $m$명을 고르는 문제로 생각할 수 있다. 남녀 집합을 모두 정렬하고 테이블을 아래와 같이 정의하자. $D[i][j]$ : 남자 $i$번, 여자 $j$번까지 매칭($j$쌍 커플) 했을 때 최소 성격 차이의 합. 상태전이는 LCS와 비슷하게 시켜주면 된다. 코드 : http://ideone.com/ehzO4C

문제 : 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로 가는...

애니 티버가 서로 봤을 때 좌우 관계가 반대인 쌍의 수를 세는 문제이다. 각도로 정렬하면 답이 되는 경우는, 정렬된 배열 상에서 애니가 기준으로 보는 별의 왼쪽에 있는 별이 티버 배열에선 오른쪽에 있는 경우이다. 이는 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

#340 Div2 E번 문제에 나왔습니다. http://codeforces.com/blog/entry/7383 http://blog.anudeep2011.com/mos-algorithm/ Mo's algorithm?  공부합시다. http://codeforces.com/contest/617/problem/E http://codeforces.com/contest/86/problem/D http://codeforces.com/contest/86/submission/15905761 http://www.spoj.com/problems/DQUERY/ http://ideone.com/OLG0dB http://codeforces.com/blog/entry/23005

https://www.acmicpc.net/problem/11583 trailling zero를 최소화 한다는 것은 그 수를 소인수분해 했을때 2와 5의 지수 중 작은 것을 최소화 하는 것과 같다. 2의 지수만을 보고 구한 것과 5의 지수만을 보고 구한 것 중 작은 값이 답이 된다. 이것은 다이나믹 프로그래밍으로 쉽게 구할 수 있다.

https://www.acmicpc.net/problem/1587 생각해보면 A집합 정점 갯수와 B집합 정점 갯수 둘 중 하나라도 짝수인 것이 있으면 같은 집합내에서 인접한애들끼리만 짝지어도 무조건 최대를 만들 수 있다는 것을 알 수 있다. 만약 둘 다 홀수라면 A의 홀수번 정점에서 B의 홀수번 정점으로 가는 것 말고는 이득을 볼 것이 없다는 것을 알 수 있다. 따라서 A의 홀수번 정점에서 B의 홀수번 정점으로 가는 간선이 있는지만 체크해서 답을 구하면 된다.

INC 2007 H번 https://www.acmicpc.net/problem/7812 루트를 하나 잡고 DFS를 통해 루트에서 다른 모든 정점으로 가는 비용의 합을 구해 놓는다. 이 때 정점 u(1 ~ n)를 루트로 하는 서브트리의 정점 갯수도 구해 놓는다. 다시 DFS를 돌리는데 이때 처음에 루트에서 아까 구한 비용의 합을 들고 시작하면서 최소답을 갱신시켜 나간다. cost(u, v) = 간선(u, v)의 비용 count(u) = u를 루트로 하는 서브트리의 정점의 갯수 라 하자. 간선(u, v)를 탈때 cost(u, v) * count(v) 만큼 답이 줄어들고 cost(u, v) * (n - count(v)) 만큼 답이 늘어나는걸 이용하면 된다. 시간 복잡도는 O(N). 답이 int범위를 벗어 날 수 있음에 주의한다.

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...