알고리즘 (82) 썸네일형 리스트형 [백준] 1766번 문제집 C++ 문제풀이 https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제 풀이 전형적인 위상정렬 문제다. 위상정렬이란 순서가 정해져있는 작업을 차례로 수행할 때, 순서를 결정하는 알고리즘이다. 여기서는 고려해야하는 순서는 2가지였다. 첫 번째는 '먼저 푸는 것이 좋은 문제'의 경우에는 먼저 풀어야한다. 두 번째는 문제집 번호가 낮은 번호부터 큰 번호 순서로 진행되어야 한다. 이 두가지를 고려해 queue에 진입차수가 0인 문제가 하나.. [백준] 1202번 보석 도둑 C++ 문제풀이 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 문제 풀이 가방에 최대 1개의 보석밖에 못 넣기 때문에 그리디로 풀면 된다. 가방에 넣을 수 있는 보석들을 다 Priority_queue에 넣어놓고, 그리고 가방에 담을 수 있는 무게를 넘어가면 Priority queue에서의 Top에 있는 걸 sum에 합치고 다음 가방으로 넘어가는 형식으로 해결한다. 소스 코드 #include #inc.. [백준] 7579번 앱 C++ 문제풀이 https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 문제 풀이 맨 처음에는 그리디로 그냥 cost가 작을수록, cost가 같다면 메모리가 클수록 앞으로 배치되게 정렬한 후 풀었더니 틀렸다. 원래 0-1 Knapsack 문제는 그리디로 풀면 최적해를 보장하지 않는다. 따라서 dp로 문제를 풀었다. 위의 식 P[i,w] 는 아이템이 i개있고, w까지 한도일 때 최적의 v를 구하는 공식이다. 이 문제에서는 메모리의 경우 10,000,000 이므로 w로 사용하기.. [백준] 2623번 음악프로그램 C++ 문제풀이 https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 문제 풀이 이 문제는 위상 정렬을 이용해 푸는 문제이다. 가수의 순서가 결정되어 있는 상황에서 가수의 순서를 모두 만족하는 출현 순서를 출력해야하기 때문이다. 따라서 진입차수가 0이 되는 가수들부터 먼저 출력을 해주고, 그 가수와 연결된 가수들의 간선을 줄여주면서 queue가 비어질때까지 반복 수행하면 된다. 이 문제의 주의점은 순서를 정하는 것이 불가능한 경우가 존재한다는 것.. [백준] 2252번 줄세우기 C++ 문제풀이 https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 문제 풀이 이 문제는 키의 순서가 정해져있을 때, 차례대로 출력하는 문제이므로 위상 정렬을 이용해야함을 알 수 있다. 1005번 ACM Craft 문제와 유사하지만 여기서는 배열을 출력해야한다는 점만 차이가 있다. https://itcodeheaven.tistory.com/78 [백준] 1005번 ACM Craft C++ 문제풀이 https://www.a.. [백준] 11404번 플로이드 C++ 문제풀이 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 문제 풀이 이 문제는 플로이드 워셜 알고리즘을 통해 두 도시 사이의 최소 비용을 구하는 문제다 플로이드 워셜 알고리즘은 모든 정점들간의 최단 거리를 계산하는 알고리즘으로, 시간복잡도는 O(N^3)이다. i 와 j 두 정점 사이의 거리를 구할 때 k를 중간에 거쳐서 가는 것이 더 짧으면 갱신하면 된다. 소스 코드 #include using namespace std; int dp[101][101] =.. [백준] 1005번 ACM Craft C++ 문제풀이 https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 문제 풀이 위상정렬이라는 걸 처음 알게 되었다. 위상정렬이란 순서가 정해져있는 작업을 차례로 수행할 때, 순서를 결정하는 알고리즘이다. 예를 들어 위의 문제에서 2번 건물을 건설하기 위해서는 1번을 건설해야하고, 4번 건물을 건설하기 위해서는 1,2,3번 건물이 세워줘야하는 것 처럼 말이다. 위상정렬 알고리즘은 비순환 방향 그래프에서 사용할 수 있다. 즉 끝이 존재해야 위상 정렬을 사용할 수.. [백준] 2239번 스도쿠 C++ 문제풀이 https://www.acmicpc.net/problem/2239 2239번: 스도쿠 스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다 www.acmicpc.net 문제 풀이 그냥 백트래킹을 이용한 완전 탐색을 해주는 문제였다. 확인해야할 3가지는 (1) 행 (2) 열 (3) 박스 를 고려해서 숫자를 넣을 수 있는지 확인하면 된다. 소스 코드 #include #include using namespace std; bool row[10][10] = { false }; bool col[10][10] = { false }; bool box[10][10] = {.. 이전 1 2 3 4 5 ··· 11 다음
