본문 바로가기

알고리즘 관련

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, .. 더보기
BOJ)10216 Count Circle Groups 문제: icpc.me/10216 N개의 진영이 주어 질 때 각 진영이 통신영역이 닿거나 겹치는 부분이 있으면 서로 통신이 가능하다. 그리고 직접적으로 통신이 불가능 하더라도 중간에 몇개의 통신을 거쳐서 통신이 가능하다면 i와 j는 통신이 가능하다고 본다. 통신이 서로 가능한 진영들을 그룹으로 묶을 때 그룹의 수를 출력하는 문제이다. 우리는 a와b가 통신이 가능하고 b와c가 통신이 가능하면 a와c가 통신이 가능한 그룹이 된다는 사실을 가지고 disjoint set을 통하여 문제를 해결할 수 있다. N이 3000밖에 되지 않으므로 N^2의 방법으로 각 진영들을 비교하여 같은 그룹이 아닌 그룹들중에서 통신영역이 겹치는 두 그룹을 union 시켜주면서 시켜줄때마다 그룹의 수를 하나씩 차감시키는 방법으로 답을 구.. 더보기
BOJ)13913 숨바꼭질4 문제:icpc.me/13913 X의 위치에서 1초후에 X+1,X-1,2*X의 위치로 이동가능할 때 K로 가는데 걸리는 가장 빠른시간과 경로를 출력하는 문제이다. 우리는 각 좌표를 정점으로 생각하여 다익스트라를 돌린다면 가장 빠른시간을 구할 수 있다. 경로를 출력하는것은 백트래킹을 해야하는데 좌표N에 대한 최단경로가 갱신되는 순간에 N을 부른 위치를 기록해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #include #include #include using namespace std;int dp[250000], n, k, back[250000];stack st;int main().. 더보기
BOJ)13549 숨바꼭질3 문제:icpc.me/13549 X의 위치에서 1초후에 X+1혹은 X-1로 이동가능하고 순간이동을 할경우 0초후에 2*X위치로 이동가능할 때 K까지 가는 가장 빠른 시간을 출력하는 문제이다. 각 좌표를 정점으로 생각하여 다익스트라를 돌리면 된다. 12345678910111213141516171819202122232425262728#include #include #include #include using namespace std;int dp[250000], n, k;int main() { scanf("%d%d", &n, &k); memset(dp, -1, sizeof(dp)); priority_queue pq; pq.push({ 0, n }); while (pq.size()) { int here = pq.t.. 더보기
BOJ)2910 빈도 정렬 문제: icpc.me/2910 수열이 존재할 때 수열에서 가장 많이 등장하는 빈도로 정렬을 하는 문제이다. 이 때 빈도가 같은 수는 먼저 등장한 순서대로 정렬을 해야한다. 우리는 수가 최대 10억까지 들어올 수 있으므로 빈도를 저장하기 위해 키값에 따른 값을 저장할 수 있는 map 자료 구조를 사용할 수 있다. 두개의 맵을 선언하여 하나는 빈도수를 하나는 들어온 순서를 저장한 뒤 벡터에 빈도수와 키값을 삽입 시켜준 뒤 조건에 맞게 정렬을 해준 뒤 출력해주면 된다. 1234567891011121314151617181920212223242526272829303132#include #include #include #include using namespace std;int n, c, x;map mp;map m;.. 더보기
BOJ)7795 먹을 것인가 먹힐 것인가 문제: icpc.me/7795 A집합과 B집합이 주어졌을 때 A집합의 어떤 수 X가 B집합의 어떤 수 Y보다 큰 경우의 수의 합을 출력하는 문제이다. A집합과 B집합의 크기 N M은 20000까지 들어올 수 있으니 O(N*M)의 방법으로 완전탐색한다면 한번의 테스트 케이스에서도 간당간당한데 여러번의 테스트 케이스를 거친다면 TLE를 보게 될 것이다. 우리는 B집합을 정렬한 후 lower_bound를 이용하여 N개의 쿼리에서 각각 X보다 작은 수 Y의 개수를 구할 수 있다. 시간 복잡도는 O((N+M)logM)이 될 것이다. 12345678910111213141516171819202122232425262728#include #include #include using namespace std;int t, n.. 더보기
BOJ)3758 KCPC 문제: icpc.me/3758 KCPC대회에서 각팀의 스코어가 주어졌을 때 정해진 기준에 따라 순위를 출력하는 문제이다. 제출 횟수나 최종 제출 시간은 쿼리를 받으면서 업데이트 시켜주면 되지만 최종 점수 같은 경우는 제출한 모든 기록중 문제당 최댓값이 업데이트 되므로 배열을 만들어 따로 저장해준 후에 업데이트 시켜준 뒤 조건에 맞게 정렬해주면 쉽게 구할 수 있는 문제이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include #include #include using namespace std;int t, n, k, id, m, a, b, c;int g[101][101];struct student{ .. 더보기

티스토리툴바