알고리즘 모음(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1719 1719번: 택배첫째 줄에 두 수 n과 m이 빈 칸을 사이에 두고 순서대로 주어진다. n은 집하장의 개수로 200이하의 자연수, m은 집하장간 경로의 개수로 10000이하의 자연수이다. 이어서 한 줄에 하나씩 집하장간 경www.acmicpc.net다익스트라를 이용해 푸는 문제입니다. 거리를 출력하는 것이 아닌, 최단거리를 가기 위해서 처음으로 가는 정점을 출력하면 됩니다. 즉, 기본적인 다익스트라를 사용하면서, 거리가 바뀔 때마다 가는 정점을 같이 바꿔줘야한다는 의미입니다. 먼저 1~N까지 모두 출력해야 하기에 반복문을 통해 i번 정점을 기준으로 탐색을 시작할 수 있도록 해줍니다. 정점에서 탐색을 시작했다면 이제 갈 수 ..

문제 링크입니다. https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 까다로운 그리디 문제였습니다. 보석을 어떤 순으로 담아야 되는지 생각했어야 했습니다. N과 K의 범위가 300,000 이기에 가방 한개마다 모든 보석을 확인하기에는 문제가 있습니다. 따라서 우선순위 큐를 사용했습니다. 우선순위 큐를 사용하면 조건에 따라 가장 작은 or 가장 큰 값이 루트에 있기에 이를 가져오기만 하면 ..

문제 링크입니다. 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/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 위상정렬과 우선순위 큐를 이용한 문제입니다. 문제의 조건이 있습니다. 1. N개의 문제는 모두 풀어야 한다. 2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다. 3. 가능하면 쉬운 문제부터 풀어야 한다. 3-1. 문제 난이도는 문제 번호 순이다. 여기서 조건 2에 해당하지 않는 문제들이 있습니다. ..

문제 링크입니다. https://www.acmicpc.net/problem/11286 11286번: 절댓값 힙 첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0 www.acmicpc.net pair를 사용해, 우선순위 큐를 사용하면 되는 문제였습니다. abs(x)는 x의 절댓값을 나타냅니다. pair의 first에는 절댓값을, second에는 x를 저장해, 오름차순으로 정렬합니다. 나머지는 조건에 따라서 출력해줍니다. #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #in..