https://www.acmicpc.net/problem/4991 4991번: 로봇 청소기 각각의 테스트 케이스마다 더러운 칸을 모두 깨끗한 칸으로 바꾸는 이동 횟수의 최솟값을 한 줄에 하나씩 출력한다. 만약, 방문할 수 없는 더러운 칸이 존재하는 경우에는 -1을 출력한다. www.acmicpc.net 필요한 배경지식 1번 풀이 : DFS, BFS 2번 풀이 : BFS, 외판원 문제(TSP) 3번 풀이 : BFS, DP, 비트마스킹 문제 해결 방법 방의 크기가 최대 20*20이므로 최단경로를 구하기 위해 BFS를 한번 수행하는 시간은 크게 문제가 되지 않습니다. 더러운 칸의 개수가 10개이므로 BFS를 최대 11번 수행하여 모든 더러운 칸과 로봇청소기 사이의 거리를 어렵지 않게 구할 수 있습니다. (di..
https://www.acmicpc.net/problem/2342 2342번: Dance Dance Revolution 입력은 지시 사항으로 이루어진다. 각각의 지시 사항은 하나의 수열로 이루어진다. 각각의 수열은 1, 2, 3, 4의 숫자들로 이루어지고, 이 숫자들은 각각의 방향을 나타낸다. 그리고 0은 수열의 마 www.acmicpc.net 필요한 배경지식 다이나믹 프로그래밍 문제 해결 방법 3차원 배열을 사용하여 DP로 문제를 해결했습니다. [1,4] 범위의 수가 N만큼 주워질때 배열 dp[n][x][y] = k에 대한 의미는 다음과 같습니다. n의 범위: [0,N] x, y의 범위: [0,4] k: n번째 수까지 입력 받았을때, 두 발의 위치가 x, y인 경우에 사용된 최소의 힘 위와 같이 정의한..
https://www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 이분 그래프의 설명을 이해하기 어려워서 위키백과를 참고했습니다 문제 해결 방법 노드를 탐색할때 1과 0이 번갈아 나타나도록 방문처리를 해주면서 탐색도중 같은 방문값이 연속적으로 나타난다면 NO를 출력하고 그렇지 않으면 YES를 출력하도록 했습니다. 입력되는 데이터 중 연결되지 않은 집합이 존재할 수 있으므로 모든 노드의 방문을 확인해 주어야 합니다. C++ 전체 코드 #include ..
https://www.acmicpc.net/problem/12746 12746번: Traffic (Large) 사람들이 가장 많이 이용하는 구간을 출력하고, 몇 명의 사람들이 그 구간을 거쳤는지 출력한다. a b c 꼴로 출력하면 되는데, 이는 사람들이 가장 많이 이용하는 구간이 a번 역과 b번 역을 연결하 www.acmicpc.net 필요한 배경지식 최소 공통 조상(LCA), 트리에서의 다이나믹 프로그래밍 문제 해결 방법 이전에 포스팅한 농장 관리 문제에서 풀이한 방법과 같은 방법을 이용하여 철로를 지난 사람의 수를 구할 수 있습니다. 농장 관리 문제와 다른점은 업데이트가 모두 이루어진 후 결과값을 출력하기 때문에, 노드에 추가되는 가중치를 배열에 누적하여 저장하고 DP로 문제를 해결할 수 있습니다. ..
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)쌍을 구해야 하므로 누적합을 이용하여 식으로 표현하면 ..