본문 바로가기

분류 전체보기

BOJ)5542 JOI 국가의 행사 문제: icpc.me/5542 쿼리에서 받는 두 도시간의 경로 중 경로에 포함 된 도시들의 축제하는 도시와의 떨어진 거리의 값들 중 최솟값이 최대가 되는 경로를 구하는 문제이다. 우선 다익스트라 알고리즘을 사용하여 각 정점들의 가중치(축제가 열리는 도시와의 최단거리)를 구해줄 수 있다. 이후 쿼리를 처리해주어야 하는데 disjoint set을 이용하여 쿼리를 처리해주려고 한다. 우선 각 쿼리 번호에 해당되는 양 끝 정점들에 쿼리 번호들을 저장해준 뒤 간선의 가중치가 큰 순서대로 간선을 정렬하여 간선을 보면서 정점을 dsu를 이용하여 병합해 줄것이다. 이 때 만약 두 정점이 같은 쿼리 번호를 가지고 있다면 해당 쿼리 번호의 답은 그 간선의 가중치가 될 것이다. 1234567891011121314151617.. 더보기
BOJ)13330 유사 팰린드롬 문제: icpc.me/13330 w를 구성할 수 있는 세타 팰린드롬의 최소 개수를 출력하는 문제이다. 이 문제를 해결하기 위하여 두가지 디피 테이블을 정의해야한다. dp1[l][r]은 l,r 구간의 u의 개수 dp2[pos]는 0~pos 의 문자열을 구성 할 수 있는 세타 팰린드롬의 최소 개수라 정의하면 n^2으로 dp2를 채우기 위해 for문을 돌릴 때 이터레이터 j에 대한 검사를 dp1으로 할 수있다. 123456789101112131415161718192021222324252627282930#include #include #include using namespace std;int n, k, l, dp[10010];int a[10010][10010];char s[10010];int func(int l.. 더보기
BOJ)13352 석양이 진다... 문제: icpc.me/13352 n개의 점들이 주어질 때 두직선만으로 모든 점을 커버가능한지 판별하는 문제이다. 얼마전 코포 B번에서 유사한 문제 http://codeforces.com/contest/849/problem/B 가 등장하였지만 코포 문제는 N^2으로 해결할 수 있었던 반면 이 문제는 N제한이 10만이기 때문에 N^2으로는 풀 수 없다. 그래서 정해를 생각해보다가 도저히 떠오르지 않아서 작년에 들었던 야매 풀이를 떠올려서 풀었다. 풀이는 랜덤하게 두 점을 뽑아서 직선을 하나 만든 다음 나머지 모든 점이 한 직선으로 놓일 수 있는지 확인한다. 여기서 나머지 모든 점이 한 직선으로 놓인다면 당연히 두직선으로 커버되는 것이니 답이 되고 안된다면 위의 행동을 반복한다. 위의 행동을 충분히 반복하였는.. 더보기
BOJ)5842 Partitioning the Farm 문제: icpc.me/5842 n*n 격자가 주어질 때 주어진 격자를 가로나 세로로 k번 분할 할 수 있다. 분할 된 각 부분들의 합의 최댓값의 최솟값을 구하는 문제이다. 최대중에 최소를 구하는 문제이므로 파라메트릭 서치로 접근할 수 있다. 다만 격자에서 처리해야하는게 좀 까다로울 수 있는데 n이 15밖에 안되므로 2^15의 모든 경우로 세로 격자를 세워준 뒤 파라메트릭 서치로 가로 격자를 세우며 답을 구할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include #include #include using name.. 더보기
BOJ)2337 트리 자르기 문제: icpc.me/2337 트리에서 임의의 몇개의 간선을 잘라서 크기가 m인 트리를 얻고 싶을 때 잘라야하는 간선의 최소 개수를 구하는 문제이다. 트리디피로 풀 수 있는 문제이다. 기존에는 트리 디피를 n^3의 방법으로 풀어왔지만 이번에 smu형님의 도움으로 n^2 log n으로 푸는 방법을 알게 되었다. 우선 dp테이블을 dp[here][k]를 here번 정점이 루트인 크기가 k인 트리를 만드는데 필요한 간선컷의 최솟값으로 정의하면 dp[here][k]를 어떤식으로 빌드할거냐면 here가 가지는 자식들은 여러개의 서브트리를 이룰것이다. 이 서브트리를 하나씩 병합하면서 dp[here][k]를 채울 것이다. 당연히 처음에는 dp[here][1]밖에 없을 것이다 .여기서 1은 곧 자기 자신이다 이는 0으.. 더보기
deque를 이용한 다이나믹프로그래밍 BOJ)5977 Mowing the Lawn 라는 문제를 풀 때 이용한 테크닉이다. 문제: icpc.me/5977 시퀀스가 주어질 때 주어진 시퀀스에서 수를 선택하여 최댓값을 만들어야 하는데 수를 연속으로 k이하로 선택가능할 때 답을 출력하는 문제이다. 예를 들어서 n이 5고 k가2라면 (1,2) (4,5) 이런식으로 연속된 수열은 최대 k까지 선택하여야 한다. 문제만 보면 당연히 다이나믹 프로그래밍을 떠올릴 수 있다. 하지만 점화식을 세우다보면 n이 너무 크기때문에 곤란할 수 있다. 하지만 일단 점화식을 세워보자 dp[i]는 i번째 인덱스까지 수열을 처리하였을 때 최댓값이라고 정의를 한다면 dp[i] =max(psum[i]- psum[j]+ dp[j-1]) j:(i-k+1 ~ i) 라는 수식이 세워진다.. 더보기
BOJ)11003 최소값 찾기 문제: icpc.me/11003 구간 n에서 ai-l+1 ~ai의 최솟값을 매번 찍어내는 문제이다. RMQ 문제로 생각하여 세그트리나 multiset을 이용한 풀이를 예전에 제출했지만 n이 너무나도 커서 tle를 맞은 후 잊고 있던 문제였지만 오늘 다른 문제에서 다이나믹프로그래밍을 공부하다가 필요에 의해 다시 풀게 된 문제이다. 이 문제는 deque를 이용하여 해결할 수 있다. 연속 된 시퀀스에서 deque에는 pair형으로 해당 값과 해당 인덱스를 가지고 있을것이다. 우리는 답을 출력할 때 deque에 삽입 되어있는 구간에서 최솟값을 출력해야 하기때문에 앞이나 뒤에 최솟값을 가지고 있어야한다. 일단 deque의 front에 최솟값을 가지고 있다고 해보자. 그러면서 만약 deque의 front의 값의 인.. 더보기
BOJ)1460 진욱이의 농장 문제: icpc.me/1460 n*n 크기의 격자에 씨를 뿌리는 방법이 주어지고 격자에서 임의의 정사각형을 선택하여 정사각형 내부의 점에 서로 다른 씨앗이 최대 2개가 되도록 정사각형을 선택할 때 가장 넓은 정사각형의 넓이를 출력하는 문제이다. 씨앗의 종류인 F의 범위가 0~7인걸 이용하여 F^2+F로 모든 경우의 씨앗을 정한다면 현재 상태에서 해당하는 씨앗이 뿌려져있는 가장 넓은 정사각형을 구하는 문제로 치환하여 풀 수 있다. 이는 다이나믹 프로그래밍을 이용하여 n^2에 해결할 수 있다. 1234567891011121314151617181920212223242526272829303132333435#include #include #include using namespace std;int res, a[10.. 더보기
BOJ)13548 수열과 쿼리 6 문제: icpc.me/13548 길이가 N인 수열이 주어질 때 구간 i j 사이에 가장 많이 등장한 수가 몇번 등장했는지 출력하는 문제이다. 이 문제를 온라인으로 수행하려고하면 굉장히 힘들어 보인다. 하지만 업데이트가 이루어지지 않기 때문에 오프라인 쿼리 문제로 변형시켜서 풀어볼 수 있다. 따라서 이 문제를 mo's algorithm을 이용하여 풀건데 가장 많이 등장하는 수를 결정해야 하기 때문에 현재까지 가장 많이 등장하는 수를 계속 가지고 있어야하고 각각의 수가 몇번 등장하였나 배열을 a, i번 등장한 수가 몇개 있나 배열을 b에 각각 저장해두면 현재 쿼리의 답이 x면 만약 add로 인하여 추가 된 b가 x보다 크다면 x를 증가시켜주고 erase로 인하여 x만큼 등장한 수가 없어진다면 x를 감소시켜주.. 더보기
BOJ)2419 사수아탕 문제:icpc.me/2419 사탕이 담긴 사탕바구니가 x축위에 있고 1초마다 사탕 바구니의 사탕이 1개씩 사라질 때 수아가 먹을 수 있는 최대의 사탕 수를 구하는 문제이다. 문제가 다이나믹 프로그래밍임은 쉽게 알 수 있었지만 먹을 수 있는 최대의 사탕수에 포커스를 맞추니 어려워진 문제였다. 이를 dp[l][r][state]로 해결해야하는데 l에서 r까지 사탕을 커버하고 state(왼,오)에 서있을 때 먹는 최대의 사탕수라고 정의를 한 뒤 제출을 하니까 WA를 받았다. 다시 잘 생각해보니 l~r을 커버할 때 나머지 구간에 사라진 사탕수가 항상 최적으로 있을 수 없다는 걸 깨달았다. 따라서 dp테이블의 정의를 바꾸어 l에서 r까지 구간을 커버하고 사라지는 사탕 수로 문제를 풀어야한다. 근데 이 또한 사라지는.. 더보기