본문 바로가기

알고리즘 관련/BOJ

BOJ)10775 공항 문제: icpc.me/10775 비행기가 도착하는 순서대로 게이트에 도킹을 하는데 한 게이트에는 오직 한대의 비행기만 도킹이 가능하다 이때 각각의 비행기는 1~g번째 게이트중 하나에 도킹할 수 있다는 정보가 들어올 때 최대로 도킹할 수 있는 비행기의 수를 출력하면 된다. g번째 게이트부터 도킹을 하는게 이득인 것임은 자명하므로 disjoint-set을 이용하여 g게이트에 도킹이 될 경우 다시 g게이트를 확인 할 때 g-1게이트를 확인 하도록 parent를 설정해주면 된다. 만약 find 호출에서 0을 호출하게 된다면 1~g번째 게이트는 모두 사용중인것이니 더 이상 도킹이 불가능 하므로 현재까지 도킹 된 횟수를 출력해 주면 된다. 12345678910111213141516171819202122#includ.. 더보기
BOJ)12845 모두의 마블 문제: icpc.me/12845 인접한 두 카드를 합쳐서 하나로 만들어 점수를 얻는데 이때 카드의 레벨이 합쳐지는 두 카드 중 높은 카드에 의해서 결정이 될 때 획득 할 수 있는 최대 골드를 출력하는 문제이다. 문제를 읽고 파일 합치기나 행렬 곱셈 순서과 유사한 문제로 판단하여 두문제를 푸는데 사용했던 dp기법을 사용하였으나 TLE를 받게 되었다.... 123456789101112131415161718192021222324252627282930313233#include #include #include #define INF 987654321using namespace std;int n;int arr[1010];int dp[1010][1010];int ax[1010][1010];int func(int lo,.. 더보기
BOJ)12846 무서운 아르바이트 문제: icpc.me/12846 알바를 한 기간동안 임금이 가장 적은날을 기준으로 급여를 받을 때 최대 이익을 출력하는 문제이다. 유명한 문제인 히스토그램에서 가장 큰 직사각형과 같은 문제로 해석해도 된다. 세그먼트 트리를 이용하여 최솟값의 위치를 저장한 후 가장 작은 위치를 기준으로 왼쪽 오른쪽을 보며 답을 비교해 나간다. 히스토그램에서 가장 큰 직사각형 문제는 스택으로도 풀 수 있으니 이곳을 참고하도록 하자 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include #include typedef long long ll;using namespac.. 더보기
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.. 더보기

티스토리툴바