본문 바로가기

Problem Solving/BaekJoon

 (10)
16236 아기 상어 16236번: 아기 상어 N×N 크기의 공간에 물고기 M마리와 아기 상어 1마리가 있다. 공간은 1×1 크기의 정사각형 칸으로 나누어져 있다. 한 칸에는 물고기가 최대 1마리 존재한다. 아기 상어와 물고기는 모두 크기를 가 www.acmicpc.net 아기 상어가 물고기를 먹을 때마다 새롭게 BFS를 수행하면 된다. 조건만 빠뜨리지 않고 처리한다면 무난히 풀 수 있는 문제이다. 더보기 #include #include #include #include #include using namespace std; using mypair = pair; int n; int baby_shark = 2; int space[20][20]; int visited[20][20]; int cnt; int min_dist; mypa..
1005 ACM Craft 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net DP라기 보다는 위상 정렬에 더 무게를 둔 문제이다. 각 건물의 선행 건물들과 선행 건물의 수를 그 건물에 대응되는 배열의 위치에 저장한 후 큐를 이용하여 건물들을 짓는 것에 조건을 만족하며 소요되는 최소 시간을 계산하는 방식으로 해결하였다. 더보기 더보기 #include #include #include using namespace std; int main(void) { ios_base::sync_with_stdio(false); cin.tie(nullpt..
17142 연구소3 17142번: 연구소 3 인체에 치명적인 바이러스를 연구하던 연구소에 승원이가 침입했고, 바이러스를 유출하려고 한다. 바이러스는 활성 상태와 비활성 상태가 있다. 가장 처음에 모든 바이러스는 비활성 상태이고 www.acmicpc.net 이번 문제는 간단히 정리하면 M개 이상 10개 이하의 임의의 지점을 선택해서 탐색을 진행했을 때에 모든 방을 탐색하는 것에 소요되는 최소 시간을 구하는 문제이다. 먼저 탐색 공간의 크기가 최대 50 X 50이고 바이러스는 최대 10개이기에 전역 탐색을 진행해도 빠르게 끝낼 수 있다고 판단되어 next_permutation 함수를 사용해서 바이러스를 활성화하는 모든 경우의 수를 탐색하였다. 그리고 활성화 바이러스는 인접한 지역으로 동시에 퍼지므로 사용한 알고리즘은 BFS를 ..
14476 최대공약수 하나 빼기 14476번: 최대공약수 하나 빼기 첫째 줄에 정수의 개수 N (4 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 N개의 수가 주어진다. 각각의 수는 20억을 넘지 않는 자연수이다. www.acmicpc.net 최대공약수를 구하는 것에 사용되는 유클리드 호제법에는 결합 법칙이 적용된다. 예를 들어 GCD(4,18, 14)의 결과는 GCD(GCD(4,18), 14)의 결과와 같다. 그리고 이 문제와 같이 배열에서 하나의 수를 제거했을 때의 최대공약수는 위 사실을 이용하면 간단히 해결할 수 있다. a b c d e f a gcd(a,b) gcd(a,b,c) gcd(a,b,c,d) gcd(a,b,c,d,e) gcd(a,b,c,d,e,f) gcd(a,b,c,d,e,f) gcd(b,c,d,..
2056 작업 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net DP와 DFS를 활용하여 해결했다. 각 작업을 노드로, 그리고 각 작업과 선행작업을 방향이 있는 간선으로 연결했다. 그래프를 구성한 다음에는 각 노드에 연결된 선행 작업들을 DFS 방식으로 순회하며 최대 작업 시간을 가진 노드를 찾고, 그 노드의 작업시간과 해당 노드의 수행 시간을 더해 작업시간으로 정했다. 그리고 이 과정에서 각 노드의 작업시간을 구하면 메모리제이션을 이용하여 한번만 찾도록 했다. 이 과정을 수행하면서 모든 작업을 완료하기 위한 최소 ..
1987 알파벳 1987번: 알파벳 세로 R칸, 가로 C칸으로 된 표 모양의 보드가 있다. 보드의 각 칸에는 대문자 알파벳이 하나씩 적혀 있고, 좌측 상단 칸 (1행 1열) 에는 말이 놓여 있다. 말은 상하좌우로 인접한 네 칸 중의 한 칸으 www.acmicpc.net 전형적인 DFS 문제이다. 리트코드에서 DFS 사용하는 문제랑 비교도 할 수 없을 정도로 단순하게 입력받아서 DFS 돌리면 된다. 그런데 이거 의외로 시간 복잡도가 빡빡해서 DFS 내부적으로 쓰이는 연산은 가벼운 걸로 수행해야 했었다. 그냥 아무 생각 없이 map 사용하고, 매번 map 복사하니까 바로 시간 초과가 났다... 그래서 그냥 배열 써버리고 재사용하니까 여유롭게 통과됐다. C++ 더보기 #include using namespace std; in..
1806 부분합 1806번: 부분합 첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다. www.acmicpc.net 배열의 연속된 부분합 중, 합이 S 이상이 되는 가장 짧은 부분의 길이를 구하는 문제이다. 일단 분류는 투 포인터로 되어있는데 난 그냥 이진 탐색 써서 풀었다. 먼저 각 구간의 누적합을 계산한 다음, 배열의 첫번째 위치부터 n - 1번째 위치를 구간의 시작점으로 두고, 구간의 끝점은 이진 탐색으로 찾았는데, 끝점이 될 수 있는 left bound는 lbound, right bound는 rbound로 정하고 lbound와 rbound 사이의 거리를 ..
2228 구간 나누기 다이나믹 프로그래밍으로 해결해야 하는 knapsack 계열의 문제이다. vec = vector(n + 1); dp = vector(n + 1, vector(m + 1, -1)); 먼저 배열이 저장될 벡터 vec와 메모라이즈 된 값이 저장될 벡터 dp를 만들어주었다. 여기서 dp[i][j]의 의미는 i번째 배열까지 탐색했을 때, j개의 구간으로 조합했을 때의 최댓값을 나타내며, 메모라이즈 여부를 확인하기 위해서 -1로 초기화하였다. int search(int n, int m) { if (m == 0) return 0; if (n 0; --i) { partial_sum += vec[i]; temp = partial_sum + search(i - 2, m - 1); if (temp > dp[n][m]) dp[..
728x90

티스토리툴바