본문 바로가기

알고리즘 관련/BOJ

BOJ)11670 초등 수학 문제: icpc.me/11670n개의 줄에 순서 쌍 a,b가 주어진다. 각 a,b에 대하여 a+b또는a-b또는a*b 에 일치하는 수들이 중복 없이 n개 존재한다면 그 답을 출력하는 문제이다.이 문제는 잘 생각해보면 순서 쌍 a,b와 답이 될 수 있는 후보인 수들의 이분 그래프로 모델링 할 수 있다.따라서 답을 구하기 위하여 이분 매칭을 구해주어 최대 매칭이 n이 된다면 답을 역추적하여 구해주고, n이 안된다면 impossible을 출력하면 된다.12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970#include #includ.. 더보기
BOJ)3136 평면도 문제: icpc.me/3136좌표평면에 주어진 순서대로 그림을 그릴 때 평면도 상에서 존재하는 모든 방의 개수를 출력하는 문제이다.평면 그래프에서 V-E+F=2 라는 공식이 성립한다는 점을 이용하여 문제를 해결할 수 있다.(V:정점의 수, E:간선의 수,F:평면의 수)구해야 하는게 평면의 수 이므로 평면의 수는 F=2-V+E로 구할 수 있다. 하지만 좌표 평면 전체도 하나의 평면으로 세므로 답은 1-V+E가 된다.이제 V의 수와 E의 수를 구해야 하는데 이는 set을 이용하여 세주면 편리하게 계산할 수 있다.이 때 주의해야 할 점이 대각선으로 만나는 점을 처리해주기 위해 한 방향으로 나아갈 때 두번씩 나아가도록 점을 찍어주어야 한다. 자세한 것은 소스를 보며 이해하도록 하자.1234567891011121.. 더보기
BOJ)14195 DotB 문제: icpc.me/14195각 테스트 케이스마다 n과 c가 주어진다. 이후 n개의 시퀀스가 주어진다.이제 0번 인덱스부터 증가하는 순서로 보면서 시퀀스를 c만큼 감소시킬 것이다. 해당 원소가 0이하가 되면 시퀀스의 탐색 방향을 반대방향으로 바꾸고 해당 원소를 제거한다.이렇게 하였을 때, n+5번 탐색을 하였을 때 가장 마지막에 감소 된 원소의 번호를 출력하는 문제이다.n이 적은편이기 때문에 시뮬레이션을 돌려주면 된다.1234567891011121314151617181920212223242526272829303132333435363738394041424344#include #include #include using namespace std;int t, r, n, c;int func(vector vt, .. 더보기
BOJ)14748 Flow Graph Complexity 문제: icpc.me/14748 주어진 문자열로 만들 수 있는 그래프의 C값을 구하는 문제이다.C값은 EF+W*EB-V+2 로 구할 수 있다.즉 주어진 문자열을 잘 파싱하여서 EF, EB, V 세 값을 구해내면 되는 문제이다.하지만 문제에서 valid하지 않은 경우가 주어지는데 이는 일단 생각하지 말고 주어진 조건에 따라서 그래프를 그리게 된다면 EB가 생기는 경우는 무조건 L이 있는 경우이다 즉, EB의 수는 L이 등장하는 횟수이다.V가 생기는 경우는 S일 때는 하나가 생기며, L이나 B의 경우 하나가 더 생겨서 2개가 생긴다.즉 V의 수는 S+2*L+2*B 이다. 마지막으로 EF의 수는 각 정점은 마지막 정점을 제외하고 모두 아래로 하나씩 EF를 쏜다. (L에 의하여 생기는 정점은 간선을 받지 않지만.. 더보기
BOJ)5846 Tractor 문제: icpc.me/5846 n^2의 격자에서 한 점에서 4방향으로 일정 조건(둘의 차이가 k이하이면 이동 가능)을 만족하면 이동가능할 때임의의 한점을 잡아 반 이상의 격자를 순회할 수 있는 최소의 k를 찾는 문제이다. 최대중의 최소를 구하는 문제이므로 파라메트릭 서치를 생각해볼 수 있다.이 때 k를 mid값으로 정해놓은 뒤에 만족 여부를 확인하게 되는데만족여부는 dfs를 통하여 확인할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #include #include using namespace std;int n, a[555][555], b[555][555];int dx[] = .. 더보기
BOJ)5849 Cow Crossings 문제: icpc.me/5849N개의 2점이 주어진다.a[i]와 b[i]인데 이 문제는 각 (a[i],0)과 (b[i],1) 두 점을 잇는 N가지 직선들 중 다른 어떤 직선과도 겹치지 않는 직선의 수를 세는 문제이다.N^2으로 완전 탐색을 하는 방법으로는 해결이 불가능하니, 보통 이러한 류의 문제에서는 스위핑을 이용하게 되는데우선 a[i]를 기준으로 정렬을 해보자.그러고 a[i]가 증가하는 순서대로 보면 이러한 생각을 하게 될 수 있다.내가 이전에 본 직선들의 b[x]의 좌표 중에 나의 b[i]보다 하나라도 큰 수가 있다면 나는 이전에 업데이트 된 직선에 의해서 겹치는 직선이 된다는 걸 알 수 있다.이러한 원리로 우선 a[i]가 증가되는 순서로 안되는 직선들을 걸러준다.하지만 이렇게 처리하면 몇가지 직선이.. 더보기
BOJ)2023 신기한 소수 문제: icpc.me/2023 N자리의 신기한 소수를 모두 출력하는 문제이다. 문제를 잘 생각해보면 N자리의 신기한 소수는 결국 N-1자리의 신기한 소수로부터 파생된다는 걸 알 수 있다. 게다가 예제를 보면 그 수가 얼마 안되기 때문에 N-1자리의 신기한 소수들에서 파생되는 수들에 대해서만 sqrt(Number)시간에 소수여부 검사를 해주면 빠르게 구해줄 수 있다. 123456789101112131415161718192021222324252627282930#include #include #include using namespace std;vector v[10];bool isp(int x) { for (int i = 2; i 더보기
BOJ)13212 Random 문제: icpc.me/13212 1)주어지는 수의 1을 제외한 소인수가 모두 K보다 크면서 2)연속되는 같은 숫자가 4개 이상이 아닌지 확인하는 문제이다. 2)의 조건은 10으로 나눠주면서 연속되는 자리수의 개수를 세주면 되고 1)의 조건은 sqrt(maxNumber)보다 작은 모든 소수를 구해준 뒤 그 수들로 나눠지는 가장 작은 수가 K보다 큰지 여부를 확인해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include #include #include using namespace std;typedef long long ll;ll n, k, num;bool p[100010];vecto.. 더보기
BOJ)13213 Binary Roads 문제: icpc.me/13213 N개의 정점과 E개의 간선으로 이루어진 그래프에서 0번정점에서 N-1번 정점으로의 최단거리를 구하는 문제이다. 단, 조건이 하나있는데 엣지에 패리티가 붙어있어서 0이나 1중 하나의 속성을 지닌다. 이전에 0인 엣지를 통하여 왔다면 다음에는 1인 엣지만 밟을 수 있다. 이 문제를 해결하기 위하여 각 정점을 2차원으로 생각해주면 된다. 0인 엣지를 밟고 V번 정점인 경우와 1인 엣지를 밟고 V번 정점인 경우로 나눠서 생각해주면 다익스트라를 2번 실행하는 것으로 문제를 해결해 줄 수 있다. N제한이 크긴 하지만 시간이 3초이니 제한시간 내에는 넉넉히 들어올 수 있다. 12345678910111213141516171819202122232425262728293031323334353.. 더보기
BOJ)11442 홀수번째 피보나치 수의 합 문제: icpc.me/11442 N보다 작은 모든 홀수번째 피보나치 수의 합을 구하는 문제이다. N이 너무 크기 때문에 피보나치 수의 N번째 항은 행렬 곱셈의 분할 정복으로 log 시간에 구할 수 있지만 이방법으로 모든 피보나치수를 구하는건 너무 많은 시간이 걸린다. 하지만 수를 쭉 나열해보면 Rn이 n보다 작은 모든 홀수번째 피보나치 수의 합이라고 가정한다면 R(2n)=R(2n-1)=F(2n) 이라는 공식이 나온다. 따라서 이에 대한 답을 구해주면 된다. 123456789101112131415161718192021222324252627282930313233343536#include #include #include #include using namespace std;typedef long long ll;.. 더보기

티스토리툴바