본문 바로가기

분류 전체보기

BOJ)12844 XOR 문제: icpc.me/12844 특정 구간에 XOR을 하거나 구간을 XOR한 값을 출력하는 문제이다. N,M이 50만이므로 구간에 대한 쿼리를 빠르게 처리 하기 위해 세그먼트 트리를 사용해야 한다. 이때 한 지점에 대해서가 아닌 구간에 대한 업데이트가 이루어지므로 lazy propagation을 이용하여 최적화 시켜줄 필요가 있다. 주의해야 할 점은 항상 a가 b보다 작지는 않다는 것이다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263#include #include using namespace std;int n, m, a, b, c, d;in.. 더보기
BOJ)10815 숫자 카드 문제: icpc.me/10815 N개의 카드와 M개의 카드가 있을 때 M개의 카드 들이 각각 N개에 카드에 속해 있나 확인하는 문제이다.O(NM)의 방법으로 풀 경우 TL을 받으므로 binary_search를 이용하여 O(logNM)의 방법으로 해결하면 된다. 1234567891011121314151617181920212223#include #include #include using namespace std;int n, m, x;vector vt;int main() { scanf("%d", &n); for (int i = 0; i 더보기
BOJ)1733 등번호 문제: icpc.me/1733 참가자와 등번호들로 이루어진 이분 그래프를 이분매칭하는 문제이다. 이분 매칭의 역추적은 매칭을 시킬 때 배열등에 저장하여 쉽게 할 수 있다. 다만 N이 100만이므로 매칭때마다 memset을 사용할 경우 TL을 볼 수도 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #include #include #include using namespace std;vector vt;int check[1000100];int backmatch[1000100];int r[1000100];int n, x, y, s;bool dfs(int here) { .. 더보기
BOJ)14168 Cow Checklist 문제:icpc.me/14168 H의 순서와 G의 순서를 지키면서 순서대로 순회 할 때 소모되는 에너지의 최솟값을 구하는 문제이다. 이때 조건이 반드시 시작과 끝은 H의 처음과 끝이어야 한다는거다. H순서와 G순서를 각각 배열에 저장 한 뒤 다이나믹 프로그래밍을 통하여 문제를 해결하였다. dp[h][g][s]의 정의는 H순서를 h까지 G순서를 g까지 처리하고 s가 1이면 H의 h번째 점에 서 있을 경우 s가 0이면 G의 g번째 점에 서 있을 경우앞으로 순회하는데 소모되는 에너지의 최솟값이다. 123456789101112131415161718192021222324252627282930313233343536373839404142#include #include #include #define INF 9876543.. 더보기
BOJ)11895 속이기 문제: icpc.me/11895 XOR의 원리에 의해서 답이되는 X그룹과 Y그룹이 존재한다면 X그룹과 Y그룹을 각각 XOR한 결과는 같으므로 결국 모든 원소들을 XOR을 한 결과는 0이 되어야 한다. 따라서 전체를 XOR했을 때 0이 아닌 다른 수가 나온다면 X그룹과 Y그룹이 존재할 수 없으므로 0을 출력하면 되고 X그룹과 Y그룹이 존재하는 경우에는 전체를 XOR한 경우가 0이므로 A^0 = A에 의하여 그룹을 어떻게 나누더라도 XOR한 결과가 같을 것이다. 문제에서는 최댓값을 출력하라고 하였으므로 파셜섬 한 값에서 가장 작은 값을 빼준 값을 출력해주면 된다. 1234567891011121314151617181920#include #include using namespace std;int n, x, Ps.. 더보기
BOJ)2401 최대 문자열 붙여넣기 문제 : icpc.me/2401 긴 문자열에 여러개의 짧은 문자열을 붙일 때 얼마만큼 붙일 수 있는지 최대 길이를 출력하는 문제이다. KMP로 긴문자열에 대응하는 짧은 문자열들을 찾아주어 (a부터b까지 짧은 문자열이 같다면) a 점에서 붙일 수 있는 점들을 vt[a]에 b로 저장 해 준 후 다이나믹 프로그래밍을 이용하여 답을 구해준다 . dp테이블의 정의는 dp[x]는 x번째 문자열부터 시작하였을 때 붙일 수 있는 문자열의 최대 길이이다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273#include #inc.. 더보기
BOJ)13168 내일로 여행 문제: icpc.me/13168 최단 거리로 각각의 도시들을 순서대로 여행 다닐 때 내일로 티켓을 구매할지 안할지 결정해 주면 된다. 내일로 티켓을 구매 했을 경우와 구매하지 않았을 경우에 대하여 각각 그래프를 만들어 준 후 n이 100밖에 안되니 플로이드 워셜을 돌려주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778#include #include #include #include #include #include #define INF 987654321using namespace std.. 더보기
BOJ)13911 집 구하기 문제: icpc.me/13911 맥세권과 스세권을 만족하는 집 중 최단거리의 합이 최소인 집을 구하면 된다. 맥도날드로 부터 거리를 구하기 위한 다익스트라와 스타벅스로 부터 거리를 구하기 위한 다익스트라를 두번 돌려 준 후 mdp[x]와 sdp[x]가 정해진 거리를 만족하면서(맥세권,스세권이면서) mdp[x]+sdp[x]가 최소인 거리를 출력해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576#include #include #include #include #include #define IN.. 더보기
BOJ 5719) 거의 최단 경로 문제: icpc.me/5719 BOJ 5719 다익스트라로 최단경로를 구현하고 최단경로에 포함되는 모든 간선들을 지워준 뒤 다시 다익스트라를 실행하면 된다. 최단경로에 속하는지 여부는 BFS처럼 처음에 queue에 도착지점을 넣어준 뒤 하나씩 빼면서 for(i 0~n-1) dp[here]= dp[i]+dist[i][here]를 만족하는 경우에 dist[i][here]를 지워주고 i를 큐에 삽입하면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include #include #include #include using namespace std;int n, m, x.. 더보기
BOJ 7894) 큰 숫자 문제: icpc.me/7894 BOJ 7894 임의의 숫자 n의 자리수는 ceil(log10(n))으로 결정된다 n!의 자리수는 ceil(log10(n)+log10(n-1)+...+log10(1)) 으로 결정된다. 12345678910111213141516171819202122#include #include #include using namespace std;int t, m;int main() { scanf("%d", &t); while (t--) { scanf("%d", &m); double r = 0.0; for (double i = (double)m; i > 0; i--) { r += log10(i); } if (m == 1) printf("1\n"); else printf("%lld\n", (in.. 더보기