본문 바로가기

알고리즘 관련/BOJ

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.. 더보기
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.. 더보기
BOJ)2275 트리의 높이 줄이기 문제: icpc.me/2275 트리에서 모든 리프까지의 거리가 H이하로 되게 만들 때 비용의 최솟값을 구하는 문제이다. 우리는 가능하다면 부모에서 높이를 줄여야지 한번에 여러 리프들의 높이를 동시에 줄이는게 가능하다는 사실을 이용하여 모든 리프에 줄여야할 가중치를 할당하고 바텀업 방식으로 부모에서 높이를 줄이는게 가능하다면 줄이는 방식으로 문제를 해결해주면 된다. 문제를 해결하기 위하여 dfs로 전처리를 해줘야하는데 해당 노드의 깊이 중첩 가중치를 미리 구해주면 쉽게 계산해 줄 수 있다. 아래 코드에서 각 배열이 의미하는건 r[v]는 v노드에서 줄여야하는 가중치이고 d[v]는 v까지의 누적 가중치이다. 123456789101112131415161718192021222324252627282930313233.. 더보기
BOJ)8012 한동이는 영업사원! 문제:icpc.me/8012 한동이가 방문해야 할 도시를 x->y->z->w 순이라면 x->y의 거리와 y->z의 거리 z->w의 최소시간을 더해서 출력하는게 답이된다. 결국 N,M제한 때문에 거리를 logN의 시간복잡도에 해결을 해줘야하는데 우리는 주어진 그래프가 트리라는걸 이용하여 LCA를 통하여 계산해 줄수 있다. x와 y의 최단 거리는 결국 모든 간선의 가중치가 1이니까 깊이를 이용하여 dph[x]+dph[y]-2*dph[lca(x,y)] 로 계산할 수 있다. 이를 이용하여 답을 구해주면 된다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#in.. 더보기
BOJ)1761 정점들의 거리 문제:icpc.me/1761 두 정점간의 최단거리를 매 쿼리마다 출력하는 문제이다. 우리가 기본적으로 알고 있는 그래프의 최단거리 알고리즘들은 시간복잡도 때문에 사용할 수가 없다. 하지만 우리는 이 그래프가 트리라는것을 이용하여 매 쿼리를 O(logN) 시간마다 처리해 줄 수있다. 우리는 lca를 이용하여 두 노드의 최단 거리를 계산할 것이다. lca전처리를 위해 dfs를 돌려줄 때 루트에서 부터 자기 자신까지의 거리를 dist배열에 저장해두면 두 노드의 X,Y 의최단 거리는 dist[X]+dist[Y]-2*dist[lca(X,Y)]로 정의 할 수있다. 이를 이용하여 매 쿼리를 logN시간에 처리해주면 된다. 12345678910111213141516171819202122232425262728293031.. 더보기
BOJ)2512 예산 문제:icpc.me/2512 최소중의 최대를 구하는 전형적인 파라메트릭 서치 문제이다. 다만 주의해야 할 건 모든 인풋 a[i]의 합이 m보다 작을 경우 a[i]중에 최댓값을 출력해줘야 하는 예외 케이스가 있다. 123456789101112131415161718192021222324252627282930313233343536#include #include typedef long long ll;using namespace std;ll n, a[10000], m, lo, hi, ma, s;int main() { scanf("%lld", &n); for (int i = 0; i = s) { printf("%lld\n", ma); return 0; } lo = 0; hi = 21000000000; while (.. 더보기
BOJ)1576 DNA점수 문제: icpc.me/1576 점수판을 채우는 규칙이 주어질 때 주어진 DNA 문자열의 각 문자열에서 얻을 수 있는 점수의 평균의 최댓값을 구하는 문제이다. 우리는 평균의 최댓값을 구하기 위해서 총점의 최댓값을 구하면 된다. 결국 총점이 최대가 되도록 점수판을 채우면 되는것이다. 우리는 다이나믹 프로그래밍을 이용해서 총점이 최대가 되도록 점수판을 채워나갈 것이다. 점수판을 채우는 순서는 임의로 지정해 줄 수 있다. dp테이블은 dp[4][4][10*16*2] 이 될것이다. dp 테이블이 의미하는 바는 dp[x][y][z]일때 (x,y)까지 채웠고 점수판의 점수 총합이 z일 때 총점의 최댓값으로 정의하면 된다. 우리는 점수판의 총점이 음수가 될 때도 있으니 그걸 고려하여 10*16의 총점에 2를 곱해주었다.. 더보기

티스토리툴바