분류 전체보기130 [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++] 백준 27172번: 수 나누기 게임 (수학) https://www.acmicpc.net/problem/27172문제 이해하기 문제의 요구사항은 다음과 같습니다.n명의 플레이어가 1부터 1000000 사이의 수 하나를 각각 가질 때, 게임이 종료된 후 각 플레이어의 점수를 구하여라 게임 규칙은 다음과 같습니다.1. 한 플레이어는 다른 모든 플레이어와 한 번씩 결투를 진행한다.2. 결투는 공격하는 플레이어의 수로 공격을 받는 플레이어의 수를 나누었을 때, 나머지가 0이면 공격자가 승리한다. 나누어 떨어지지 않으면 무승부이다.3. 승리한 플레이어는 1점을 얻고, 패배한 플레이어는 1점을 잃는다.(점수는 음수도 가능하다.)시간복잡도 어림하기브루트 포스 알고리즘 가장 단순한 알고리즘을 생각해 보면, 각 플레이어의 수를 배열에 저장해 두고, 두 개의 for .. 2024. 10. 23. [C++] 백준 17404번: RGB거리 2 (DP) https://www.acmicpc.net/problem/17404문제 이해하기 문제의 요구사항은 다음과 같습니다.N개의 집을 인접한 집끼리 다른 색으로 칠할 때 모든 집을 칠하는 비용의 최솟값을 구하여라. 1번 집과 N번 집도 인접한 것으로 본다. 시간복잡도 어림하기브루트포스 알고리즘 각 집은 빨강, 초록, 파랑 세 색깔로 칠할 수 있습니다. 이때, 인접한 집끼리는 같은 색을 칠할 수 없으므로 한 집당 두개의 상태를 가질 수 있습니다. 문제에서 집은 최대 1000개이므로 최대 경우의 수는 2^1000 쯤 될 것입니다. 따라서 제한 시간 내에 모든 경우의 수를 탐색할 수 없습니다.DP 알고리즘 현재 집은 이전 집의 상태를 보고 어떤 색깔을 칠할지 결정할 수 있습니다. 즉, 현재 상태를 구하기 위해 이전 .. 2024. 10. 22. [C++] 백준 1647번: 도시 분할 계획 (최소 신장 트리) https://www.acmicpc.net/problem/1647문제 이해하기 문제의 요구사항은 다음과 같습니다.한 마을을 두 마을로 분리할 때, 두 마을을 유지하는 길의 최소 비용을 구하여라.시간복잡도 어림하기 최소 신장 트리(Minimum Spanning Tree) 그래프의 모든 노드를 최소 비용으로 연결해야 하는 문제이므로 최소 신장 트리를 만드는 문제입니다. 최소 신장 트리는 크루스칼(Kruskal), 프림(Prim) 알고리즘으로 찾을 수 있습니다. 크루스칼 알고리즘은 간선 선택 기반 최소 신장 트리 구성 알고리즘으로 O(eloge)의 시간복잡도를 가지고, 프림 알고리즘은 정점 선택 기반 알고리즘으로 O(n^2)의 시간복잡도를 가집니다. 문제에서 e의 최댓값은 1,000,000이고 n의 최댓값은 .. 2024. 10. 16. [C++] 백준 15681번: 트리와 쿼리 (DP) https://www.acmicpc.net/problem/15681문제 이해하기 문제의 요구사항은 다음과 같습니다.루트가 R인 트리가 주어질 때, 어떤 노드 U를 루트로 하는 서브트리에 속한 정점의 수를 구하여라.시간복잡도 어림하기DFS 알고리즘 서브트리의 개수를 구하는 문제이므로 DFS를 사용할 수 있습니다. 정점의 수가 N인 트리에서 DFS 알고리즘을 사용하면 O(N)의 시간복잡도를 가집니다. 한 번 방문한 정점은 다시 방문하지 않기 때문입니다. 이 과정을 모든 쿼리 Q번 반복하면 시간복잡도는 O(NQ) 입니다. N과 Q의 최댓값은 모두 100,000 이고, NQ = 100,000 x 100,000 = 10,000,000,000 (백억)이므로 제한 시간 내에 해결하기 어려운 수치입니다. 따라서 DFS.. 2024. 10. 15. 이전 1 2 3 4 ··· 22 다음