전자공학 및 알고리즘

문제 링크입니다. https://www.acmicpc.net/problem/1162 1162번: 도로포장 첫 줄에는 도시의 수 N(1 ≤ N ≤ 10,000)과 도로의 수 M(1 ≤ M ≤ 50,000)과 포장할 도로의 수 K(1 ≤ K ≤ 20)가 공백으로 구분되어 주어진다. M개의 줄에 대해 도로가 연결하는 두 도시와 도로를 통과하 www.acmicpc.net DP와 다익스트라 알고리즘을 사용하는 문제입니다. N의 값이 10000이하이기에 다익스트라를 구현하면 시간 초과가 걸립니다. 따라서 DP의 개념을 이용해 다익스트라를 구현해야 합니다. 먼저 도로 개통을 할 수 있기에 X번 도시를 도착한 경우를 나눠줘야합니다. 즉 X번 도시를 도착했을 때, 도로를 몇번 개통했는지에 따라 다르게 계산해야 된다는 의..

문제 링크입니다. https://www.acmicpc.net/problem/2665 2665번: 미로만들기 첫 줄에는 한 줄에 들어가는 방의 수 n(1 ≤ n ≤ 50)이 주어지고, 다음 n개의 줄의 각 줄마다 0과 1이 이루어진 길이가 n인 수열이 주어진다. 0은 검은 방, 1은 흰 방을 나타낸다. www.acmicpc.net 다익스트라와 bfs를 이용해 푸는 문제입니다. 해당 문제에서 생각해야 할 것이 있습니다. 먼저 하나의 구역으로 묶여있는 흰 방을 방문할 때 바꾼 검은 방의 갯수를 바꿔줘야 하나? 입니다. 당연하게도 바꿀 필요가 없습니다. 같은 구역의 흰 방이라면 무조건 같은 갯수의 검은 방 입니다. 따라서 바꾼 검은 방의 갯수가 바뀌는 경우는 흰 방 -> 검은 방 * X -> 흰 방의 경우입니다..

문제 링크입니다. https://www.acmicpc.net/problem/5972 5972번: 택배 배송 농부 현서는 농부 찬홍이에게 택배를 배달해줘야 합니다. 그리고 지금, 갈 준비를 하고 있습니다. 평화롭게 가려면 가는 길에 만나는 모든 소들에게 맛있는 여물을 줘야 합니다. 물론 현서는 www.acmicpc.net 다익스트라를 이용해 푸는 문제입니다. 정점 1번에서 시작해서 N번까지 가는게 필요한 최소 비용을 구하는 문제입니다. 간선의 가중치가 1만 있는 것이 아니기에 다익스트라 알고리즘을 통해서 최단 거리를 구해야하는 문제였습니다. 다익스트라 알고리즘이 궁금하다면 해당 링크를 통해 확인하시면 됩니다. https://junseok.tistory.com/187 백준 1753 - 최단경로(C++) 문제..

문제 링크입니다. https://www.acmicpc.net/problem/10282 10282번: 해킹 최흉최악의 해커 yum3이 네트워크 시설의 한 컴퓨터를 해킹했다! 이제 서로에 의존하는 컴퓨터들은 점차 하나둘 전염되기 시작한다. 어떤 컴퓨터 a가 다른 컴퓨터 b에 의존한다면, b가 감염되면 www.acmicpc.net 다익스트라를 사용하는 문제입니다. 다익스트라 알고리즘을 통해 C번에서 탐색을 시작하면 되는 문제입니다. void Dijstra(int x){ Distance[x] = 0; q.push({0,x}); while(!q.empty()){ int X = q.top().second; long long cost = q.top().first; q.pop(); for(int i = 0; i < l..

문제 링크입니다. https://www.acmicpc.net/problem/14938 14938번: 서강그라운드 예은이는 요즘 가장 인기가 있는 게임 서강그라운드를 즐기고 있다. 서강그라운드는 여러 지역중 하나의 지역에 낙하산을 타고 낙하하여, 그 지역에 떨어져 있는 아이템들을 이용해 서바이벌을 www.acmicpc.net 다익스트라 알고리즘을 사용하는 문제입니다. X번 지점에서 시작했을 때, 수색 범위 내에 얻을 수 있는 아이템의 최댓값을 구하는 문제입니다. 저는 1 ~ N번까지 각각의 그래프를 확인한 뒤, 해당 그래프에서 얻을 수 있는 아이템의 값을 구하고 값들을 전부 확인하게습니다. 다음 그림을 통해 확인해보겠습니다. 위 그림과 같은 방식으로 아이템의 최댓값을 구하면 됩니다. 자세한 것은 코드를 참..

문제 링크입니다. https://www.acmicpc.net/problem/11779 11779번: 최소비용 구하기 2 첫째 줄에 도시의 개수 n(1≤n≤1,000)이 주어지고 둘째 줄에는 버스의 개수 m(1≤m≤100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스 www.acmicpc.net 다익스트라 알고리즘을 사용하는 문제입니다. https://junseok.tistory.com/188 백준 1916 - 최소비용 구하기(C++) 문제 링크입니다. https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(..

문제 링크입니다. https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net 다익스트라 알고리즘을 사용해 푸는 문제입니다. K번 학생이 X번 정점을 왕복할 때의 최단 시간을 구하는 문제입니다. 1 ~ N번 학생의 최단 시간 중에서 최댓값을 구하면 됩니다. 이때 주어진 간선은 단방향이니, 한쪽 방향으로만 저장해야 합니다. 왕복 값을 구해야하지만, 1 ~ N번점부터 X번 점까지 각각 값을 구하기에는 복잡해집니다. 따라서 X번 점..

문제 링크입니다. https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 다익스트라를 여러번 사용하면 되는 문제입니다. 다익스트라를 여러번 사용해야 되는 문제입니다. 다익스트라 알고리즘을 모르신다면 https://junseok.tistory.com/187 를 참고해주세요 문제에서 주어진 두 정점을 무조건 지났을 때의 최솟값을 구하는 문제입니다. 이 두점을 First, Second로 정하겠습니다. 1번 정점에..

문제 링크입니다. https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 다익스트라 알고리즘을 이용하면 쉽게 풀 수 있는 문제였습니다. 다익스트라 알고리즘을 통해 시작점에서 출발하여 끝점까지의 최소 비용을 구하는 문제였습니다. https://junseok.tistory.com/187 백준 1753 - 최단경로(C++) 문제 링크입니다. https://www.acmicpc.net/problem/1753 1753번: 최단..

문제 링크입니다. https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1 ≤ V ≤ 20,000, 1 ≤ E ≤ 300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1 ≤ K ≤ V)가 www.acmicpc.net 다익스트라 알고리즘의 기본 문제입니다. 1. 다익스트라 알고리즘이란? - 다익스트라 알고리즘은 그래프에서 최소 비용을 구해야 하는 경우 사용되는 알고리즘입니다. 최소 비용 중에서도, 주어진 두 노드(시작 노드, 도착 노드) 사이의 최소 비용인 경로를 찾을 때 사용됩니다. 2. 동작 원리 먼저 1차원 배열을 통해 X번 노드에서의 최소 값을 저장..