본문 바로가기

분류 전체보기130

[C++] 백준 1865번: 웜홀 (벨만 포드) https://www.acmicpc.net/problem/1865문제 이해하기 문제의 요구사항은 다음과 같습니다.도로와 웜홀의 정보가 주어질 때, 줄어든 시간으로 출발 위치에 도착할 수 있는지 그 여부를 구하여라.시간복잡도 어림하기벨만 포드(Bellman Ford) 알고리즘 이번 문제에서 웜홀은 그 가중치만큼 시간을 줄이는 역할을 합니다. 즉, 음의 가중치를 가지는 간선입니다. 문제에서 줄어든 시간으로 출발 위치에 도착 가능한지를 물어보았습니다. 줄어든 시간으로 출발 위치에 도착 가능하다는 말은 음의 가중치로 인해 최단거리가 무한히 갱신된다는 것을 의미하고 이는 그래프에 음의 사이클이 존재한다는 것을 의미합니다. 그래프에 음의 사이클이 존재하는지 확인하는데 적합한 알고리즘은 벨만 포드 알고리즘입니다. 기.. 2024. 8. 20.
[C++] 백준 4386번: 별자리 만들기 (최소 신장 트리) https://www.acmicpc.net/problem/4386문제 이해하기 문제의 요구사항은 다음과 같습니다.모든 별을 잇는 최소 비용을 구하여라.시간복잡도 어림하기최소 신장 트리(Minimum Spanning Tree) 모든 노드(별)을 연결하는 최소 비용을 구하는 문제이므로 최소 비용으로 신장 트리를 구성하는 것과 같습니다. 최소 신장 트리를 구하는 알고리즘으로 Kruskal 알고리즘과 Prim 알고리즘 두 종류가 있습니다. Kruskal 알고리즘의 시간 복잡도는 O(eloge)이고, Prim 알고리즘의 시간 복잡도는 O(n^2) 입니다. 이번 문제에서 n의 최댓값은 100이고, e의 최댓값은 100 x 100 = 10000 이므로 둘 중 어느 알고리즘을 사용해도 해결할 수 있는 문제입니다. 이번.. 2024. 8. 19.
[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.

티스토리툴바