[Algorithm] 허수에서 실수까지/Gold524 [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. [C++] 백준 20055번: 컨베이어 벨트 위의 로봇 (구현) https://www.acmicpc.net/problem/20055문제 이해하기 문제의 요구사항은 다음과 같습니다.주어진 순서대로 컨베이어 벨트와 로봇이 이동할 때, 컨베이어 벨트의 동작이 멈추는 단계를 구하여라.시간복잡도 어림하기 미리 시간복잡도를 어림하는 것이 큰 의미가 없는 구현 문제이므로 생략하겠습니다.알고리즘 설계하기 문제에서 주어진 동작을 살펴봅시다.1. 벨트가 로봇과 함께 한 칸 회전한다.2. 가장 먼저 올라간 로봇부터 한 칸 앞으로 이동할 수 있다면 이동한다. - 로봇이 이동하기 위해서는 이동할 칸에 다른 로봇이 없고, 칸의 내구도가 1이상이어야 한다.3. 올리는 위치의 칸의 내구도가 1이상이라면 로봇을 올린다.4. 내구도가 0인 칸의 개수가 K개 이상이라면 동작을 종료한다. 그렇지 않으면.. 2024. 5. 24. [C++] 백준 2023번: 신기한 소수 (소수) https://www.acmicpc.net/problem/2023문제 이해하기 문제의 요구사항은 다음과 같습니다.어떤 수의 왼쪽부터 1자리 2자리 ... N자리 수 모두 소수인 어떤 수를 신기한 소수라고 할 때, N자리 신기한 소수를 구하여라.시간복잡도 어림하기브루트 포스 알고리즘 8자리 수는 99,999,999 까지로 1억 미만의 수입니다. 만약, 1과 1억 사이의 모든 소수를 구해 각 수가 신기한 소수인지 판단할 수 있습니다. 1과 1억사이의 소수를 제한 시간 내에 구하기 위해서는 단순 소수 구하기가 아닌 에라토스테네스의 채 알고리즘을 사용하는 것이 빠릅니다. 하지만, 문제의 메모리 제한이 4MB이기 때문에 int형 배열에 최대 4 x 2^20 / 4 = 2^20개의 숫자를 담을 수 있습니다. 2^2.. 2024. 5. 23. [C++] 백준 2011번: 암호 코드 (DP) https://www.acmicpc.net/problem/2011문제 이해하기 문제의 요구사항은 다음과 같습니다.주어진 암호에 대해 암호를 알파벳으로 변환할 수 있는 경우의 수를 구하여라.시간복잡도 어림하기브루트포스 알고리즘 가장 첫 글자를 제외하면 각 자리의 숫자는 한 자리를 알파벳으로 해석하는 경우와 두 자리를 알파벳으로 해석하는 경우, 두 가지로 해석할 수 있습니다.(숫자가 0인 경우는 일단 고려하지 않았습니다.) 주어진 암호의 최대 길이는 5000이고, 암호의 해석으로 나올 수 있는 경우의 수는 2^5000가지 입니다. 이는 제한 시간 내에 문제를 해결하기 어려운 수치이므로 브루트 포스 알고리즘을 사용할 수 없습니다. DP 알고리즘 dp 배열에 현재 인덱스까지 해석할 수 있는 암호의 경우의 수를 .. 2024. 5. 22. [C++] 백준 14719번: 빗물 (구현) https://www.acmicpc.net/problem/14719문제 이해하기 문제의 요구사항은 다음과 같습니다.지형의 형태가 주어질때, 고인 빗물의 총량을 구하여라.시간복잡도 어림하기 미리 시간복잡도를 어림하는 것이 큰 의미가 없는 구현 문제이므로 생략하겠습니다.알고리즘 설계하기 먼저, 빗물이 어떤 경우에 고이게 되는지 생각해봅시다. 예시를 보면 알다시피, 빗물이 고이기 위해서는 좌우가 블럭으로 둘러쌓여야 하고, 그 블럭 중 낮은 높이의 블럭까지 빗물이 차오릅니다. 이를 다른 관점으로 보면 특정 높이에서 블럭으로 둘러쌓인 공간의 수를 구하고, 이를 가능한 모든 높이에 대해 반복하여 빗물이 어느 위치에 고이는지 판단할 수 있습니다. 그림으로 보면 다음과 같습니다. 탐색은 왼쪽에서 오른쪽으로 진행되고.. 2024. 5. 21. [C++] 백준 9205번: 맥주 마시면서 걸어가기 (BFS) https://www.acmicpc.net/problem/9205문제 이해하기 문제에서 맥주 한 병당 50m를 이동하고 맥주는 최대 20개까지 가질 수 있으므로한 번에 최대 1000미터를 이동할 수 있을 때, 상근이네 집에서 페스티벌에 도달할 수 있는지 구하여라. 를 묻는 문제입니다.시간복잡도 어림하기BFS 알고리즘 이 문제는 도착 지점에 도달 가능한지 확인하는 문제입니다. 이때, 편의점에서 맥주를 구매하여 맥주 20병을 채울 수 있으므로 시작 지점에서 바로 목표지점에 도달하거나, 편의점을 경유하여 목표지점에 도달하는지를 확인하는 문제입니다. 시작지점에서 각 편의점으로 이동할 때에는 가중치가 동일하므로 BFS를 통해 탐색을 진행할 수 있습니다. 매 테스트 케이스마다 주어지는 편의점의 수는 최대 100개이.. 2024. 5. 20. 이전 1 2 3 4 다음
