본문 바로가기

알고리즘 관련

UVaOJ)12878 Flowery Trails 문제:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4743 그래프에서 0번 정점에서 n-1번 정점으로의 여러경로의 최단거리에 속한 간선들의 가중치의 합을 구하는 문제이다. 한 정점에서 한 정점으로의 최단거리가 유일하다면 경로의 가중치의 합을 구하는건 그렇게 어렵지 않게 풀 수 있다. 하지만 최단거리가 여러가지 경로가 있다면 다익스트라를 이용할 시 그걸 구하는 시간만해도 꽤 오랜 시간이 걸릴 수 있다. 처음 문제를 접근할 때 다익스트라를 돌리며 일일이 경로를 다 저장하여 역추적을 하여 tle를 받게되었다. 하지만 잘 생각해본다면 다익스트라(혹은 spfa) 두번의 전처리로 문제를 해.. 더보기
BOJ)9023 연습시즌 문제: icpc.me/9023 연습 일정에 맞춰서 경기장이나 호텔을 빌려야 할 때 두 팀이 지불해야하는 비용의 합의 최솟값을 구하는 문제이다. 다이나믹 프로그래밍을 이용하여 해결해줄 수 있는데 점화식을 세울 때 주의할 점은 두 팀 다 쉬는날이 없게해야한다. (무조건 손해) dp테이블을 dp[x][y][bx][by] (x번째 경기 y번째 경기를 진행해야되고 bx,by는 이전에 호텔에 묶었는지 여부 )로 세워준다음에 점화식을 세워주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950#include #include #include #include #define INF 1e9using nam.. 더보기
BOJ)13309 트리 문제:icpc.me/13309 트리에서 두 가지 쿼리를 처리하는 문제이다. 첫번 째 쿼리는 두 정점이 같은 컴포넌트에 존재하는지 여부이고 두번 째 쿼리는 두 정점이 같은 컴포넌트에 존재하는지 여부를 물음과 동시에 존재할 경우 두 정점 x,y 중 x와 x의 부모의 간선을 단절 존재하지 않을 경우 y와 y의 부모의 간선을 단절 시키는 쿼리이다. 오래 생각하다가 못 풀겠어서 풀이를 봤는데 재밌는 문제였다. 우선 루트에서 DFS를 돌면서 정점들의 번호를 방문하는 순서대로 새롭게 매겨준다. 이렇게 하면 어떤 정점 A의 자식들은 모두 A보다 큰 번호를 연속적으로 가지게 된다. 이걸 이용하여 정점 A부터 A의 자식들까지 범위를 저장해놓고 있을 수 있다. 그렇다면 두 정점이 같은 컴포넌트인지 확인하는 경우를 올라갈 수.. 더보기
UVaOJ)10968 KuPellaKeS 문제: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1909 도시가 주어질 때 연결 된 도시의 개수가 홀수개인 도시들을 몇개의 다리를 파괴하여 전부 2이상의 짝수개의 정점만 연결되게 만들어주려고 할 때 제거해야하는 최소 간선의 개수를 출력하는 문제이다. 연결 된 도시의 간선이 홀수인 정점이 2개 이하라는 조건도 있다. 우선 연결 된 도시의 간선이 홀수개인 정점이 두개가 있다고 생각해보자. 그렇다면 우리는 두 도시에 연결 된 간선을 하나씩 지워줘야 한다. 이 때 하나씩 지우면 반대쪽 정점들의 간선의 개수가 홀수가 되기 때문에 또 지워줘야한다. 이렇게 서로 지우다가 한 간선에서 만나.. 더보기
UVaOJ)12645 Water Supply 문제: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4393 오염된 물을 정화하기 위해서 단방향 그래프에서 0번 정점에서 나오는 정화제를 x개의 간선을 추가하여 모든 정점에 뿌려야할 때 연결해야하는 간선 x개의 최솟값을 구하는 문제이다. 이 문제는 정점들을 scc로 묶어준다음 위상정렬을 통하여 해결가능하다. 즉 0번 정점을 포함한 scc를 제외한 indegree가 0인 scc의 개수를 출력해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545.. 더보기
UVaOJ)11751 Installing Diagnostic Software 문제: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2851 확실한 번역은 모르겠지만 대략적인 설명은 간선이 주어질 때 해당 간선에 연결 된 두정점중 하나는 반드시 소프트웨어가 설치되어야 할 때 최소비용으로 소프트웨어를 설치하는 방법을 출력하는 문제이다. 소프트웨어 설치비용은 i번 정점의 경우 2^i의 비용이 소모된다. 즉 i번 정점에 소프트웨어를 설치하는건 0~i-1번 정점 모두에 소프트웨어를 설치하는것보다 비싸다 그렇기 때문에 최대한 작은 정점에 소프트웨어를 설치해야한다. 이를 위하여 간선에 연결 된 두 정점 중 작은 정점에 설치를 해야함은 자명하다. 그렇다면 이제 문제는 간.. 더보기
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 .. 더보기
(pow(A,B))mod C 를 logB 시간안에 구하는 함수 http://jason9319.tistory.com/169 예전에 이항 계수를 구할 때 설명한 적이 있지만 빈번하게 사용되는 유용한 테크닉이라 생각되어 다시 설명드립니다. 우선 소스코드를 먼저 보시죠 12345678910111213141516#include #include using namespace std;typedef long long ll;ll a, b, c;ll mypow(ll x, ll y) { if (!y)return 1; if (y % 2) return (x*mypow(x, y - 1)) % c; return mypow((x * x) % c, y / 2) % c;}int main() { scanf("%lld%lld%lld", &a, &b, &c); printf("%lld", mypow(a, .. 더보기
SPOJ)BATMAN2 문제:http://www.spoj.com/problems/BAT2/ 각 방의 가중치가 주어지고 두명의 사람이 이동을 한다. 한 사람은 1에서 부터 다른 한사람은 N에서 부터 이동할 때 겹치지 않는 경로로 가중치가 증가하는 순서대로 이동할 때 밟을 수 있는 방의 수의 최댓값을 출력하는 문제이다. 다이나믹 프로그래밍을 이용하여 dp[pos][x][y]의 정의를 1번부터 pos번 정점까지 확인 했을 때 한 사람은 x번 정점을 마지막으로 한사람은 y번 정점을 마지막으로 밟았다고 생각하면 점화식을 세울 수 있다. dp[pos][x][y]= max(dp[pos][a[pos]][y]+1, dp[pos][x][a[pos]]+1 , dp[pos][x][y]) 1234567891011121314151617181920212.. 더보기

티스토리툴바