본문 바로가기

분류 전체보기

BOJ)9252 LCS 2 문제: icpc.me/9252 LCS를 구해주는 문제이다. 다이나믹 프로그래밍을 통하여 LCS를 구해준 뒤 백트래킹하여 해당 LCS를 출력해주면 된다. dp테이블의 정의는 dp[x][y]는 첫번째 문자열을 x까지 두번째 문자열을 y까지 봤을 때 LCS의 크기이다. 점화식은 (if a[x]!=b[y]) dp[x][y]=max(dp[x][y-1],dp[x-1][y]) else dp[x][y]=dp[x-1][y-1] 이 된다. 소스코드에서는 테이블의 정의를 반대로 사용하였다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include #include #include #include #include usin.. 더보기
BOJ)1701 Cubeditor 문제: icpc.me/1701 문자열이 주어질 때 2번이상 나오는 부분 문자열 중 가장 길이가 긴 부분 문자열의 길이를 출력하는 문제이다. N이 5000밖에 안되기 때문에 문자열의 모든 Suffix에 대해서 failure function을 구해준 뒤 그 중 최댓값을 출력하면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940#include #include #include #define MAX_N 5001using namespace std;char a[MAX_N][MAX_N];int l, r;vector pi;void getpi(const char *c,int len) { pi.clear(); pi.resize(len); .. 더보기
BOJ)11585 속타는 저녁 메뉴 문제: icpc.me/11585 문자열 A와 B가 주어질 때 환형으로 이루어진 문자열 B로 이루어진 돌림판을 돌려서 A가 나올 확률을 구하는 문제이다. 우리는 환형으로 이루어진 문자열 B를 구현하기 위하여 문자열 B뒤에 문자열 B를 붙인 뒤 KMP를 이용하여 2개의 연속 된 문자열 B에서 A를 찾는 횟수를 구한 뒤 기약 분수 형태로 만들어 출력해주면 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152#include #include #include #define MAX_N 1000000using namespace std;char a[MAX_N], b[2 * MAX_N];int n,.. 더보기
BOJ)4354 문자열 제곱 문제: icpc.me/4354 문자열 A가 주어질 때, A를 서로 같은 부분 문자열 N개로 쪼갤 수있을 때 N의 최댓값을 출력하는 문제다. 우리는 문자열이 N개의 부분 문자열로 쪼개질 때 규칙성을 찾아보면 KMP에서의 pi배열의 pi[a.length()-1]=(n-1/n)*a.length()를 만족한다는 걸 알 수 있다. 이를 이용하여 최대 N을 계산해주면 된다. 12345678910111213141516171819202122232425262728293031323334#include #include #include #include #include using namespace std;string a;vector pi;void getpi(){ pi.clear(); pi.resize(a.length()); i.. 더보기
BOJ)2233 사과나무 문제:icpc.me/2233 트리가 주어질 때 루트에서 DFS를 탐색하는 순서대로 0은 노드를 처음 방문할 때 1은 노드에서 더 이상 탐색이 불가능하여 return 될 때를 순서대로 수열로 나타낼 때 썩은 사과 2개를 동시에 제거 가능한 가장 가까운 노드의 0과 1의 위치를 출력하는 문제이다. 우리는 썩은 사과 2개가 주어질 때 동시에 제거 가능한 가장 가까운 노드를 LCA를 통하여 구할 수 있다. 0과 1로 이루어진 수열에서 0일 경우에는 노드를 추가하고 현재 보는 노드의 자식으로 설정 1일 경우에는 현재 보고 있는 노드의 부모를 현재 보고있는 노드로 설정해 주어 깊이와 부모를 구해준 후 LCA를 구해주면 된다. 12345678910111213141516171819202122232425262728293.. 더보기
단절점(Articulation Point)와 단절선(Bridge) 하나의 컴포넌트로 이루어진 무방향 그래프에서 한 정점을 제거했을 때 그래프가 두개 이상의 컴포넌트로 나누어지는 정점을 단절점이라고 합니다.다음과 같은 무방향 그래프가 있다고 해봅시다. 여기서 빨간색 테두리로 이루어진 정점들중 하나를 지울 경우 컴포넌트가 2개로 나누어지게 됩니다. 이러한 성질을 가지는 정점들을 단절점이라고 부릅니다. 그러면 우리는 단절점을 어떤 방법으로 찾을 수 있을까요? 우선은 단절점을 찾기 위해서 우선 단절점이 가지는 특징을 알아야 됩니다. 아까의 그래프에서 단절점인 빨간정점에 연결된 정점들을 초록정점으로 색칠해봤습니다. 우리는 어떤 정점 A에 연결된 모든 정점들 중 두 정점들 간에 정점 A를 거치지않고 갈 수 있는 우회경로가 존재하지 않는 경우가 존재한다면 정점 A는 단절점으로 판단.. 더보기
BOJ)3682 동치 증명 문제: icpc.me/3682 그래프에서 동치임을 증명하기 위해 사용하는 함축의 수의 최솟값을 출력하는 문제이다. 우리는 동치임을 증명하기 위해서 그래프의 사이클을 생성해주면 된다. 우리는 그래프의 SCC를 분류한 뒤 다시 SCC들을 정점으로 가지는 그래프로 압축하여 각 SCC의 indegree와 outdegree의 수를 구해준 뒤 indegree가 0인 정점과 outdegree가 0인 정점중 최댓값을 출력해주면 된다. 그래프의 사이클을 만들어야 하기 때문에 사이클이 존재하려면 indegree와 outdegree가 적어도 1씩 존재해야 하기 때문이다. 단 그래프가 하나의 SCC를 이룰 경우는 예외처리를 해주어야만 한다. 12345678910111213141516171819202122232425262728.. 더보기
BOJ)11338 XOR Sum 문제: icpc.me/11338 n개의 쿼리가 주어질 때 2가지 쿼리에 따라서 문제를 해결하는 문제이다. insert 쿼리는 리스트에 숫자를 추가하는것이며 print 쿼리는 리스트 중에 상위 K숫자를 XOR한 값을 출력하는 문제이다. 우리는 매 print마다 리스트에서 XOR을 할 경우 시간초과가 나므로 insert 될 때 마다 모든 값을 XOR해준 뒤 minheap을 이용하여 리스트 숫자가 K를 초과할때 마다 최솟값을 XOR해준다. 이는 A^X^X=A가 되는 원리를 이용하는 풀이이다. 1234567891011121314151617181920212223242526272829303132#include #include #include using namespace std;char a[7];int t, m, k.. 더보기
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의 길이가 답이됩니다. 즉, 그 수열에서 존재하는 모든 부분 증가 수열.. 더보기

티스토리툴바