본문 바로가기

알고리즘 관련/BOJ

BOJ)10265 MT 문제: icpc.me/10265 K이하의 사람이 버스에 탈 수 있을 때 버스에 탈 수 있는 최대 인원을 출력하는 문제이다. 문제에는 조건이 있는데 A라는 사람은 B라는 사람이 버스에 안타면 A도 반드시 안타는 정보 N개가 주어진다. 우리는 이러한 조건을 B->A라는 방향 그래프로 만들어 준 SCC끼리 분류를 한다음 다음 위상 정렬을 이용하여 X라는 정점이 방문 가능한 모든점 Y는 반드시 X의 인원을 포함한다고 정의 가능하다. 이 때 X의 인원은 SCC의 그룹 크기와 동치가 된다. 따라서 연결 그래프마다 최소 인원~최대 인원 셋을 저장한 뒤 Knapsack문제를 해결하듯이 다이나믹 프로그래밍을 이용해주어 답을 계산해주면 된다. 이때 연결 그래프의 수는 SCC 그래프의 indegree가 0인 SCC의 개수이.. 더보기
BOJ)3977 축구 전술 문제: icpc.me/3977 A->B로 이동해야하는 전술들이 주어질 때 시작 지점이 될 수 있는 위치를 찾는 문제이다. 이 때 적절한 시작지점이 없으면 Confused를 출력하면 된다. 여기서 SCC를 이루는 그룹이면 어떤 곳에서 시작하던 topology에 의해 나머지 지점들을 전부 탐색 가능하니 정점들을 SCC로 묶은 뒤 indegree가 0인 지점이 하나일 때는 해당 SCC에 속하는 모든 점들이 시작지점이 될 수 있고, 만약 indegree가 0인 지점이 여러곳일 경우에는 어떤 지점에서 시작해도 모든 점을 방문 불가능하기 때문에 Confused를 출력해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041424.. 더보기
BOJ)4196 도미노 문제:icpc.me/4196 X번 블록이 넘어지면 Y번 블록이 넘어지는 정보가 여러개 주어질 때 도미노를 직접 넘어뜨려야하는 최소 블록 개수를 출력하는 문제이다. 도미노를 직접 넘어뜨려야 한다는 건 결국 다른 도미노에 의해서 넘어지지 않는다는걸 의미하는데 이는 곧 indegree가 0인 정점의 개수다. 또 하나 고려해줘야 하는 경우가 있는데 cycle을 이룰 경우 indegree가 0이지 않지만 누가 먼저 넘어지지 않는 이상 영원히 넘어지지 않는다. 따라서 우리는 방향 그래프에서 SCC를 구해준 후 SCC로 이루어진 그래프에서 indegree가 0인 SCC의 개수를 세어주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839.. 더보기
BOJ)3665 최종 순위 문제:icpc.me/3665 작년의 등수가 주어지고 올해 등수가 역전 된 두 팀의 목록이 주어질 때 올해 순위를 발표하는 문제이다. 우선 작년의 등수를 기반으로 n^2의 방법으로 간선을 연결해주고 올해에 뒤 바뀐 순위를 기반으로 간선의 방향을 바꿔준다. 이후 위상정렬을 해주면 되는데 이 때 큐에 동시에 2개가 들어간다면 ?를 출력하고 n번을 돌리기전에 큐가 비어버린다면 사이클이 생긴것이므로 IMPOSSIBLE을 출력 해 주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172#include #include #.. 더보기
BOJ)2637 장난감조립 문제:icpc.me/2637 장난감 완제품 N을 만드는데 필요한 기본 부품의 종류와 수를 출력하는 문제이다. 여기 기본 부품은 indegree의 수가 0인 정점들이 되고 위상정렬 순서대로 부품의 개수를 중첩 시켜 나가면 답을 구할 수 있다. a[x][y]가 의미하는건 x번 부품(제품)을 만드는데 필요한 기본 부품 y의 개수이다. 123456789101112131415161718192021222324252627282930313233343536373839#include #include #include #include using namespace std;int n, m, a[101][101], in[101], x, y, z;vector vt;int main() { scanf("%d%d", &n, &m); vt.. 더보기
BOJ)9470 Strahler 순서 문제: icpc.me/9470 indegree가 0인 노드들의 순서가 1인데 어떤 노드의 indegree와 연결된 노드 중 순서가 가장 큰 값을 i라고할 때 i가 1개 들어오면 해당 노드의 순서는 i 2개 이상 들어온다면 해당 노드의 순서는 i+1이 된다. 우리는 indegree의 정보를 이용하여 위상정렬을 실행하는데 이때 들어오는 indegree의 최댓값과 개수만 count해주어 값을 갱신해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051#include #include #include #include #include using namespace std;int k, m, p,.. 더보기
BOJ)13711 LCS4 문제: icpc.me/13711 LCS의 크기를 구하는 문제이다. 우리는 다이나믹 프로그래밍을 이용하여 LCS를 구할 수 있다. 하지만 LCS4 문제는 N이 10만이기 때문에 다른 방법을 생각해보아야 한다. 단순히 N이 10만에서 최장 공통 부분 수열을 구하라고 한다면 무척 어려운 문제가 되겠지만 다행히 조건이 더 주어진다. 1~N까지 정수는 두 수열 A,B에서 전부 한번 씩 주어진다는 것이다. 우리는 수열 A에서 입력을 받은 후 입력 받은 수의 인덱스로 A[x]의 들어온 순서를 삽입하는 방식으로 A수열을 정의 해준 뒤 A[B[i]]의 LIS를 구함으로서 최장 공통 부분 수열의 길이를 구할 수 있다. 이때 N이 10만이기 때문에 N^2 DP로 LIS를 구하는 방법은 안되고 NlogN 이분 탐색의 방법으로.. 더보기
BOJ)1183 약속 문제: icpc.me/1183 도착하는 시간 A 배열과 기다리는 시간 S배열이 주어질 때 SUM[ abs(S[i]-A[i]+T) ] 을 최소로 만드는 T의 개수를 세는 것이다. 어짜피 s배열과 a배열 둘다 입력으로 주어지는 수니 수식의 간편화를 위하여 X로 표시할 수 있다 결국 우리는 SUM[ abs(X[i]+T) ]를 구하면 되는 것이다. X[i]들을 전부 정렬한 후 어떤 수 T를 어떤 수 -X[i]로 잡고 값을 정할 때 T를 -X[i]에서 증가 시킬 경우 (X[i]보다 큰수들-X[i]보다 작은수들)만큼 증가하며 -X[I]에서 감소 시킬 경우 (X[i]보다 작은수들-X[i]보다 큰수들)만큼 증가하게 된다. 결국 이를 이용하여 생각하면 정렬을 했을 때 중앙값의 음수부호를 취해준 -X[i]가 합을 최소로 .. 더보기
BOJ)2150 Strongly Connected Component 문제: icpc.me/2150 SCC를 구하는 기본 문제이다. 출력을 SCC가 속한 가장 작은 정점의 정점 번호 순으로 출력해야 하므로 정렬이 필요하다. 코사라주 알고리즘을 통하여 구현하였다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include #include #include #include #include #define MAX_V 10000using namespace std;int v, e, visited[MAX_V + 1], x, y, r;vector scc;vector vt;vector rvt;stack st;bo.. 더보기
BOJ)3176 도로 네트워크 문제: icpc.me/3176 N개의 도시와 그 도시를 연결하는 N-1개의 도로 네트워크가 있을 때 두 도시를 연결하는 경로 상에서 가장 짧은 도로의 길이와 가장 긴 도로의 길이를 출력하는 문제이다. 우리는 모든 도시 쌍에는 그 도시를 연결하는 유일한 경로가 있다는데에서 주어진 그래프가 트리임을 유추할 수 있다. 우리는 문제를 해결하기 위하여 LCA를 이용할 것이다. 우리는 LCA를 구할 때 두 도시의 2^i번째 부모를 저장한다. 이 때 우리는 2^i번째 부모를 저장할 뿐만 아니라 x번째 정점 기준으로 2^i번째 부모까지의 모든 간선중에 최솟값과 최댓값을 같이 저장할 수 있다. 이를 이용하여 쿼리를 처리하면 문제를 해결할 수 있다. 1234567891011121314151617181920212223242.. 더보기

티스토리툴바