본문 바로가기

2017/07

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 .. 더보기
제 3회 SCPC 본선진출 너무 행복하다 ㅎㅎㅎ 올해 ACM-ICPC에 같이 나갈 우리 팀원 모두 본선에 가게 되서 더욱 더 기쁘다 ㅎㅎ 이제 다시 달릴 명분이 생겨버림 ㅎㅎㅎ... 더보기
BOJ)10637 Minimum Spanning Tree 문제: icpc.me/10637 간선들의 셋이 주어진다. 출력해야하는 답은 각 간선마다 자신을 제외한 간선들로 만들 수 있는 MST의 가중치의 합을 출력하는 문제이다. 이건 MST에 포함 안되는 간선에 대한 답은 MST의 가중치가 되겠지만 아닌 경우가 문제가 된다. 그렇다면 아닌 경우에 대해 생각해보자. 만약에 MST에 포함되지 않는 간선이 u-v 를 연결한다고 생각해보자 그러면 우리는 mst에서 u v를 잇는 경로상의 어떤 간선을 지워도 이 간선을 통하여 MST를 유지 할 수 있다. 즉 이러한 사실을 이용하여 MST를 만들 때 사용되지 않은 간선들을 가중치 순서대로 정렬하여 오프라인으로 미리 mst상에 사용 된 간선들의 답을 정해주는 것이다. 여기서 매번 경로를 확인해준다면 당연히 TLE를 보게 될 것.. 더보기
트리에서 A와 B의 경로 사이에 C존재 여부 트리에서 임의의 노드 A,B가 있을 때 A와 B의 경로에 C가 존재하는지 여부는 어떻게 알 수 있을까? A와 B의 LCA를 LCA(A,B)라고 칭해보자. 만약 A와 B의 경로사이에 C가 존재한다면 C는 A와 LCA(A,B) 사이의 경로에 존재하거나 B와 LCA(A,B) 사이의 경로에 존재할 것이다. 일단 A와 LCA(A,B) 사이의 경로에 C가 존재한다고 가정해보자 그렇다면 LCA(A,C)==C && LCA(A,B)==LCA(C,B) 가 성립할 것 이다. 그러면 이번에는 B와 LCA(A,B)사이의 경로에 C가 존재한다고 가정해보자. 그렇다면 LCA(B,C)==C && LCA(A,B)==LCA(C,A) 가 성립할 것이다. 따라서 { LCA(A,C)==C && LCA(A,B)==LCA(C,B) }|| { L.. 더보기
다익스트라 알고리즘(Dijkstra's Algorithm) 다익스트라 알고리즘은 간선에 가중치가 있는 그래프에서 1:N 최단거리를 구하는 알고리즘 입니다. 여기서 말하는 1:N이란 한 정점 V를 기준으로 V와 같은 컴포넌트에 속해있는 모든 정점들과의 최단거리를 계산한다는 의미입니다. 보통 가중치가 없는 그래프에서의 1:N 최단거리는 BFS (O(V+E))를 통하여 계산해주고, 가중치가 있는 그래프에서의 N:N 최단거리는 플로이드 워셜(O(N^3))으로 계산해주는게 일반적입니다. 단 다익스트라를 포함한 위에서 제시한 알고리즘들은 가중치가 음수 일때는 사용하지 못합니다. 가중치가 음수일 경우 벨만포드 알고리즘(O(VE))이나 SPFA(O(VE))를 통하여 최단거리를 구해주어야 합니다. 그렇다면 다익스트라는 어떤 방식으로 1:N 최단거리를 구해낼까요? 일단 다익스트라.. 더보기
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.. 더보기

티스토리툴바