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/17142 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 필요한 배경지식 DFS, BFS 문제 해결 방법 모든 빈칸에 바이러스가 있게 되는 최소 시간을 구해야 합니다. DFS를 이용하여 활성화할 M개의 바이러스를 고르고, 해당 바이러스들을 시작노드로 BFS를 수행하여 최소 시간을 구해낼 수 있습니다. 바이러스가 총 k개 있고 m개의 바이러스를 활성화 시킬 수 있다면 C(k,m) 만큼 BFS를 수행하여 최소 시간을 구해야 합니다. 최소시간을 구하는 과정에서 바이러..
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/15957 15957번: 음악 추천 입력의 첫째 줄에는 세 정수로, 곡의 수 N(2 ≤ N ≤ 100,000), 추천 알고리즘의 결과 데이터의 수 K(1 ≤ K ≤ 100,000), 목표 점수 J(10 ≤ J ≤ 108)가 주어진다. 각각의 곡은 1번부터 N번까지 번호가 붙어 www.acmicpc.net 필요한 배경지식 병렬 이분 탐색(PBS), 펜윅 트리, 오일러 경로 테크닉 문제 해결 방법 [1,N] 번 노래를 부른 가수의 평균 점수가 J를 넘게 되는 시간을 각각 구하기 위해, 주워지는 쿼리를 이용하여 병렬 이분 탐색을 할 수 있습니다. 특정 노래를 부른 가수의 평균점수가 J점수를 언제 초과하는지 확인하기 위해 쿼리를 매개변수로 이분탐색을 하는..
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쿼리 모두 노드가 아닌 간선의 값을 처리해야 하기 때문에 모든 간..