본문 바로가기

[Algorithm] 허수에서 실수까지/Gold331

[C++] 백준 20303번: 할로윈의 양아치 (DP) https://www.acmicpc.net/problem/20303문제 이해하기 문제의 요구사항은 다음과 같습니다.한 아이의 사탕을 뺏으면 그 아이와 연결된 친구의 사탕도 모두 뺏을 때, K명 이상의 아이의 사탕을 뺏지 않고 최대로 구할 수 있는 사탕의 개수를 구하여라.시간복잡도 어림하기브루트포스 알고리즘 아이들의 친구 관계수의 최솟값이 0이므로 모든 아이가 친구가 없는 상황을 생각해 볼 수 있습니다. 이 경우에 K명의 아이를 울리지 않고 사탕을 얻을 수 있는 경우의 수는 nCk-1 입니다. 즉, 아이 n 명 중에서 사탕을 뺏을 아이 k - 1명을 뽑는 경우의 수와 같습니다. 이때 n의 최댓값은 30,000이고 k의 최댓값은 3000입니다. 30000C2999를 대략적으로 계산해봐도 분자가 아주 큰 수가.. 2024. 11. 4.
[C++] 백준 16724번: 피리 부는 사나이 (DFS) https://www.acmicpc.net/problem/16724문제 이해하기 문제의 요구사항은 다음과 같습니다.방향 지도가 주어질 때 회원들이 지도 어느 구역에 있더라도 SAFE ZONE에 들어가게 하는 SAFE ZONE의 최소 개수를 구하여라. 우선 직관적으로 문제를 살펴보면 SAFE ZONE의 위치는 이동이 순환되는 위치에 있음을 알 수 있습니다. 즉, 그래프에서 사이클이 형성되는 위치에 SAFE ZONE을 배치하면 해당 경로의 어느 위치에서 SAFE ZONE에 도달할 수 있습니다. 하지만, 항상 사이클이 생기지 않을 수도 있으니 이를 더 일반화해봅시다. 사이클이 형성되지 않더라도 같은 경로의 마지막 위치에 SAFE ZONE을 배치하면 해당 경로의 모든 위치는 마지막 SAFE ZONE으로 이동하게.. 2024. 10. 25.
[C++] 백준 2629번: 양팔 저울 (브루트 포스, DP) https://www.acmicpc.net/problem/2629문제 이해하기 문제의 요구사항은 다음과 같습니다.추와 구슬이 주어질 때, 주어진 추로 구슬의 무게를 확인할 수 있는지 여부를 구하여라. 말이 어려울 수 있지만 더 간단히 요약해보면, 주어진 숫자를 더하고 빼는 연산만 사용하여 목표 숫자를 만들 수 있는지를 구하는 문제입니다.시간복잡도 어림하기브루트 포스 알고리즘 브루트 포스 알고리즘으로 가능한 모든 합 배열을 만들고, 이후 목표 숫자를 만들 수 있는지 판단하는 로직을 사용할 수 있습니다. 문제의 조건에 따라 더하기와 빼기 연산만 가능하므로 한 숫자 당 두 개의 연산을 진행할 수 있습니다. 지금까지 구한 모든 수에 더하고 빼는 연산을 진행할 것이므로 2^n 정도의 속도로 숫자가 늘어날 것입니다.. 2024. 9. 10.
[C++] 백준 14442번: 벽 부수고 이동하기 2 (BFS) https://www.acmicpc.net/problem/14442문제 이해하기 문제의 요구사항은 다음과 같습니다.주어진 맵에서 벽을 최대 K번 부수고 이동할 수 있을 때, (1, 1)에서 (N, M)까지의 최단거리를 구하여라.시간복잡도 어림하기BFS 알고리즘 가중치가 1로, 가중치가 동일한 최단거리 문제이므로 BFS를 사용하여 문제를 해결할 수 있습니다. 탐색 가능한 위치는 최대 N x M으로 1000 x 1000 = 1,000,000입니다. 이때, 벽을 깰 수 있는 최대 횟수는 10회이므로 벽을 깬 횟수까지 탐색 위치에 포함시키면 1,000,000 x 10 = 10,000,000 입니다. 따라서 제한 시간 내에 문제를 해결할 수 있습니다.알고리즘 설계하기  일반적인 문제는 탐색 위치가 y 좌표, x .. 2024. 9. 9.
[C++] 백준 2533번: 사회망 서비스 (DP) https://www.acmicpc.net/problem/2533문제 이해하기 문제의 요구사항은 다음과 같습니다.얼리어답터가 아닌 사람에게 아이디어를 전파하기 위해서는 주변 사람이 모두 얼리어답터여야 할 때, 모든 사람에게 아이디어를 전파하기 위한 최소 얼리어답터의 수를 구하여라.시간복잡도 어림하기브루트 포스 알고리즘 모든 사람은 얼리어답터이거나 얼리어답터가 아닌 두 상태를 가집니다. 이를 기반으로 모든 경우의 수를 구해본다면 2^n개 입니다. 이때, n의 최댓값은 1,000,000 이므로 경우의 수가 너무 많습니다. 따라서 제한 시간 내에 문제를 해결할 수 없습니다.DP 알고리즘 어떤 사람이 얼리어답터라면, 그와 연결된 다른 사람은 얼리어답터이거나, 얼리어답터가 아닌 두 상태를 가집니다. 또한, 어떤 .. 2024. 9. 4.
[C++] 백준 1939번: 중량제한 (다익스트라) https://www.acmicpc.net/problem/1939문제 이해하기 문제의 요구사항은 다음과 같습니다.섬과 각 섬을 잇는 다리의 중량 제한이 주어질 때, 한 섬에서 다른 섬으로 한 번에 물품을 옮길 수 있는 최대 중량을 구하여라.시간복잡도 어림하기브루트 포스 알고리즘(플로이드 워셜 알고리즘) 문제를 해결하기 위해 가능한 모든 경로를 탐색해볼 수 있습니다. 해당 알고리즘으로는 플로이드 워셜 알고리즘이 있습니다. 하지만, 플로이드 워셜 알고리즘은 O(n^3)의 시간복잡도를 가집니다. 문제에서 n의 최댓값은 10,000 이므로 제한 시간 내에 문제를 해결하기 어렵습니다.DP 알고리즘(다익스트라 알고리즘) 한 노드에서 다른 노드까지의 가중치를 구하는 문제이므로 다익스트라 알고리즘을 떠올릴 수 있습니다.. 2024. 9. 3.

티스토리툴바