본문 바로가기

알고리즘 관련

BOJ)1514 자물쇠 문제: icpc.me/1514 비밀번호 A를 B로 바꾸기 위한 최소 돌림의 횟수를 구하는 문제이다. 동적 계획법을 통해 문제를 해결 할 수 있다. dp[pos][x][y][z][flag]=> pos번 째 자물쇠를 볼 때 x: pos번 자물쇠를 돌린 범위 y: pos+1번 자물쇠를 돌린 범위 z:pos+2번 자물쇠를 돌린 범위(flag는 자물쇠를 돌리는 방향성) 123456789101112131415161718192021222324252627282930313233343536373839#include #include #include using namespace std;int n, a[110], b[110], dp[110][10][10][10][2];int modulo(int x) { while (x 더보기
BOJ)5721 사탕 줍기 대회 문제: icpc.me/5721 최대로 가져갈 수 있는 사탕의 수를 구하는 문제이다. 동적 계획법으로 문제를 해결 가능하다. dp[x][y][z] = x-1행 까지 모든 사탕상자와 x행의 y행 까지의 사탕상자를 커버했을 때 가질 수 있는 최대 사탕 개수(이 때 z는 x행에서 사탕상자를 한번이라도 커버했는 지 여부이다) 이렇게 정의를 해주면 dp[x][y][z]= max(a[x][y]+ dp[x][y+2][1], dp[x][y+1][z]) 라는 대략적인 점화식이 세워진다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include #include #include using namespace std;vecto.. 더보기
BOJ)11560 다항식 게임 문제: icpc.me/11560 문제를 풀기 위하여 k:0~20 에 대한 p(x)를 모두 구하여도 시간내에 충분히 수행가능하다. 따라서 미리 계산을 다 해준 뒤 쿼리를 받을 때 마다 출력해주면 된다. 123456789101112131415161718192021222324252627282930313233343536#include #include #include using namespace std;typedef long long ll;vector b, a;ll x, y, z;int main() { for (int i = 3; i 더보기
BOJ)10276 Jewelry Exhibition 문제: icpc.me/10276 각 행이나 열에 빛을 발사해서 보석들을 지킬 때 모든 보석들을 지키는 최소한의 빛의 수를 구하는 문제이다. x행 y열의 위치에 존재하는 보석을 x정점과 y정점을 잇는 간선이라고 생각한다면 결국 모든 보석을 지키는건 각 행(정점)들을 몇개 선택하여 모든 간선을 커버하는 문제로 치환되므로 최소 버텍스 커버 문제로 볼 수 있다. 이분 그래프에서의 최소 버텍스 커버 문제는 쾨닉의 정리에 의해 이분 매칭으로 해결할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243#include #include #include #include using namespace std;int t, n, m,.. 더보기
BOJ)1999 최대최소 문제: icpc.me/1999 n*n 행렬에 값이 주어져 있을 때 한 지점에서 부터 시작한 b*b 크기의 부분 행렬에서의 최댓값-최솟값을 출력하는 문제이다. 2차원 세그먼트 트리를 이용하면 O(K*NlogN)에 해결할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #include #include using namespace std;int n, b, k, minseg[251][250 * 4], maxseg[251][250 * 4], a[251][251];int minupdate(int *tree, int pos, int val, int node, int x,.. 더보기
BOJ)13511 트리와 쿼리2 문제: icpc.me/13511 트리에서 2가지 종류의 쿼리를 수행하는 문제이다. 1번 쿼리의 경우 정점들의 거리와 같은 문제로 트리의 루트로 부터 정점 x로의 거리를 dist[x]라고 하였을 때 1번 쿼리의 답은 dist[u]+dist[v]-2*dist[lca(u,v)]가 된다. 왜 이렇게 되는지는 그림을 그려보면 쉽게 알 수 있다. 2번 쿼리는 lca를 구할 때 만든 sparse table을 이용해줄 수 있다.(선형으로 탐색할 경우 시간초과를 피할 수 없다.) 만약 dph[x]-dph[lca]가 z-1보다 크거나 작다면 x를 z-1번 올려주면 되고 (올려줄 때 sparse table을 이용하여 log시간에 올려주어야 한다.) 아닌 경우 두 경로사이에 속한 정점의 수 -z 만큼 y를 올려준다. 1234.. 더보기
BOJ)14657 준오는 최종인재야!! 문제:icpc.me/14657 문제를 해석해보자면 최대한 많이 문제를 푸는건 결국 주어진 트리를 가중치 없는 그래프에서의 지름에 해당 되는 정점들을 선택하는 경우이다. 하지만 같은 크기를 가지는 지름이 많을 수 있기 때문에 모든 지름을 탐색해야한다. 이를 위하여 지름의 중심이 되는 점을 찾은 뒤 그 점부터 이동 가능한 가장 먼 leaf로의 최단거리를 탐색한 다음 계산해준다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283#include #include #include #in.. 더보기
BOJ)2300 기지국 문제: icpc.me/2300 모든 건물을 커버하는 기지국들을 세울 때 기지국의 설치비용의 최솟값을 구하는 문제이다. n이 10000이고 시간 제한이 2초이기 때문에 n^2 dp를 생각해볼 수 있다. dp[i]= MIN[for(j: 0~i-1) : dp[j]+max(wide[i]-wide[j-1],2*maxheight) ] 라는 점화식이 나온다. 1234567891011121314151617181920212223242526#include #include using namespace std;typedef long long ll;ll n, dp[10010];pair a[10010];int main() { scanf("%lld", &n); for (int i = 1; i 더보기
BOJ)11985 오렌지 출하 문제: icpc.me/11985 오렌지를 연속적으로 M개 이하 씩 포장할 때 포장비용이 주어질 때 전체를 포장했을 때 포장비용의 최솟값을 출력하는 문제이다. 이 문제는 다이나믹 프로그래밍으로 해결할 수 있다, DP[i]= i까지 포장하는데 필요한 최소 비용 이라고 생각하면 for( j= i-m+1~i)에 대해서 MIN(dp[j-1]+k+(i-j+1)*(max(i~j)-min(i~j))가 된다. 123456789101112131415161718192021#include #include using namespace std;typedef long long ll;ll n, m, k, dp[20020], a[20020];int main() { scanf("%lld%lld%lld", &n, &m, &k); for .. 더보기
BOJ)10637 Minimum Spanning Tree 문제: icpc.me/10637 간선들의 셋이 주어진다. 출력해야하는 답은 각 간선마다 자신을 제외한 간선들로 만들 수 있는 MST의 가중치의 합을 출력하는 문제이다. 이건 MST에 포함 안되는 간선에 대한 답은 MST의 가중치가 되겠지만 아닌 경우가 문제가 된다. 그렇다면 아닌 경우에 대해 생각해보자. 만약에 MST에 포함되지 않는 간선이 u-v 를 연결한다고 생각해보자 그러면 우리는 mst에서 u v를 잇는 경로상의 어떤 간선을 지워도 이 간선을 통하여 MST를 유지 할 수 있다. 즉 이러한 사실을 이용하여 MST를 만들 때 사용되지 않은 간선들을 가중치 순서대로 정렬하여 오프라인으로 미리 mst상에 사용 된 간선들의 답을 정해주는 것이다. 여기서 매번 경로를 확인해준다면 당연히 TLE를 보게 될 것.. 더보기

티스토리툴바