알감자의 지식창고 알감자의 지식창고

문제 링크 https://www.acmicpc.net/problem/14288 사용 알고리즘 트리에서의 DP(Tree-DP) 세그먼트 트리(Segment Tree)느리게 갱신되는 세그먼트 트리(Lazy Propagation) 풀이 과정 회사 문화 2와 회사 문화 3을 합친 것이기 때문에 3번 쿼리에 따라서 적용되는 쿼리만 잘 처리하면 문제를 쉽게 해결할 수 있습니다. 코드 #include #include #include #include using namespace std;typedef long long ll;struct Node{ int d, u; };int n, m, p[100001], c[100001], lz[400001], d;Node tree[400001]; vector g[100001..

문제 링크 https://www.acmicpc.net/problem/25710 사용 알고리즘 브루트 포스(Brute-Force) 비둘기집 원리(Pigeonhole Principle) 풀이 과정 n의 최대값이 10만이고 \(a_i\)의 최대값은 999이기 때문에배열에 중복되는 수가 생길 수 밖에 없습니다. 중복되는 수에 대해서 여러번 계산하는 것은 의미가 없으므로 한번만 계산하도록 해야하지만 이때 같은 수끼리 곱하는 경우가 있기 때문에 배열에 같은 수를 최대 2개를 남기도록 처리를 하면 배열에 남는 수는 최대 2 * 999개가 됩니다. 이렇게 되면 시간복잡도가 \(O(n^2)\)이어도 충분하기 때문에 남은 부분은 브루트 포스로 처리하면 쉽게 문제를 해결할 수 있습니다. 코드 #include #inc..

문제 링크 https://www.acmicpc.net/problem/18227 사용 알고리즘 트리에서의 DP(Tree-DP) 세그먼트 트리(Segment Tree) 풀이 과정 어떤 도시에 물이 얼마나 채워졌는지 확인하기 위해서는 해당 도시 또는 해당 도시의 자식 도시에 총 몇번 물을 채웠는지를 확인하면 구할 수 있습니다. 이를 구하기 위해서 어떤 도시에 대해서 해당 도시의 자식 도시를 옆에 일렬로 배치하게되면 자신과 자신의 자식에 대해서 세그먼트 트리를 이용해 쿼리를 처리할 수 있습니다. 이때 어떤 도시에 한번 물을 채우는 양은 어떤 도시의 트리 상에서의 레벨과 같기 때문에 이를 물을 채운 횟수와 곱해줌으로써 물의 양을 구할 수 있습니다. 코드 #include #include #include ..

문제 링크 https://www.acmicpc.net/problem/14287 사용 알고리즘 트리에서의 DP(Tree-DP) 세그먼트 트리(Segment Tree) 풀이 과정 자신의 부하들 중 하나가 상사를 칭찬할 경우 그 값이 자신에게도 더해지기 때문에 자신의 부하들이 상사를 칭찬한 값의 합 구하면 자신의 현재 값을 알 수 있습니다. 따라서 회사 문화 2에서 했듯이 사원들을 배치하고, 칭찬받은 값에 대한 업데이트를 칭찬받은 사원에 대해서만 하고, 칭찬받은 값에 대한 합을 관리하는 세그먼트 트리를 구성하면 어떤 사원이 칭찬받은 정도를 알 수 있습니다. 코드 #include #include #include #include using namespace std; typedef long long l..

문제 링크 https://www.acmicpc.net/problem/16404 사용 알고리즘 트리에서의 DP(Tree-DP) 느리게 갱신되는 세그먼트 트리(Lazy Propagation) 풀이 과정 https://algamja1027.tistory.com/40 [백준 14268] 회사 문화 2문제 링크 https://www.acmicpc.net/problem/14268 사용 알고리즘 트리에서의 DP(Tree-DP) 느리게 갱신되는 세그먼트 트리(Lazy Propagation) 풀이 과정 어떤 사원에 대해서 그 사원의 부하들을 옆에 붙여서 배치하algamja1027.tistory.com위 문제와 풀이 방법이 같기 때문에 풀이 과정은 생략하도록 하겠습니다. 코드 #include #include #i..

문제 링크 https://www.acmicpc.net/problem/1766 사용 알고리즘 위상 정렬(Topological-Sorting) 우선순위 큐(Priority-Queue) 풀이 과정 2번 조건을 만족하기 위해서 위상 정렬을 사용하고, 3번 조건을 만족하기 위해서 위상 정렬을 사용하는 과정에서 우선순위 큐를 사용하면 모든 조건을 만족할 수 있습니다. 코드 #include #include #include #include using namespace std; typedef long long ll; int n, m, c[32001]; vector g[32001]; priority_queue, greater> pq; int main(){ ios_base::sync_with_stdio(0); c..

문제 링크 https://www.acmicpc.net/problem/27277 사용 알고리즘그리디(Greedy) 풀이 과정 뽑히지 않은 수 중에서 최대값과 최소값을 번갈아가면서 뽑으면 자연스럽게 가장 큰 수의 값을 최대한 보전하면서 값을 늘려갈 수 있습니다. 코드 #include #include #include using namespace std; typedef long long ll; int n, ret, l, c; vector v; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for (int i = 0; i > x; v.push_back(x); } sort(v.begin(), v.end()..

문제 링크 https://www.acmicpc.net/problem/11049 사용 알고리즘 동적 계획법(Dynamic-Programming, DP) 풀이 과정 어떤 구간에서의 최소 연산 수를 DP를 통해서 관리하고 M[i][0]은 i번째 행렬의 행, M[i][1]은 i번째 행렬의 열이라고 할 때, 어떤 구간 (i, j)의 최소 연산 수는 다음과 같이 정의 할 수 있습니다. \((i \leq k \(dp[i][j] = min(dp[i][j], dp[i][k] + dp[k + 1][j] + M[i][0] * M[k][1] * M[j][1])\) 해당 식을 모든 범위에 대해서 적용하기 위해 범위의 크기가 2일 때부터 n일 때까지 순서대로 적용해주면 됩니다. 코드 #include #include #..