본문 바로가기

알고리즘 관련/BOJ

BOJ)11983 Radio Contact 문제: icpc.me/11983 파머존과 소가 움직이는 경로가 주어질 때 파머존만 움직이거나 소만 움직이거나 둘이 동시에 움직일수 있다. 이동 후 둘의 거리의 제곱에 비례하게 라디오의 에너지가 소모될 때 파머존과 소가 목적지에 도착했을 때 소모된 라디오 에너지의 최솟값을 출력하는 문제이다. 우리는 이 문제를 다이나믹 프로그래밍을 통하여 해결할 수 있다. dp[x][y]의 정의는 Farmer John이 X번 이동한 위치이고 소가 Y번 이동한 위치일 때까지 소모된 라디오 에너지의 최솟값이다. 점화식은 dp[x][y]=min(dp[x-1][y],dp[x][y-1],dp[x-1][y-1])+dist(FJx ,COWy)가 되겠다. 파머존과 소가 한번도 움직이지 않았을 때는 에너지 소모가 없다고 하니 기저는 dp[.. 더보기
BOJ)1766 문제집 문제: icpc.me/1766 문제집을 푸는 순서가 주어지는데 이때 가능하면 쉬운 문제부터 풀어야 할 경우 문제를 푸는 순서를 출력하는 문제이다. 우리는 문제집을 푸는 순서가 주어질 때 topological sort를 통하여 순서를 출력할 수 있다. 하지만 가능하면 쉬운 문제를 풀어야 하니 topology가 여러개일 경우 작은 순서를 먼저 출력해줘야 한다. 이는 min heap을 통하여 해결 가능하다. 123456789101112131415161718192021222324252627282930313233#include #include #include #include #define MAX_N 32000using namespace std;int n, m, a, b, in[MAX_N + 1];vector vt.. 더보기
BOJ)2623 음악프로그램 문제: icpc.me/2623 음악프로그램의 출연 순서의 리스트가 주어졌을 때 모든 리스트를 만족시키도록 출연 순서를 출력하는 문제이다. 만약 모든 리스트를 만족할 수 없는 경우 0을 출력하면 된다. 우리는 출연 순서가 A->B->C 라면 A->B / B->C의 방향으로 간선을 연결해 준 뒤 topology를 구해줌으로서 리스트를 구할 수 있다. 이때 모든 리스트를 만족할 수 없는 경우는 사이클이 생기는 경우로서 그래프의 사이클 여부를 체크해줌으로서 확인 가능하다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include #include #include #include #define MA.. 더보기
BOJ)11438 LCA 2 문제:icpc.me/11438 이 문제는 LCA (BOJ 11437) 의 풀이도 포함한다. 루트의 번호가 1번인 N개의 정점으로 이루어진 트리가 존재할 때 두 노드의 쌍 M이 주어질 때 두 노드의 LCA를 구하는 문제이다. 여기서 LCA(Lowest Common Ancestor)란 직역하면 최소 공통 조상(?) 이다. 즉 트리의 두 노드가 주어졌을 때 서로의 조상을 거슬러올라갔을 때 가장 먼저 만나는 정점이 LCA가 된다. LCA를 구하는 방법으로 두 노드의 높이(깊이)를 맞춘후에 한칸씩 올라가며 조상이 같아질 때까지 비교하는 방법이 있다. 하지만 이방법은 한번의 쿼리를 처리할 때 O(N)의 시간복잡도를 가지므로 LCA 2문제 같이 M과 N이 10만이면 O(N*M)으로 TLE를 피하기 힘들것이다. 그래서.. 더보기
BOJ)4386 Freckles 문제: icpc.me/4386 N개의 점들이 주어지고 각 점들사이의 가중치는 거리와 비례한다 할 때 MST를 구성하는 문제다. N이 100밖에 되지 않으니 N^2의 방법으로 간선들을 구해준 후 크루스칼을 돌려주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #include using namespace std;int n, par[101], it;double r;pair p[101];priority_queue pq;double calc(pair cx, pair cy) { return sqrt((cx.first - cy.first)*(cx.first - cy.first) + (cx.se.. 더보기
BOJ)4343 Arctic Network 문제: icpc.me/4343 P개의 전초기지가 있을 때 S개의 전초기지는 위성채널과 연결되어 있을 때 전초기지 전체가 위성채널과 연결되게 하는데 필요한 마지막 최소 연결비용을 출력하는것이다. 연결비용은 두 전초기지의 거리와 같다. 우리는 P-S개의 간선을 연결하는 MST를 구현하여 마지막으로 연결되는 간선의 가중치를 출력하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253#include #include #include using namespace std;int t, n, m, x, y, par[501], c;pair p[501];double r;double calc(pa.. 더보기
BOJ)13325 이진 트리 문제: icpc.me/13325 포화 이진트리의 높이 K가 주어 질 때 에지의 가중치를 증가시켜서 루트에서부터 리프까지의 거리를 모두 같게 만드는 문제이다. 아래에서 부터 부모가 같은 두노드의 엣지의 가중치 차이를 바텀업으로 중첩시켜서 증가시켜주면 된다. 12345678910111213141516171819#include #include using namespace std;int n, a[1 더보기
BOJ)11975 Build Gates 문제: icpc.me/11975 펜스를 동서남북으로 치려고 할 때 펜스로 인하여 닫힌 구간은 나가야 할 문이 필요하다고 할 때 문의 최소 개수를 출력하는 문제이다. 문제를 다시 해석하자면 그래프를 그린 뒤 완전히 닫혀있는 구간의 개수를 세는것이다. 즉 평면의 개수를 찾는 문제인데, 선을 그어서 생긴 그래프이므로 평면그래프가 되니 V-E+F=2라는 공식을 이용하여 F=2-V+E로 평면의 개수를 구할 수 있다. 이때 그래프 전체가 평면의 개수에 포함되기 때문에 F-1을 출력해주면 된다. Vertex와 Edge는 중복이 되면 안되므로 set을 통하여 관리해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839#include #i.. 더보기
BOJ)11974 Subsequences Summing to Sevens 문제: icpc.me/11974 N마리의 소가 각각의 고유 ID를 가지고 있을 때 연속된 소의 고유 ID의 합이 7의 배수인 구간의 길이를 출력하는 문제이다. 소를 입력 받은 후에 소의 partial sum을 저장한 뒤 partial sum을 7로 나눈 나머지를 저장한다면 해당 값이 같은 가장 긴 구간이 답이될 것이다. 123456789101112131415161718192021222324252627282930313233#include #include using namespace std;typedef long long ll;ll n, a[50000], p[50000], r;int main() { scanf("%lld", &n); for (int i = 0; i 더보기
BOJ)11973 Angry Cows 문제: icpc.me/11973 Angry Cow를 x위치에 던지면 [x-R,x+R]위치의 건초가 모두 파괴된다. N개의 건초더미의 위치가 주어질 때 K마리의 Angry Cow를 던져서 모든 건초를 파괴하려할 때 R의 최솟값을 출력하는 문제이다. 우리는 건초더미들의 위치를 구간으로 생각하여 한 Angry Cow가 구간 2*R을 파괴할 때 K마리의 Angry Cow가 전체 구간을 다 파괴할 수 있는지를 확인하여 R의 최솟값을 구해야한다. R의 최솟값은 이분탐색을 통하여 구할 수 있다. 123456789101112131415161718192021222324252627282930313233#include #include using namespace std;typedef long long ll;ll n, k, .. 더보기

티스토리툴바