https://www.acmicpc.net/problem/11960 11960번: Max Flow Farmer John has installed a new system of \(N-1\) pipes to transport milk between the \(N\) stalls in his barn (\(2 \leq N \leq 50,000\)), conveniently numbered \(1 \ldots N\). Each pipe connects a pair of stalls, and all stalls are connected to each-other www.acmicpc.net 필요한 배경지식 최소 공통 조상(LCA), 트리에서의 다이나믹 프로그래밍 문제 해결 방법 이전에 포스팅한 농장 관리 문제에서 ..
https://www.acmicpc.net/problem/5916 5916번: 농장 관리 첫째 줄에 농장의 수 N과 쿼리의 수 M(1 ≤ N, M ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 도로가 연결하는 농장의 번호가 주어진다. 다음 M개의 줄에는 쿼리가 한 줄에 하나씩 주어진다. www.acmicpc.net HLD 풀이가 정해이지만 LCA + 세그트리로 해결할 수 있습니다. 필요한 배경지식 최소 공통 조상(LCA) 세그먼트 트리 오일러 투어 테크닉 문제 해결 방법 우선 N개의 노드와 N-1개의 간선이 존재하므로 농장은 트리 형태의 자료구조를 가진다는것을 확인할 수 있습니다. 이 문제에서 조심해야 할 부분으로는 P와 Q쿼리 모두 노드가 아닌 간선의 값을 처리해야 하기 때문에 모든 간..
https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 필요한 배경지식 최소 신장 트리(Minimum Spanning Tree) : 크루스칼(Kruskal) 알고리즘 문제 해결 방법 단순 MST문제입니다. 유니온 파인드를 활용한 크루스칼 알고리즘을 이용했습니다. C++ 전체 코드 #include using namespace std; using tpi = tuple; int N,M; vector edge; int par[1001]{}; int find(int k){ if(k == par[k]) return k; else return par[k..
https://www.acmicpc.net/problem/10986 10986번: 나머지 합 수 N개 A1, A2, ..., AN이 주어진다. 이때, 연속된 부분 구간의 합이 M으로 나누어 떨어지는 구간의 개수를 구하는 프로그램을 작성하시오. 즉, Ai + ... + Aj (i ≤ j) 의 합이 M으로 나누어 떨어지는 (i, j) www.acmicpc.net 필요한 배경지식 누적 합 : prefix sum 문제 해결 방법 누적합 알고리즘을 이용하여 1번째부터 n번째까지의 수의 합을 S[n]이라고 나타내면 i번째 수부터 j번째까지 수들의 합 S[i,j]를 S[j] - S[i-1]로 나타낼 수 있습니다. 문제 조건에서 S[i,j] % M이 0인 (i,j)쌍을 구해야 하므로 누적합을 이용하여 식으로 표현하면 ..
백준 14267번 - 회사 문화 1
https://www.acmicpc.net/problem/14267 14267번: 회사 문화 1 영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하 www.acmicpc.net 필요한 배경지식 트리에서의 다이나믹 프로그래밍 문제 해결 방법 문제를 읽어보면 직원들의 관계가 트리형태로 이루어져 있다는 것은 충분히 확인할 수 있습니다. 또한 i번째 직원이 받은 총 칭찬의 수는 i번째 직원이 직속 상사로부터 받은 칭찬과 i번째 직원을 부하로 가지는 모든 직원들이 직속 상사로부터 받은 칭찬을 더한 값이라고 볼 수 있습니다. 예시로 아래와 같은 트리를 살펴 봅시다. i번째 직원이..
https://www.acmicpc.net/problem/17780 17780번: 새로운 게임 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하 www.acmicpc.net 문제를 제대로 읽지않아 한참동안 헤매었던 문제였습니다. 턴이 진행되던 중에 말이 4개 이상 쌓이면 게임을 끝내야 하는데 K개와 비교한 것이 문제였습니다. 필요한 배경지식 std::vector 컨테이너에 대한 이해 문제 해결 방법 Vector를 잘 활용하면 직관적으로 풀어낼 수 있습니다. 선언한 변수의 정보는 다음과 같습니다. using pii = pair; using dpi = pair; int ..
https://www.acmicpc.net/problem/10159 10159번: 저울 첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 www.acmicpc.net 입력으로 주어지는 물건의 대소관계를 그래프로 표현하면 사이클이 없는 방향 그래프(DAG)로 표현할 수 있고 결과를 출력하기 위해 두 물건을 비교해야 하므로 위상정렬이 먼저 떠올랐습니다. 하지만 모든 물건들간에 비교가 필요하고 N의 최대가 100이라는 점에서 플로이드 와샬 알고리즘을 해결방법으로 생각해 낼 수 있었습니다. 필요한 배경지식 플로이드 와샬 알고리즘 : Floyd..
백준 1368번 - 물대기
https://www.acmicpc.net/problem/1368 1368번: 물대기 첫 줄에는 논의 수 N(1 ≤ N ≤ 300)이 주어진다. 다음 N개의 줄에는 i번째 논에 우물을 팔 때 드는 비용 Wi(1 ≤ Wi ≤ 100,000)가 순서대로 들어온다. 다음 N개의 줄에 대해서는 각 줄에 N개의 수가 들어 www.acmicpc.net 필요한 배경지식 최소 신장 트리 : Minimum Spanning Tree - 크루스칼(Kruskal) 알고리즘 문제 해결 방법 MST를 활용하여 풀어낼 수 있는 문제입니다. i번째 논과 j번째 논을 연결하는데 드는 비용 Pi,j를 그래프의 간선으로 표현하면, 문제의 조건에서 Pi,j = Pj,i 라는 것을 확인할 수 있으므로 N개의 논은 무방향 그래프로 나타낼 수 ..