[Algorithm] 허수에서 실수까지/Gold331 [C++] 2623번: 음악 프로그램 (위상 정렬) https://www.acmicpc.net/problem/2623문제 이해하기 문제의 요구사항은 다음과 같습니다.각 부분 순서를 보고, 이에 맞는 전체 순서를 구하여라. 시간복잡도 어림하기위상 정렬 알고리즘 여러 노드들의 순서 정보를 보고 전체 순서를 결정하는 것은 위상 정렬 알고리즘으로 해결할 수 있습니다. 위상 정렬 알고리즘의 시간복잡도는 O(V + E)입니다. 이 문제에서 N의 최대값은 1000이므로 제한 시간 내에 문제를 해결하기 충분한 수치입니다.알고리즘 설계하기 위상 정렬은 Khan 의 알고리즘을 사용하여 다음과 같이 구현합니다./*L : 정렬된 원소들을 담을 리스트*//*S : incoming edge가 없는 노드의 집합*/while S가 비어있지 않을 때 동작 S에서 노드 n 삭제 .. 2024. 8. 16. [C++] 백준 7579번: 앱 (DP, 배낭 문제) https://www.acmicpc.net/problem/7579문제 이해하기 문제의 요구사항은 다음과 같습니다.필요한 메모리를 확보하기 위해 비활성화 해야 하는 앱의 최소 비용을 구하여라.시간복잡도 어림하기브루트 포스 알고리즘 모든 앱은 활성화, 비활성화의 두 상태를 가질 수 있습니다. 문제에서 주어지는 앱의 최대 개수는 100개이므로 전체 경우의 수는 2^100 입니다. 이는 제한 시간 내에 모든 경우를 확인하기 어려우므로 브루트 포스 알고리즘을 사용할 수 없습니다. DP 알고리즘 제한된 용량 안에서 최대의 가치를 구하는 문제는 배낭 문제입니다. 이 문제도 이와 비슷한 성격을 띠고 있습니다. 배낭 문제를 해결하기 위해서는 DP 알고리즘을 사용하고, 시간 복잡도는 O(N^2)입니다. 문제에서 N의 최.. 2024. 8. 14. [C++] 백준 4179번: 불! (BFS) https://www.acmicpc.net/problem/4179문제 이해하기 문제의 요구사항은 다음과 같습니다.불을 피해 지훈이가 미로를 탈출할 수 있는 최소 시간을 구하여라.시간복잡도 어림하기BFS 알고리즘 최소 시간으로 미로를 탈출하는 것은 가중치가 같은 최단거리 문제이므로 BFS를 사용할 수 있습니다. BFS 알고리즘은 O(N^2)의 시간복잡도를 가지고, 이번 문제의 N의 최댓값은 1000이므로 BFS 한번은 1,000,000의 시간복잡도를 가집니다. 이번 문제에서는 지훈이 뿐만 아니라 불도 최단거리로 이동하므로 BFS를 한번 더 사용합니다. 하지만, BFS를 더 사용한다고 해도 2,000,000 이므로 제한 시간 내에 문제를 해결하기 충분합니다.알고리즘 설계하기 불과 지훈이를 미로에 퍼트려야 하.. 2024. 8. 13. [C++] 백준 1600번: 말이 되고픈 원숭이 (BFS) https://www.acmicpc.net/problem/1600문제 이해하기문제의 요구사항은 다음과 같습니다.원숭이가 말처럼 이동할 수 있는 횟수가 정해져 있을 때, 원숭이 동작수의 최솟값을 구하여라.시간복잡도 어림하기BFS 알고리즘 가중치가 같은 최단거리 문제이므로 BFS를 사용할 수 있습니다. 또한, 이번 문제는 시작 위치가 하나로 고정되어 있으므로 BFS를 한 번만 시행해도 됩니다. 일반적인 BFS 알고리즘의 시간복잡도는 O(N^2)입니다. 이번 문제에서는 가로와 세로의 길이가 주어지므로 200 x 200 = 40,000입니다. 이 문제에서는 고려해야할 것이 하나 더 있는데, 바로 말처럼 이동할 수 있는 횟수입니다. 각 위치마다 말처럼 이동할 수 있는 횟수를 저장한다고 해봅시다. 말처럼 이동 가능.. 2024. 8. 12. [C++] 백준 1937번: 욕심쟁이 판다 (DP, DPS) https://www.acmicpc.net/problem/1937문제 이해하기 문제의 요구사항은 다음과 같습니다.판다가 항상 더 많은 대나무가 있는 위치로 이동할 때, 판다가 이동할 수 있는 최대 칸 수를 구하여라.시간복잡도 어림하기DFS 알고리즘 시작 위치에서 최대로 이동가능한 위치를 찾는 알고리즘으로 DFS를 사용할 수 있습니다. DFS는 O(N^2)의 시간복잡도가 필요합니다. 이 문제에서 시작 위치는 정해진 것이 없으므로 모든 위치에 대해 DFS를 사용해야합니다. 즉, 시간복잡도가 O(N^4)가 됩니다. 문제에서 N의 최댓값은 500이므로 이는 제한 시간 내에 해결하기 어려운 시간복잡도 입니다. 따라서 다른 알고리즘을 사용해야 합니다. DP 알고리즘 위 DFS 알고리즘의 동작을 다시 생각해 보면 중.. 2024. 8. 9. [C++] 백준 11779번 : 최소비용 구하기2 (다익스트라) https://www.acmicpc.net/problem/11779문제 이해하기 문제의 요구사항은 다음과 같습니다.출발 도시에서 도착 도시까지의 최소 비용과 경로 및 거쳐가는 도시의 수를 구하여라.시간복잡도 어림하기다익스트라 알고리즘 한 노드를 시작으로 다른 모든 노드까지의 최소 비용을 구하는 문제이므로 다익스트라 알고리즘을 사용할 수 있습니다. 우선순위 큐를 사용하는 다익스트라 알고리즘은 O(E log E)의 시간복잡도를 가집니다. 문제에서 E의 최댓값은 100,000이므로 제한 시간 내에 문제를 해결하기 충분한 수치입니다.알고리즘 설계하기 다익스트라 알고리즘은 다음과 같은 순서로 동작합니다.1. 시작 노드 방문 및 최단거리를 0으로 초기화합니다.2. 우선순위 큐가 빌 때까지 아래 동작을 반복합니다.3.. 2024. 8. 8. 이전 1 2 3 4 5 6 다음