본문 바로가기

전체 글

BOJ)2211 네트워크 복구 문제:icpc.me/2211 원본 네트워크가 주어질 때 1.최소 개수의 회선만 복구하면서 2. 1번 노드에서 k번 노드의 최단거리가 원본보다 길어지지 않도록 복구하라는 문제이다. 처음에 1번 조건만 봤을때는 MST를 떠올릴 수 있으나 2번조건 때문에 다익스트라를 이용하여 1번 정점부터 최단거리를 구해주면서 사용되는 모든 간선을 벡터에 저장해주면 된다. 1234567891011121314151617181920212223242526272829303132333435363738394041#include #include #include #include #include #define MAX_N 1000using namespace std;int n, m, a, b, c, dp[MAX_N + 1];priority_qu.. 더보기
[최장 증가 수열] LIS(Longest Increasing Subsequence) 이번 글에서는 DP중에서 특별한 케이스인 LIS에 대해 얘기해보자 합니다. LIS(Longest increasing Subsequence)는 가장 긴 증가하는 부분 수열 정도로 해석 가능합니다. 쉬운 이해를 위해서 예를 들어보겠습니다. 다음과 같은 수열이 존재한다고 해봅시다. 여기서 LIS를 찾는다면 다음과 같이 빨간 부분으로 색칠된 부분이 LIS가 됩니다. 눈치 빠르신 분들은 벌써 알아채셨을겁니다. LIS는 앞에서부터 뒤로 숫자를 선택하며 부분 수열을 구성해 나갈 때 증가하는 순서대로 숫자를 고르면서 고른 부분 수열의 길이가 최대 길이가 되도록 숫자를 선택하는 경우입니다. 보통 LIS를 구하는 문제의 답은 한 수열에서 주어지는 LIS의 길이가 답이됩니다. 즉, 그 수열에서 존재하는 모든 부분 증가 수열.. 더보기
BOJ)2275 트리의 높이 줄이기 문제: icpc.me/2275 트리에서 모든 리프까지의 거리가 H이하로 되게 만들 때 비용의 최솟값을 구하는 문제이다. 우리는 가능하다면 부모에서 높이를 줄여야지 한번에 여러 리프들의 높이를 동시에 줄이는게 가능하다는 사실을 이용하여 모든 리프에 줄여야할 가중치를 할당하고 바텀업 방식으로 부모에서 높이를 줄이는게 가능하다면 줄이는 방식으로 문제를 해결해주면 된다. 문제를 해결하기 위하여 dfs로 전처리를 해줘야하는데 해당 노드의 깊이 중첩 가중치를 미리 구해주면 쉽게 계산해 줄 수 있다. 아래 코드에서 각 배열이 의미하는건 r[v]는 v노드에서 줄여야하는 가중치이고 d[v]는 v까지의 누적 가중치이다. 123456789101112131415161718192021222324252627282930313233.. 더보기

티스토리툴바