본문 바로가기

알고리즘 관련/BOJ

BOJ)13309 트리 문제:icpc.me/13309 트리에서 두 가지 쿼리를 처리하는 문제이다. 첫번 째 쿼리는 두 정점이 같은 컴포넌트에 존재하는지 여부이고 두번 째 쿼리는 두 정점이 같은 컴포넌트에 존재하는지 여부를 물음과 동시에 존재할 경우 두 정점 x,y 중 x와 x의 부모의 간선을 단절 존재하지 않을 경우 y와 y의 부모의 간선을 단절 시키는 쿼리이다. 오래 생각하다가 못 풀겠어서 풀이를 봤는데 재밌는 문제였다. 우선 루트에서 DFS를 돌면서 정점들의 번호를 방문하는 순서대로 새롭게 매겨준다. 이렇게 하면 어떤 정점 A의 자식들은 모두 A보다 큰 번호를 연속적으로 가지게 된다. 이걸 이용하여 정점 A부터 A의 자식들까지 범위를 저장해놓고 있을 수 있다. 그렇다면 두 정점이 같은 컴포넌트인지 확인하는 경우를 올라갈 수.. 더보기
BOJ)2507 공주 구하기 문제: icpc.me/2507 0에서 n-1을 갔다가 0으로 다시 돌아와야하는 bitonic tour의 변형문제이다. 바이토닉 투어는 다이나믹 프로그래밍으로 해결해줄 수 있다. dp[x][y] = 올 때 x번 정점을 밟고 갈 때 y번 정점을 밟을 때의 경로의 개수 점화식은 중복을 제거해주기 위해 max(x,y)보다 큰 섬으로만 보낼 수 있어야 한다. 12345678910111213141516171819202122232425262728293031323334353637#include #include #include using namespace std;int n, w[505], g[505], b[505], a[505][505], dp[505][505];const int MOD = 1000;int func(in.. 더보기
BOJ)12869 뮤탈리스크 문제:icpc.me/12869 3개의 SCV의 체력이 주어질 때 뮤탈리스크가 각 SCV를 서로 다른 공격으로 공격할 때 공격횟수의 최솟값을 출력하는 문제이다. 이 문제는 그리디하게 힘들다고 생각한 순간 동적 계획법을 떠올릴 수 있다. 하지만 공격횟수로 테이블을 잡기 애매하기 때문에 각 SCV의 체력에 포커스를 맞춘다면 dp[x][y][z] = 체력이 x , y ,z 인 SCV를 파괴하는데 필요한 최소 공격 횟수로 테이블을 세울 수 있고 점화식은 공격가능한 6가지 방법 중에 최솟값을 호출하면 된다. 123456789101112131415161718192021222324252627#include #include #include #define INF 987654321using namespace std;int .. 더보기
BOJ)12922 블럭 퍼즐 문제: icpc.me/12922 1x1x2 블럭이 정사각형 그리드에서 이동할 때 게임승리를 불가능하게 뚫어야하는 구멍의 수를 출력하는 문제이다. 문제에서 블럭의 이동경로를 살펴보면 시작점에서 부터 4방향으로 3칸 떨어진 지점에만 서있을 수 있다. 이를 이용하여 모든 정점에서 3칸 떨어진 지점으로 그래프를 구성해주는데 이 때 간선의 capacity는 지나가는 경로에 뚫어야하는 구멍 수가 되야되고 해당 정점에 구멍을 뚫는 경우는 정점을 분할하여 사이에 capacity를 1로 주는걸로 그래프를 모델링 해주면 src에서 sink로의 mincut을 구해주면 답을 구해낼 수 있다. 123456789101112131415161718192021222324252627282930313233343536373839404142.. 더보기
BOJ)12963 달리기 문제: icpc.me/12963 N개의 정점과 M개의 간선으로 이루어진 그래프에서 0번정점에서 N-1번 정점으로 이동 가능한 사람의 최대 수를 구하는 문제이다. 얼핏보면 그냥 0번 정점에서 N-1번 정점으로의 maximum flow를 구하는 문제로 볼 수 있겠지만 한가지 문제가 있다. 간선의 capacity가 너무 커지기 때문에 modulo작업이 필수가 되는데 이와 같은 환경에서 maximum flow를 잘 처리해줄 수가 없기 때문이다. 따라서 우리는 조금 그리디하게 접근을 해야한다. 그래프에서 가장 큰 간선의 가중치는 나머지 모든 간선의 가중치의 합보다 크기 때문에 그 간선으로 이동가능한 경우가 그리디하게 최대가 된다. 그렇기 때문에 그 간선을 연결해보고 0에서 N-1 정점으로 이동가능하면 그 가중치만.. 더보기
BOJ)8217 유성 문제: icpc.me/8217 회원국이 커버하고있는 행성구역이 주어지고 날짜에 따른 유성 예보수가 주어질 때 각 회원국이 목표치로 정한 운석 샘플을 구하는데 걸리는 최소 날짜를 출력하는 문제이다. 각 날짜에 대해 나이브하게 계산을 해준다면 모든 날에 대해 단순히 K일을 커버하는 작업만 O(N*K)가 걸리게 된다. 이런 방법으로는 도저히 시간안에 문제를 해결할 수 없다. 따라서 새로운 방법이 필요한데 답으로 출력해야되는 모든 행성구역의 답의 범위를 lo~hi로 전부 잡아놓은 뒤 전체에 대하여 binary search를 돌리는 parallel binary search를 이용하자. 우선 답이 정해야하는 모든 구간에 대해 lo와 hi를 잡아준 뒤 모든 구간에 대한 답이 결정될 때 까지 while문으로 반복한다... 더보기
BOJ)14434 놀이기구1 문제: icpc.me/14434 놀이기구를 타는 키 제한이 존재하고 각 날마다 키가 자라는 아이와 어떤 놀이기구를 타는지 물어보는 질의들이 주어질 때 각 날마다 아이들이 타는 놀이기구의 수를 출력하는 문제이다. 이 문제는 각 질의에 대하여 해당 놀이기구를 탈 수 있는 첫번 째 날을 구해주면 그 날 이후는 해당 놀이기구를 항상 탈 수 있으니 psum으로 해결 가능하다. 문제는 질의마다 첫번 째 놀이기구의 탑승 가능일을 구해주는 일이다. 우선 질의에 대해 첫번 째 놀이기구의 탑승 가능일을 탐색해야하므로 mid값을 날짜로 생각을 하자. 그럼 mid일에 놀이기구를 타야하는 두 아이의 키를 가져와야 하는데 이는 2차원 벡터로 각 아이에 대해 키가 크는 날짜를 벡터에 삽입해준다면 upper_bound로 계산해줄 수.. 더보기
BOJ)1396 크루스칼의 공 문제: icpc.me/1396 lca를 이용하는 난이도 있는 문제다. 풀이 방법이 재밌다. x정점에서 y정점으로 이동할 때의 최소온도는 도로네트워크 등의 문제에서 했듯이 두 정점 사이의 lca를 구해나가면서 해당 간선의 가중치의 최댓값도 parent 배열과 같이 저장하는 방법으로 구해낼 수 있으나 공이 움직일 수 있는 범위를 출력하는게 문제가 되었다. 오래 생각해도 모르겠어서 찾아보니까 재밌는 방법으로 이걸 해결할 수 있었다. MST를 구성하는 과정에서 두 정점을 연결하는 대신 새로운 정점을 생성하는 방법이다. 즉 기존의 정점들은 새로운 그래프에서의 leaf가 되며 n-1개의 정점을 새로 구축하는 방법이다. 예제의 그래프를 새로 구축하면 이런 모양이 될 것이다. (기존의 정점(1~5)) 여기서 새로 생기.. 더보기
BOJ)10319 좀비 아포칼립스 문제: icpc.me/10319 감염이 되기전에 병원으로 이동가능한 최대한의 사람을 구하는 문제이다. 문제에서 요구하는 조건이 곧 시작지점부터 병원까지의 최대유량을 구하는 문제인데 문제는 간선에 capacity말고도 단위시간이라는 제약 조건이 붙는다. 이걸 해결해주기 위해 단위시간만큼 정점을 분할 시켜주어 각 시간별로 주어진 정점들로 이루어진 그래프로 새로 재구성 시켜준 뒤 maximum flow를 구해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868.. 더보기
BOJ)5651 완전 중요한 간선 문제: icpc.me/5651 어떤 그래프에서 플로우를 흘렸을 때 어떤 간선의 용량이 1 줄어들면 최대유량도 1 줄어들게 되는 간선을 완전 중요한 간선이라 할 때 그러한 간선의 수를 구하는 문제이다. 유량을 최대로 흘렸을 때 해당 간선에 용량을 줄였을 때 maximum flow에 직접적인 타격을 주려면 해당 유량이 해당 간선으로 밖에 통하지 못하여야 한다. 즉 유량 그래프에서 u->v로의 경로가 유일해야 한다. 답을 구하기 위해 유량을 흘려준 뒤 플로이드 워셜을 이용해 transitive closure를 구해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565.. 더보기

티스토리툴바