초보개발자

입력: 테스트케이스 T, 가로 N, 세로 M, 배추가 심어져있는 개수 K, K개의 좌표 (x, y)출력: 최소 배추흰지렁이 마릿수알고리즘: DFS소스코드 import java.util.*; public class Main { static int n, m; static int[][] mov = new int[][] {{-1, 0},{0,-1},{1, 0},{0, 1}}; static int[][] map; public static void dfs(int x, int y){ map[x][y] = 0; for(int i=0; i= n || mY = m) continue; if(map[mX][mY] != 1) continue; dfs(mX, mY); } } public static void ..

입력: 가로 R, 세로 C, 로봇청소기의 위치(x, y), 방향(0:북쪽, 1: 동쪽, 2: 남쪽, 3: 서쪽) RxC 지도(1: 벽, 0: 청소)출력: 로봇이 청소하는 공간의 개수소스코드 #include using namespace std; bool clean[50][50] = { false, }; int map[50][50]; int mov[4][2] = { {0, -1}, {-1, 0}, {0, 1},{1, 0} }; void dfs(int x, int y, int& rooms, int dir, const int r, const int c) { if(!clean[x][y]) rooms++; clean[x][y] = true; int mX, mY, see = dir; for (int i = 0; i ..

입력: 일수 N, N개의 걸리는 일과 금액출력: 최대 금액알고리즘: 동적계획법, Knapsack 알고리즘소스코드 #define _CRT_SECURE_NO_WARNINGS #include #include #include #define plan pair #define mp(x, y) make_pair(x, y) using namespace std; vector cache; vector schedule; int benefit(int idx, int n) { if (idx >= n) return 0; int& ret = cache[idx]; if (ret != -1) return ret; ret = max(benefit(idx + 1, n), ret); if (idx + schedule[idx].first

입력: 노트북이 섞인 날 어제 노트북을 구입한 사람의 수 N(1

입력: 직원 수 N, 일의 개수 M, N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호출력: 강호네 회사에서 할 수 있는 일의 개수알고리즘: 이분매칭소스코드 #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; vector priority; vector visited; vector task, tasks; bool dfs(int here) { if (visited[here]) return 0; visited[here] = true; int sz = priority[here].size(); for (int i = 0; i < sz; i++) { int there = priority[here][i];..

입력: 가로 n출력: 2x1, 2x2 타일을 이용하여 2xn 타일을 나타낼 수 있는 경우의 수알고리즘: 동적 계획법, 피보나치 수열소스코드 #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; int main() { int n; scanf("%d", &n); vector tile(n + 1); tile[1] = 1; tile[2] = 3; for (int i = 3; i

입력: 표현하려는 숫자 N(1≤N≤200), 양수의 개수 K(1≤K≤200)출력: 자연수 N을 K개의 양수로 표현할 수 있는 방법의 수(숫자 순서가 다르면 다른 경우)알고리즘: 동적 계획법소스코드 #define _CRT_SECRUE_NO_WARNINGS #include #include #define MOD 1000*1000*1000 using namespace std; vector cache; int sumDecomp(int n, int k) { if (n < 0 || k

입력: 배열의 가로 n, 세로 m, 배열의 값 n*m, 쿼리 수 k, 두 개의 좌표 (i, j), (x, y)출력: (i, j) ~ (x, y) 부터 더한 값알고리즘: 세그먼트 트리, 동적 계획법소스코드 #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; int init(int start, int end, int node, vector &arr, vector &tree) { if (start == end) return tree[node] = arr[start]; else return tree[node] = init(start, (start + end) / 2, node * 2, arr, tree) + init((s..

입력: 정수 N (1≤N= n) return; vector visit(n, false); for (int i = 0; i = 0) visit[y - (row - i)] = true; } for (int i = 0; i < n; i++) { if (row == n - 1 && !visit[i]) cnt++; else if(!visit[i]){ queen.push_back(i); CountQueen(n, row + 1, cnt); queen.pop_back(); } } } 퀸은 가로, 세로, 대각..

입력: 세로 r 가로 c r*c로 된 대문자 집합출력: 상하좌우로 움직이면서 방문했던 알파벳은 방문하지 않았을 때 최대의 길이알고리즘: DFS, 백트래킹소스코드 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include using namespace std; void DFS(int, int, int, int&); int r, c; vector board; vector alphabet(26, false); int main() { scanf("%d%d", &r, &c); board = vector(r); for (int i = 0; i > board[i]; int max = 0; DFS(0, 0, 1, max); prin..