[Algorithm] 허수에서 실수까지/Gold430 [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++] 백준 14938번: 서강그라운드 (플로이드 워셜) https://www.acmicpc.net/problem/14938문제 이해하기 문제의 요구사항은 다음과 같습니다.필드의 정보와 수색 범위가 주어질 때, 얻을 수 있는 최대 아이템 개수를 구하여라.시간복잡도 어림하기플로이드 워셜 알고리즘 문제를 살펴봤을 때, 그래프 탐색이 필요하고, 탐색 가능한 거리에 제한이 있는 문제입니다. 따라서 어떤 노드에 도달가능한 최단거리를 알아야, 해당 노드까지 탐색이 가능한지 판단할 수 있습니다. 이때, 각 노드에 대해 모든 노드에 대한 최단거리 정보가 필요하므로 플로이드 워셜 알고리즘을 사용할 수 있습니다. 플로이드 워셜 알고리즘의 시간복잡도는 O(n^3)이고, 문제에서 n의 최댓값이 100이므로 n^3 = 1,000,000(백만) 입니다. 따라서 제한 시간 내에 문제를 .. 2024. 9. 26. [C++] 백준 10830번: 행렬 제곱 (분할 정복) https://www.acmicpc.net/problem/10830문제 이해하기 문제의 요구사항은 다음과 같습니다.크기가 N x N인 행렬을 B제곱한 결과를 구하여라. 각 원소는 1000으로 나눈 나머지를 취한다.시간복잡도 어림하기단순 계산 알고리즘 먼저 단순한 행렬 계산식부터 생각해 봅시다. 기본적인 행렬 계산 알고리즘은 O(n^3)의 시간복잡도를 가집니다. 행렬 M1, M2가 있다고 했을 때, M1의 각 행과 M2의 각 열에 대응하는 원소를 모두 곱해 더해야하고, 이 과정을 M1의 모든 행에 대해 반복해야 하기 때문입니다. 하지만 문제의 B의 최댓값은 1,000,000,000,000 으로 1조에 해당하는 큰 수입니다. 당연히 이를 제한 시간에 해결할 수 없으므로 다른 방법을 사용해야 합니다.분할 정복.. 2024. 9. 25. [C++] 백준 7662번: 이중 우선순위 큐 https://www.acmicpc.net/problem/7662문제 이해하기 문제의 요구사항은 다음과 같습니다.주어진 명령을 처리한 후 Q에 남아있는 값 중 최댓값과 최솟값을 구하여라. 명령의 종류는I n 명령 : Q에 n을 삽입한다.D 1 명령 : Q에서 최댓값을 삭제한다.D -1 명령 : Q에서 최솟값을 삭제한다. 의 세 종류로 구성되어 있습니다.시간복잡도 어림하기 자료구조를 사용하여 주어진 명령을 처리하도록 구현하는 문제이므로 시간복잡도 어림은 생략하겠습니다.알고리즘 설계하기 우선순위 큐(Priority Queue)는 데이터를 오름차순 또는 내림차순으로 정렬하여 구성하는 자료구조입니다. 기본적으로 한 방향(오름차순 또는 내림차순)으로 정렬을 하기 때문에, 이번 문제와 같이 최댓값과 최솟값을 모.. 2024. 7. 10. 이전 1 2 3 4 5 다음