[Algorithm] 허수에서 실수까지/Gold524 [C++] 백준 11000번: 강의실 배정 (그리디) https://www.acmicpc.net/problem/11000문제 이해하기 문제의 요구사항은 다음과 같습니다.수업의 시작 시간과 종료 시간이 주어질 때, 사용가능한 최소의 강의실 수를 구하여라.시간복잡도 어림하기브루트 포스 알고리즘 모든 경우의 수 탐색은 강의실의 수가 1개일 때 부터 n개일 때 까지 탐색하면서 확인할 수 있습니다. 하지만 n개의 강의를 2개의 집합으로 나눈다고 할 때, 그 경우의 수는 2^(n - 1) - 1개 이고, n = 200,000이므로 전체 경우의 수는 아주 큰 수가 될 것입니다. 따라서 브루트 포스 알고리즘으로 문제를 해결할 수 없습니다. DP 알고리즘 dp를 사용한다면 dp에는 현재 시간까지 사용가능한 최소 강의실의 수를 담을 수 있습니다. 하지만, 강의 시간의 범위가.. 2024. 5. 17. [C++] 백준 13023번 ABCDE (DFS) https://www.acmicpc.net/problem/13023문제 이해하기 문제의 요구사항은 다음과 같습니다.최소 5명의 사람이 연속적인 친구 관계를 가지는지 구하여라. 문제에서 친구관계는 그래프의 간선으로 치환할 수 있으므로 그래프 문제로 생각하면그래프에 깊이가 5인 경로가 존재하는지 구하여라.로 요약할 수 있습니다.시간복잡도 어림하기DFS 알고리즘 그래프의 깊이를 구해야하는 문제이므로 DFS 알고리즘을 사용할 수 있습니다. 이 문제에서는 그래프를 인접 리스트를 통해 구현할 수 있어 DFS 알고리즘의 시간복잡도는 O(N + M)입니다. 문제에서 N과 M은 모두 2000이므로 DFS 알고리즘은 4000의 시간복잡도를 가집니다. 이를 모든 노드에 대해 반복하면 2000 x 4000 = 8,000,0.. 2024. 5. 16. [C++] 16928번: 뱀과 사다리 게임 (BFS) https://www.acmicpc.net/problem/16928문제 이해하기 문제의 요구사항은 다음과 같습니다.1번부터 100까지 있는 게임판에서, 다른 칸으로 이동하는 뱀과 사다리가 주어질 때, 100번칸에 도달하기 위해 굴려야하는 주사위 횟수의 최솟값을 구하여라.시간복잡도 어림하기BFS 알고리즘 가중치가 같은(이동할 때는 모두 주사위 한 번) 최단거리를 묻는 문제이므로 BFS를 사용할 수 있습니다. BFS를 사용했을 때, 게임판을 탐색하는 횟수는 최대 100번이지만, 게임판에 있는 뱀과 사다리에 따라 100번보다 더 많이 탐색할 가능성도 있습니다. 하지만, 게임판의 크기가 100으로 아주 작고, 다시 되돌아간 경우에도 반드시 재탐색을 하는 것이 아니므로 제한 시간내에 문제를 해결할 수 있을 것입.. 2024. 5. 15. [C++] 백준 2589번: 보물섬 (BFS) https://www.acmicpc.net/problem/2589문제 이해하기 문제의 요구사항은 다음과 같습니다.보물이 두 지점 간 최단거리 중 가장 긴 시간이 걸리는 지점에 위치할 때, 보물이 있는 위치로 이동하는 최단 시간을 구하여라.시간복잡도 어림하기BFS 알고리즘 가중치가 같은 최단거리를 구해야하는 문제이므로 BFS와 DFS를 사용할 수 있습니다. 문제에서는 보물이 묻힌 위치가 두 지점 간 최단거리 중 가장 긴 시간이 걸리는 지점에 위치한다고 했으므로, 모든 지점에 대해 이동할 수 있는 모든 위치에 대한 최단거리를 구해야합니다. 따라서 시간복잡도는 모든 위치 탐색 X BFS 또는 DFS의 시간복잡도 = O(n^4)가 될 것입니다. 문제에서 n의 최댓값은 50이고 50^4는 6백만 정도이므로 제한 .. 2024. 5. 14. [C++] 백준 1068번: 트리 (DFS) https://www.acmicpc.net/problem/1068문제 이해하기 문제의 요구사항은 다음과 같습니다.트리에서 삭제할 노드가 주어질 때, 해당 노드를 삭제한 후 남아있는 리프 노드의 개수를 구하여라.시간복잡도 어림하기 구현에 가까운 문제이므로 미리 시간복잡도를 어림하는 것이 큰 의미가 없는 문제입니다. 따라서 이 단계는 생략하겠습니다.알고리즘 설계하기 코드의 전체 흐름은 다음과 같이 설계할 수 있습니다.1. 트리 구성2. 노드 삭제3. 리프 노드 카운트 가장 먼저 트리를 구성해봅시다. 이 문제에서는 오로지 '삭제' 연산만 진행하면 됩니다. 삭제 연산은 해당 노드의 부모 노드와의 연결을 끊는 것과 같습니다. 따라서 어떤 노드의 부모 노드 정보만 있으면 삭제 연산을 진행할 수 있습니다. 트리를.. 2024. 5. 13. [C++] 백준 2470: 두 용액 (두 포인터) https://www.acmicpc.net/problem/2470문제 이해하기 문제의 요구사항은 다음과 같습니다.두 용액을 조합하여 특성합이 0에 가장 가까운 조합을 구하여라.시간복잡도 어림하기브루트 포스 알고리즘 한 용액에 대해 가능한 모든 특성합을 구하는 알고리즘은 O(n^2)의 시간복잡도를 가집니다. 문제에서 n의 최댓값은 100,000이므로 10,000,000,000의 시간복잡도를 가집니다. 이는 제한 시간 내에 문제를 해결하기 어려운 수치입니다. DP 알고리즘 DP 알고리즘을 사용해도 합이 0에 가까운 두 용액을 찾기 위해서는 O(n^2)의 시간복잡도를 가지므로 DP 알고리즘도 사용할 수 없습니다. 이분 탐색, 두 포인터 알고리즘 이 문제는 합이 0에 가까운 두 용액을 구하는 것입니다. 여기서.. 2024. 5. 12. 이전 1 2 3 4 다음