본문 바로가기

Algorithm

 (2139)
(C++) - 백준(BOJ)코딩 2468번 : 안전 영역 답 www.acmicpc.net/problem/2468 2468번: 안전 영역 재난방재청에서는 많은 비가 내리는 장마철에 대비해서 다음과 같은 일을 계획하고 있다. 먼저 어떤 지역의 높이 정보를 파악한다. 그 다음에 그 지역에 많은 비가 내렸을 때 물에 잠기지 않는 www.acmicpc.net 비의 높이를 1씩 증가시키면서 bfs로 안전영역의 개수를 센 후 가장 큰 값이 답인 brute force 문제였습니다. 풀이방법 1. 잠기는 물의 높이를 0부터 100까지라고 설정한 후 정한 물의 높이보다 높은 지역만 안전영역으로 지정하고 이를 값 1이라고 가정합니다. 2. 안전영역이 있다면 이와 인접한 안전영역을 check하기 위해 모든 안전영역을 검사하며 check가 안되어 있다면 bfs를 시행합니다. 따라서 bf..
(C++) - 백준(BOJ) 10830번 : 행렬 제곱 답 문제링크 : https://www.acmicpc.net/problem/10830 행렬 제곱을 구현해보는 문제였습니다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include using namespace std;long long a[6][6],ans[6][6],c[6][6],n,b;void cal(long long a[6][6], long long b[6][6]){ for (int i = 1; i 0) { if (b % 2 == 1)//지수가 홀수면 { cal(ans, a); } cal(a, a); b /= 2; } for (int i = 1; i
(C++) - 백준(BOJ) 2740번 : 행렬 곱셈 답 https://www.acmicpc.net/problem/2740 2740번: 행렬 곱셈 첫째 줄에 행렬 A의 크기 N 과 M이 주어진다. 둘째 줄부터 N개의 줄에 행렬 A의 원소 M개가 순서대로 주어진다. 그 다음 줄에는 행렬 B의 크기 M과 K가 주어진다. 이어서 M개의 줄에 행렬 B의 원소 K개 www.acmicpc.net 간단한 행렬 곱셈 문제였습니다. Code #include using namespace std; int a[101][101], b[101][101],c[101][101],n,m,k; int main() { cin >> n >> m; for (int i = 1; i a[i][j]; cin >> m >> k; for (int i = 1; i b[i][j]; for (int i = 1; i
(C++) - 백준(BOJ) 2738번 : 행렬 덧셈 #include using namespace std; int a[101][101], b[101][101],n,m; int main() { cin >> n >> m; for (int i = 1; i a[i][j]; for (int i = 1; i b[i][j]; for (int i = 1; i
(C++) - 백준(BOJ) 1629번 : 곱셈 답 https://www.acmicpc.net/problem/1629 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 풀이방법 a^b%c를 구하는 문제다. a를 b번 곱하게 되면 O(b)의 시간이 거리게 되지만 a ^ b/2 * a ^ b/2 로 곱하게 된다면 시간은 O(2 * logN)의 시간이 걸린다. 따라서 이 문제는 분할 정복 문제라고 볼 수 있다. Code #include using namespace std; long long a, b, c; long long cal(long long a, long long b, long long c) { if (b == 0) { re..
(C++) - 백준(BOJ) 7562번 : 나이트의 이동 답 https://www.acmicpc.net/problem/7562 간단한 BFS문제였습니다. 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657#include #include using namespace std; int a[301][301], c[301][301], d[301][301];int cnt, t, u, uf, v, vf, I;int dx[] = { -1,-2,-2,-1,1,2,2,1 }, dy[] = { -2,-1,1,2,2,1,-1,-2 }; void BFS(int i, int j){ queue q; q.push(make_pair(i, j)); c[i][j..
(C++) - 백준(BOJ)코딩 1012번 : 유기농 배추 답 www.acmicpc.net/problem/1012 1012번: 유기농 배추 차세대 영농인 한나는 강원도 고랭지에서 유기농 배추를 재배하기로 하였다. 농약을 쓰지 않고 배추를 재배하려면 배추를 해충으로부터 보호하는 것이 중요하기 때문에, 한나는 해충 방지에 www.acmicpc.net 전형적인 bfs문제였습니다. 풀이방법 1. 배추가 있는 곳(밭이 1인 곳)마다 bfs를 호출합니다. 2. 인접한 배추를 bfs로 check했기 때문에 이 bfs 호출 개수가 즉 배추흰지렁이의 놓아야할 개수입니다. Code #include using namespace std; int testCase, n, m, k; int field[51][51]; int check[51][51]; int dx[4] = {0,0,-1,1};..
(C++) - 백준(BOJ) 10865번:친구 친구 답 12345678910111213141516#include using namespace std;int N, M,u,v,a[100001];int main() { cin >> N >> M; for (int i = 1; i > u >> v; a[u]++; a[v]++; } for (int i = 1; i

티스토리툴바