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개의 논은 무방향 그래프로 나타낼 수 ..
https://www.acmicpc.net/problem/2512 2512번: 예산 첫째 줄에는 지방의 수를 의미하는 정수 N이 주어진다. N은 3 이상 10,000 이하이다. 다음 줄에는 각 지방의 예산요청을 표현하는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 값들은 모두 1 이상 www.acmicpc.net 필요한 배경지식 이분탐색, 매개 변수 탐색 : parametric search 문제 해결 방법 답으로 출력될 값(배정될 예산)을 기준으로 하여, 매개 변수 탐색을 하면 됩니다. 즉, 이분탐색으로 배정될 예산을 구하는 과정에서 그 예산이 배정될 수 있으면 예산을 늘리고 배정될 수 없다면 줄이면서 가장 큰 값을 찾아나가는 방법입니다. 이분탐색의 구현은 lower bound 방식을 활용하여 구현했..
https://www.acmicpc.net/problem/10775 10775번: 공항 예제 1 : [2][?][?][1] 형태로 도킹시킬 수 있다. 3번째 비행기는 도킹시킬 수 없다. 예제 2 : [1][2][3][?] 형태로 도킹 시킬 수 있고, 4번째 비행기는 절대 도킹 시킬 수 없어서 이후 추가적인 도킹은 불 www.acmicpc.net 처음에는 세그먼트 트리를 이용하여 풀어 보기 위해 많은 시간 고민했지만 쉽지 않았습니다. 결국은 태그에서 힌트를 얻어 유니온 파인드를 이용하여 문제를 해결했습니다. 필요한 배경지식 유니온 파인드 : Union-Find (Disjoint-set) 문제 해결 방법 g가 주어질때 들어갈 수 있는 가장 큰 번호의 게이트에 비행기를 도킹해 주면 비행기를 최대로 도킹할 수 ..