문제 링크: https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 최소 스패닝 트리, 크루스칼 알고리즘 크루스칼 알고리즘을 사용해서 최소 비용으로 모든 노드를 연결하면 됩니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 7..

문제 링크: https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 다익스트라 알고리즘 다익스트라 알고리즘으로 출발점에서 도착점까지 최단 경로를 구하면 됩니다. #include #include #include #include #include #include using namespace std; const int MAX_N = 125; const int dx[4] = { 0, 0, 1, -1 }; const int dy[4] = { 1..

문제 링크: https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 다익스트라 알고리즘 다익스트라 알고리즘을 사용해서 출발지부터 도착지까지의 최단거리를 구하면 됩니다. #include #include #include #include #include #include using namespace std; const int MAX_N = 50000; int N, M; vector adj[MAX_N + 1]; int d[MAX_N + 1]; int dijkstra(i..

문제 링크: https://www.acmicpc.net/problem/14442 14442번: 벽 부수고 이동하기 2 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 1,000), K(1 ≤ K ≤ 10)이 주어진다. 다음 N개의 줄에 M개의 숫자로 맵이 주어진다. (1, 1)과 (N, M)은 항상 0이라고 가정하자. www.acmicpc.net BFS 알고리즘 BFS를 사용하여 최단거리를 찾을 때, 현재까지 몇 개의 벽을 부쉈는지를 체크하기 위해서 3차원 visited 배열을 다음과 같이 선언합니다. visited[N][M][K] : (N,M) 좌표를 K개의 벽을 부수고 방문했을 때의 최단 거리 BFS의 큐에는 (좌표, 현재까지 몇 개의 벽을 부쉈는지)에 대한 정보를 담고, 다음과 같은 조..

문제 링크: https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 장소의 수 N (2 ≤ N ≤ 500)과 도로의 수 M (1 ≤ M ≤ 104)가 주어진다. 장소는 0부터 N-1번까지 번호가 매겨져 있 www.acmicpc.net 다익스트라 알고리즘 다익스트라로 최단 거리를 갱신하고, 가능한 모든 최단 경로 삭제 후 다시 다익스트라로 최단거리를 갱신하면 됩니다. 최단 경로를 삭제하기 위해 각 정점에 도달하기 전의 정점을 기록할 수 있는 자료구조가 필요합니다. 이때 가능한 최단거리가 여러 개 있을 수 있으므로 vector 타입의 배열을 사용하여 이전 정점들을 저장해야 합니다. 제거할..

문제 링크: https://www.acmicpc.net/problem/1774 1774번: 우주신과의 교감 (1,1) (3,1) (2,3) (4,3) 이렇게 우주신들과 황선자씨의 좌표가 주어졌고 1번하고 4번이 연결되어 있다. 그렇다면 1번하고 2번을 잇는 통로를 만들고 3번하고 4번을 잇는 통로를 만들면 신들과 선자씨끼 www.acmicpc.net 최소 스패닝 트리, 크루스칼 알고리즘 모든 서로 다른 두 정점 사이에 거리를 구해서 간선에 추가하고 크루스칼 알고리즘을 이용하여 최소 스패닝 트리를 찾으면 됩니다. [주의할 점] 1. 이미 연결된 통로를 입력받을 때, 중복된 간선이 들어올 수 있습니다. 예를 들어, 1-2와 2-1은 동일한 간선을 나타냅니다. 이 경우를 고려하지 않으면 현재까지 최소 스패닝 ..

문제 링크: https://www.acmicpc.net/problem/2056 2056번: 작업 수행해야 할 작업 N개 (3 ≤ N ≤ 10000)가 있다. 각각의 작업마다 걸리는 시간(1 ≤ 시간 ≤ 100)이 정수로 주어진다. 몇몇 작업들 사이에는 선행 관계라는 게 있어서, 어떤 작업을 수행하기 위해 www.acmicpc.net 다이나믹 프로그래밍(DP), 위상정렬 알고리즘 작업에는 순서가 있으므로 위상정렬을 사용해야 합니다. 또한, 모든 작업을 완료하기 위한 최소 시간을 구하기 위해 DP를 활용해야 합니다. DP의 정의는 아래와 같습니다: DP[i] : i번째 작업이 완료되는 데 필요한 최소 시간 위상 정렬을 수행하며 현재 작업에 연결된 다음 작업들의 최소 완료 시간을 갱신해 나갑니다. 현재 작업을..

문제 링크: https://www.acmicpc.net/problem/2283 2283번: 구간 자르기 1번째 줄에 정수 N, K(1 ≤ N ≤ 1,000, 1 ≤ K ≤ 1,000,000,000)가 주어진다. 2~N+1번째 줄에 각 구간의 왼쪽 끝점과 오른쪽 끝점의 위치가 주어진다. 양 끝점의 위치는 0 이상 1,000,000 이하의 정수이다. www.acmicpc.net 투포인터, 누적합 알고리즘 먼저 모든 구간을 살펴봐야 하고 각 구간에 존재하는 막대기의 총길이가 K가 되도록 하는 조건이 있기 때문에 이 문제는 투포인터와 누적합을 사용해서 해결할 수 있습니다. 원래 모든 구간을 살펴보기 위해선 O(구간의길이^2)의 시간복잡도가 걸리지만, 각 구간에 존재하는 막대기의 총길이가 K가 되도록 하는 조건은..