포도밭 개발자

https://www.acmicpc.net/problem/2638 2638번: 치즈 첫째 줄에는 모눈종이의 크기를 나타내는 두 개의 정수 N, M (5≤N, M≤100)이 주어진다. 그 다음 N개의 줄에는 모눈종이 위의 격자에 치즈가 있는 부분은 1로 표시되고, 치즈가 없는 부분은 0으로 표 www.acmicpc.net DFS를 응용해서 풀이하였습니다. 치즈와 외부 공기의 접촉면을 구해야하기 때문에 맵의 네 모서리에서 BFS를 수행했습니다. 1. 현재 위치 (x,y)의 인접 위치(nx,ny)가 1이라면 2로 변경 2.현재 위치 (x,y)의 인접 위치(nx,ny)가 2이라면(다른 위치의 공기와 맞닿아 있고, 현재 위치와도 맞닿는 부분) 다음 루프에서 사라짐 3. 현재 위치 (x,y)의 인접 위치(nx,ny..

https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 오랜만에 머리쓰는 문제를 풀었습니다.. 처음엔 BFS로 접근해서 답은 맞췄지만 시간복잡도를 줄이기 위해 다른 방법을 더 고민해보았습니다. 먼저 DP로 접근해보았는데 4방향 모두 이동 가능해서인지 원하는 답이 안나왔습니다 .ㅠㅠ 그 후 Dijkstra 로 접근해서 풀이한 결과, 시간 복잡도를 일반 BFS의 절반으로 줄일 수 있었습니다. 소스코드는 BFS , Dijkstra 버전 둘..

https://www.acmicpc.net/problem/1065 1065번: 한수 어떤 양의 정수 X의 각 자리가 등차수열을 이룬다면, 그 수를 한수라고 한다. 등차수열은 연속된 두 개의 수의 차이가 일정한 수열을 말한다. N이 주어졌을 때, 1보다 크거나 같고, N보다 작거나 www.acmicpc.net 각 자리수가 등차수열인 수의 갯수를 구하는 문제입니다. N의 범위가 1000이하이기에 한자리,두자리,세자리 수가 등차수열인지 체크해야합니다. (1000은 각 자리수가 등차수열이 아님) - 한자리, 두자리 수의 각 자리수는 항상 등차수열을 이룹니다. 따라서, N이 100 미만이라면 답은 N이 됩니다. - N이 100이상인 경우, '10의자리수 - 1의 자리수' 와 '100의자리수 - 10의자리수' 를 ..

https://www.acmicpc.net/problem/14676 14676번: 영우는 사기꾼? 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 건물 종류의 개수 N, 건물 사이 관계의 개수 M, 영우의 게임 정보의 개수 K가 주어진다.(1 ≤ N, M, K ≤ 100,000) 다음 줄부터 M줄에 걸쳐 www.acmicpc.net 위상정렬 알고리즘을 응용해서 풀이했습니다. C++ 소스 코드 #include #include #define MAX 100001 using namespace std; int n,m,k; vector adj[MAX]; int inDegree[MAX], construct[MAX]; int main(){ ios_base::sync_with_stdio(0); cin.tie(..

https://www.acmicpc.net/problem/1325 n >> m; int u,v; for(int i=0;i> u >> v; adj[v].push_back(u); } for(int i=1;i tmax){ ans.clear(); ans.push_back(i); tmax = cnt; }else if (cnt == tmax){ ans.push_back(i); } } for(int i=0;i

https://www.acmicpc.net/problem/11728 11728번: 배열 합치기 첫째 줄에 배열 A의 크기 N, 배열 B의 크기 M이 주어진다. (1 ≤ N, M ≤ 1,000,000) 둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거 www.acmicpc.net 병합정렬 (Merge Sort) 알고리즘을 이용해 O(N+M) 에 풀이하였습니다 ! C++ 소스 코드 #include #define MAX 1000001 using namespace std; int a[MAX], b[MAX]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n,m; ..

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 우선순위 큐와 위상정렬을 이용해 풀이했습니다. C++ 소스 코드 #include #include #include #include #define MAX 32001 using namespace std; vector adj[MAX]; int inDegree[MAX]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout...

https://www.acmicpc.net/problem/2636 2636번: 치즈 아래 과 같이 정사각형 칸들로 이루어진 사각형 모양의 판이 있고, 그 위에 얇은 치즈(회색으로 표시된 부분)가 놓여 있다. 판의 가장자리(에서 네모 칸에 X친 부분)에는 치즈가 놓 www.acmicpc.net 맵의 가장자리에서 DFS를 수행하여 풀이했습니다. 이를 통해 치즈 내부에 있는 빈 공간은 그대로 두고, 가장자리와 맞닿아 있는 치즈의 갯수를 알 수 있습니다. C++ 소스 코드 #include #include #define MAX 101 using namespace std; const int dx[]= {0,0,-1,1}, dy[]= {-1,1,0,0}; int maps[MAX][MAX]; bool visit[MAX..