초보개발자

입력: 테스트케이스 T, 정점 수 N, 간선 수 M, M개의 정보 (시작점, 끝점, 가중치) 방향 없음출력: 가중치의 중간값의 최소알고리즘: 최소 신장 트리소스코드 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include using namespace std; vector graph; vector dis; vector visited; int main() { int testcase, n, m, u, v, w; scanf("%d", &testcase); for(int t = 1; t

입력: 노트북이 섞인 날 어제 노트북을 구입한 사람의 수 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, 만드려는 수 K, 동전 N개의 가치출력: K를 만들 수 있는 경우의 수알고리즘: 동적 계획법소스코드 #define _CRT_SECURE_NO_WARNINGS #include #include #include using namespace std; vector dp(10001, 0); vector coins(100); int main() { //freopen("input.txt", "r", stdin); int N, K; scanf("%d%d", &N, &K); for (int i = 0; i < N; i++) scanf("%d", &coins[i]); sort(coins.begin(), coins.begin() + N); for (int i = 0; i < N; i++) { dp[co..

입력: 서쪽 다리 갯수 n, 동쪽 다리 갯수 m (n ≤ m)출력: 다리가 겹쳐지지 않고 다리를 놓을 수 있는 경우의 수(int 수준)알고리즘: 동적 계획법소스코드 #define _CRT_SECURE_NO_WARNINGS #include #include using namespace std; vector combine(30, vector(30, -1)); int nck(int m, int n) { if (n == 1) return m; if (m == 1) return 1; if (m == n) return 1; if (combine[m][n] != -1) return combine[m][n]; return combine[m][n] = nck(m - 1, n) + nck(m - 1, n - 1); } in..

입력: 배열의 가로 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..