포도밭 개발자

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..

https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net 플로이드 와샬 알고리즘을 이용해 풀이했습니다. C++ 소스 코드 #include #define MAX 801 using namespace std; int n,e,dist[MAX][MAX]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> e; int a,b,c,..

https://www.acmicpc.net/problem/2589 2589번: 보물섬 보물섬 지도를 발견한 후크 선장은 보물을 찾아나섰다. 보물섬 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 각 칸은 육지(L)나 바다(W)로 표시되어 있다. 이 지도에서 www.acmicpc.net BFS로 풀이하였습니다. 모든 L 에서 인접한 L까지의 거리를 비교한 최대값이 답이 됩니다. C++ 소스 코드 #include #include #include #include #define MAX 51 using namespace std; int n,m,ans; const int dx[] = {0,0,-1,1},dy[]={-1,1,0,0}; string map[MAX]; bool visit[MAX][..

https://programmers.co.kr/learn/courses/30/lessons/68936 코딩테스트 연습 - 쿼드압축 후 개수 세기 [[1,1,0,0],[1,0,0,0],[1,0,0,1],[1,1,1,1]] [4,9] [[1,1,1,1,1,1,1,1],[0,1,1,1,1,1,1,1],[0,0,0,0,1,1,1,1],[0,1,0,0,1,1,1,1],[0,0,0,0,0,0,1,1],[0,0,0,0,0,0,0,1],[0,0,0,0,1,0,0,1],[0,0,0,0,1,1,1,1]] [10,15] programmers.co.kr 분할정복 기법을 이용해 풀이하였습니다. C++ 소스 코드 #include #include using namespace std; vector answer; void divide..

https://www.acmicpc.net/problem/10451 10451번: 순열 사이클 1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\ 3 www.acmicpc.net DFS를 이용해 풀이하였습니다 C++ 소스 코드 #include #define MAX 1001 using namespace std; int adj[MAX]; bool visit[MAX]; void dfs(int x){ if(visit[x]) return; // 이미 방문한 정점을 또 방문하면 cycle visit[x] = t..

https://www.acmicpc.net/problem/17837 17837번: 새로운 게임 2 재현이는 주변을 살펴보던 중 체스판과 말을 이용해서 새로운 게임을 만들기로 했다. 새로운 게임은 크기가 N×N인 체스판에서 진행되고, 사용하는 말의 개수는 K개이다. 말은 원판모양이고, 하� www.acmicpc.net C++ 소스 코드 #include #include #include #include using namespace std; int n,k; struct pos{ int x,y,d; }; vector v; const int dx[]={0,0,-1,1}, dy[]={1,-1,0,0}; int a[13][13]; string mp[13][13] = {""}; bool move(int x, int y,..

https://www.acmicpc.net/problem/1389 1389번: 케빈 베이컨의 6단계 법칙 첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻�� www.acmicpc.net 전체 유저의 수가 최대 100이기 때문에 O(N^3)인 플로이드 와샬 알고리즘을 이용해 풀이했습니다. C++ 소스 코드 #include #define INF 500000 using namespace std; int d[101][101]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); cout.ti..

https://www.acmicpc.net/problem/12869 12869번: 뮤탈리스크 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)이다. 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)이다. www.acmicpc.net 메모이제이션을 활용해 DP로 풀이하였습니다. C++ 소스 코드 #include #include using namespace std; int cache[61][61][61]; int dp(int s1, int s2, int s3){ if (s1 > n; fill(&cache[0][0][0], &cache[60][60][60]+1,-1); int scv[3] = {0,0,0}; for(int i=0;i> sc..