알고리즘 문제풀이/백준134 [백준 9372] 상근이의 여행 www.acmicpc.net/problem/9372 9372번: 상근이의 여행 첫 번째 줄에는 테스트 케이스의 수 T(T ≤ 100)가 주어지고, 각 테스트 케이스마다 다음과 같은 정보가 주어진다. 첫 번째 줄에는 국가의 수 N(2 ≤ N ≤ 1 000)과 비행기의 종류 M(1 ≤ M ≤ 10 000) 가 www.acmicpc.net 문제에서 요구하는 바만 파악하면 매우 쉬운 문제이다. 목적지를 모두 돌 수 있는 최소 비행기 수를 필요로 하므로 MST이다. 경로별 가중치가 존재하지 않고 최소 비행기 수만 요구함 + 무조건 연결그래프라는 조건이 있으므로 노드가 N개인 MST는 무조건 경로가 N-1개다. 따라서 그냥 N-1만 출력하면 된다. #include using namespace std; int t, .. 2021. 1. 25. [백준 1080] 행렬 www.acmicpc.net/problem/1080 1080번: 행렬 첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다. www.acmicpc.net 그리디 알고리즘이라는데 그리디는 알다가도 모르겠다.. 연산 방식은 1. 두 개의 행렬이 같으면 1 다르면 0으로 표시 2. 1의 행렬에 대해 3*3 뒤집기 연산을 수행 2-1. 연산을 수행할 때 마다 모든 행렬 값이 0이 되는지 확인 2-2. 모든 행렬이 0이라면 연산 횟수 리턴 2-3. 그렇지 않다면 다음 연산 수행 먼저 두 행렬을 비교하여 check배열을 만들고 다른 원소 수를 센다. for (int i = 0; i < .. 2021. 1. 24. [백준 1520] 내리막 길 www.acmicpc.net/problem/1520 #include using namespace std; int a[500][500]; int dp[500][500]; int n, m; int dr[4] = {0, 0, -1, 1}; int dc[4] = {1, -1, 0, 0}; int dfs(int row, int col) { if (row == 0 && col == 0) { return 1; } if (dp[row][col] == -1) { dp[row][col] = 0; for (int i = 0; i = 0 && nc >= 0 && nr < n && nc < m) { if (a[ro.. 2021. 1. 23. [백준 1655] 가운데를 말해요 www.acmicpc.net/problem/1655 1655번: 가운데를 말해요 첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -1 www.acmicpc.net 중간값 찾기 알고리즘을 사용한다. maxHeap과 minHeap이 필요해서 우선순위큐를 사용한다. 두 힙은 다음과 같은 규칙을 따른다. 1. maxHeap은 minHeap의 크기와 같거나 1만큼 크다. 2. maxHeap의 탑은 minHeap의 탑보다 작거나 같다. 만약 이를 만족시키지 못하면 둘을 바꾼다. 이렇게 하면 maxHeap의 탑이 항상 중간값임을 알 수 있다. 신기방기.. 예제에 적용.. 2021. 1. 14. 이전 1 ··· 5 6 7 8 9 10 11 ··· 34 다음