본문 바로가기

알고리즘 관련/BOJ

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{ .. 더보기
BOJ)8983 사냥꾼 문제: icpc.me/8983 KOI 2013 중,고등부 문제이다. N마리의 동물들의 위치가 좌표로 주어지고 x축위에 M개의 사대가 존재하는데 이때 모든 사대의 사정거리는 공통적으로 L이다. 각 사대에서 동물들과의 거리는 [abs(x(동물)-x(사로))+y(동물)] 로 계산될 때 사냥 가능한 동물의 수를 출력하는 문제이다. N과 M이 최대 10만까지 그리고 사정거리와 좌표는 1~ 1억까지 들어온다. 우리는 모든 사대와 각 동물들을 비교할 경우 O(N*M)의 시간 복잡도로 TLE를 보게 된다는 걸 알고 있다. 따라서 최대 NlogN의 알고리즘이 필요하다. 우리는 우선 동물들을 x좌표 기준으로 정렬 ,그리고 사대도 x좌표 기준으로 정렬을 할 것이다. 그 다음 동물들을 볼건데 어떤 동물 A를 사냥 가능한 사대.. 더보기
BOJ)10277 JuQueen 문제: icpc.me/10277 C개의 코어가 있을 때 쿼리를 받아 3종류의 연산을 처리해주면 되는 문제이다. 단 코어의 하한선은 0이고 상한선은 N으로 입력으로 주어진다. 쿼리는 다음과 같다 change X S 코어X를 S만큼 증가시켜라groupchange A B S 코어 A부터 코어B까지 전부 S만큼 증가시켜라state X 코어X의 값을 출력하라 단, 코어를 증가시키다가 상한이나 하한에 다다를시 증가를 멈춘다. change나 groupchange 같은 경우 증가혹은 감소시킨 계수를 출력해야 하는데 우리는 코어를 증가시키다 상한이나 하한에 도달하는 경우를 판단해야한다. 따라서 우리는 구간에 대한 최댓값 최솟값을 세그먼트 트리로 관리하여 구간을 증가 시킬 시 상한혹은 하한에 도달하는지 여부를 판단하여 상.. 더보기
BOJ)2877 4와 7 문제:icpc.me/2877 4와 7로만 이루어진 수 중에서 K번째로 작은 수를 출력하는 문제이다. 각 숫자가 4와 7로만 이루어졌기 때문에 우리는 N의 자리 수는 2^N개 밖에 존재하지 않는다는걸 알 수 있다. 이를 이용하여 K번째로 작은 수가 L자리수라는 걸 알 수 있다. 이후 L자리에서 V번째로 작은 수는 결국 이진수로 생각하면 비트가 1인 수는 '7' 비트가 0인 수는 '4'가 된다. 따라서 V의 각 비트를 조사하여 답을 출력해주면 된다. 12345678910111213141516171819202122232425#include #include using namespace std;int k, a[31], l;int main() { for (int i = 0; i 더보기
BOJ)2775 부녀회장이 될테야 문제: icpc.me/2775 a층 b호에 사는 주민은 a-1층의 1~b호까지의 주민의 합일때 k층n호에 사는 주민의 수를 출력하는 문제이다. 사실 k와 n의 범위가 매우 작기 때문에 그때 그때 구해줘도 TLE를 받을일은 없을것 같지만 우리는 배운 사람들이니까 다이나믹 프로그래밍을 통하여 쉽게 답을 구 할수 있다. 점화식은 dp[i][j]=dp[i-1][j]+dp[i][j-1] 이다. 12345678910111213141516171819#include #include using namespace std;int dp[15][15], t, k, n;int main() { for (int i = 1; i 더보기

티스토리툴바