전체 글 썸네일형 리스트형 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]가 합을 최소로 .. 더보기 이전 1 ··· 88 89 90 91 92 93 94 ··· 118 다음