본문 바로가기

알고리즘 관련

BOJ)12843 복수전공 문제: icpc.me/12843 n개의 강의가 주어질 때 서로 다른 학부의 강의면서 강의의 내용이 겹치는 강의는 두 강의중 하나만 수강할 때 최대로 수강할 강의 수를 구하는 문제이다. 내용이 겹치는 두 강의를 서로 연결해준다면 c학부와 s학부로 이루어진 이분 그래프가 나타나게 된다. 이때 이분 그래프에서 최대로 매칭되는 만큼 수업을 더 안들으면 되기 때문에 이분 매칭을 구해준 후 N에서 빼주면 답이 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include #include #include #include using namespace std;int n, m, x, y;char .. 더보기
BOJ)12841 정보대 등산 문제: icpc.me/12841 왼쪽 1번 지점에서 오른쪽 n번 지점까지 가는 최단 거리를 구하는데 이 때 횡단보도는 한번 밖에 못 건넌다는 전제가 있다. N개의 횡단보도를 건너는 케이스를 전부 확인을 해줘야 하는데 N이 10만이나 되기 때문에 모든 케이스를 직접 더해줄 경우 TLE를 받을 수 있다. 하지만 Partial sum을 이용한다면 왼쪽 오른쪽길의 횡단보도 기준으로 위 아래는 쉽게 구할 수 있다. 주의 할 점은 10만개의 횡단보도에 거리가 10만 까지 들어올 수 있으므로 long long을 사용해줘야 한다. 12345678910111213141516171819202122232425262728293031#include #include #define INF 999999999987654321using.. 더보기
BOJ)1865 웜홀 문제: icpc.me/1865 방향 그래프에서 시간이 거꾸로 간다는 개념이 나온다면 우선 벨만-포드를 생각해 볼 수 있다. 이때 주의 할 점은 도로는 방향이 없으므로 양 방향에 연결을 해줘야 한다. 문제에서 질문은 출발을 하였을 때 보다 시간이 되돌아 가 있는 경우가 있는지 확인하는 것인데 이것은 벨만-포드에서 음수 사이클 존재 여부를 확인하는 것과 동치다. 따라서 벨만-포드를 구현 한 뒤 음수 사이클 존재 여부에 따라 출력해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445#include #include #include #define INF 987654321using namespace std;in.. 더보기
BOJ)11999 Milk Pails 문제: icpc.me/11999 X,Y,M이 주어졌을 때 X와 Y를 이용하여 M을 넘치지 않도록 최대한 얼마나 채울 수 있는지 구하는 문제이다. X,Y,M이 전부 1000이하이기 때문에 이터레이터를 1000번씩 돌려주면 되는 쉬운 문제다.O(N^2) 1234567891011121314151617#include #include using namespace std;int x, y, m, r;int main() { freopen("input.txt", "r", stdin); scanf("%d%d%d", &x, &y, &m); for (int i = 0; i 더보기
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) { .. 더보기

티스토리툴바