본문 바로가기

알고리즘 관련/BOJ

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를 보게 될 것.. 더보기
BOJ)2261 가장 가까운 두 점 문제:icpc.me/2261 가장 가까운 두점을 N^2보다 적은 시간에 구해야하는 문제이다. 우선 점들을 x좌표 기준으로 스위핑해보자. 이후 x좌표가 증가하는 순서대로 점들을 볼건데 이미 본 점들은 y좌표 기준으로 정렬이 되도록 set에 삽입해준 후 지금까지의 최단거리가 d라면 현재 볼 점의 x좌표가 d이상 차이나거나 y좌표가 d이상 차이나는 점들을 제외하고 비교해준다. x좌표가 정렬 된 순서로 보기 때문에 포인트를 잡아서 기록해두면 x좌표가 차이나는 점들은 set에서 제거해줄 수 있고 y좌표는 lower_bound와 upper_bound를 통하여 탐색 지점을 정해놓고 비교해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373.. 더보기
BOJ)5038 Flight Planning 문제: icpc.me/5038 트리가 주어질 때 하나의 간선을 삭제하고 다시 하나의 간선은 연결하여 만든 트리의 지름이 최소가 되도록 하는 문제이다. N제한이 2500밖에 안되기 때문에 모든 간선을 다 삭제해 본 뒤 지름을 비교해보는걸 생각해볼 수 있다. 그렇다면 하나의 간선을 제거하였을 때 트리의 지름이 최소가 되도록 간선을 이어붙이려면 어떻게 붙여야할까? 바로 트리의 반지름을 이용하면 된다. 트리의 간선을 하나를 제거하면 두개의 트리가 생기게 된다. 이 때 두 트리의 반지름을 각각 구해준 뒤 반지름을 형성하는 정점들 사이에 간선을 연결하면 트리의 지름은 max(트리1의 지름,트리2의 지름,트리1의 반지름+트리2의 반지름+1)이 된다. 따라서 모든 경우에 대하여 트리의 지름을 구해준 뒤 비교하여 답을 .. 더보기
BOJ)8872 빌라봉 문제: icpc.me/8872 문제의 내용을 풀어서 설명하면 결국 포레스트가 주어졌을 때 해당 포레스트에 몇개의 간선을 추가하여 만들어진 트리의 지름의 최솟값을 구하는 문제이다. 문제의 답은 세 경우중 하나가 될 수 있는데 1.기존의 포레스트내의 트리에서의 지름중 최댓값 2-3. 포레스트 내부의 서브트리들의 반지름 중 가장큰 반지름을 가지는 서브트리에 나머지 반지름들을 길이 L로 연결하였을 때2.가장 긴 반지름 + 두번째로 긴 반지름 +L3.두번째로 긴 반지름 + 세번째로 긴 반지름 +L+L 이 세값 중 최댓값이 답이된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555.. 더보기
BOJ)1444 숌 언어 문제:icpc.me/1444 대문자와 소문자가 번갈아 나타나는 문장이 주어질 때 대문자와 소문자로 이루어진 최소 몇개의 단어로 문장을 만들 수 있는지를 출력하는 문제이다. 이 문제는 (대문자,소문자)로 이루어진 단어와 (소문자,대문자)로 이루어진 단어의 이분 그래프로 나타내면 최소 버텍스 커버 문제로 치환하여 해결할 수 있다. 예를들어 AaAbBa라는 단어가 있을 때 Ab라는 정점과 bB라는 정점이 연결되고 bB라는 정점과 Ba라는 정점이 연결될 것이다. 이 연결을 할 수 있게 만드는 정점의 최소수를 구하는 문제이기 때문에 최소 버텍스 커버 문제로 해결 가능한 것이다. 하지만 맨 처음 나오는 Aa라는 단어와 Ba라는 단어는 항상 선택이 강제 되어야하므로 해당 단어와 연결 된 간선들을 모두 제거해준 뒤 그.. 더보기
BOJ)9023 연습시즌 문제: icpc.me/9023 연습 일정에 맞춰서 경기장이나 호텔을 빌려야 할 때 두 팀이 지불해야하는 비용의 합의 최솟값을 구하는 문제이다. 다이나믹 프로그래밍을 이용하여 해결해줄 수 있는데 점화식을 세울 때 주의할 점은 두 팀 다 쉬는날이 없게해야한다. (무조건 손해) dp테이블을 dp[x][y][bx][by] (x번째 경기 y번째 경기를 진행해야되고 bx,by는 이전에 호텔에 묶었는지 여부 )로 세워준다음에 점화식을 세워주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include #include #include #include #define INF 1e9using nam.. 더보기

티스토리툴바