개인공부용123 프로그래밍 블로그

1. 풀이 방식( DP, 재귀, 반복문) - 재귀 풀이 방식(search) : 첫번째 아이템부터 하나씩 선택해나가면 최대값을 찾음 메모제이션을 활용하여 이미 찾은 값은 또 찾지 않도록 처리 - 반복문 방식 (search2) : 가능한 모든 무게에 item을 하나씩 추가 하여 가장 큰 가중치를 찾아나감 2. 유의 사항 : 없음 출처: https://survivalking.tistory.com/75 [생존몬의 프로그래밍 블로그] #include #include #include using namespace std; #define MAX 100000 int N, K; int W[101]; int V[101]; int dp[101][MAX + 1]; int dp2[MAX + 1]; int search(int po..

1. 풀이 방식 - 가능한 모든 수열의 갯수를 찾아야 함 - 수열의 오름차순으로 나와야함 - 완전탐색을 하되 이미 pick한 값은 제외 하여 탐색, pick한값들은 배열에 임시 저장해둠 - 고를수있는 숫자를 전부 고르면 임시저장해둔 값을 출력 - 탐색은 1부터 진행하므로 오름차순 정렬을 보장 2. 유의 사항 : pick 한 후 다시 자기 step에 왔을때 pick 한 숫자를 풀어줘야함 #include #include using namespace std; #define MAX 1000000 bool check[9]; int arr[9]; int n,m; void suyeol(int cur, int st) { // 결과 값 출력 if (cur == m) { for (int i = 0; i < m; ++i) ..

1. 풀이 방식 : 단순 재귀 함수로 구현 2. 유의 사항 : 0! = 1 #include #include using namespace std; int recur(int n) { if (n == 0) return 1; return n * recur(n - 1); } int main() { int N; cin >> N; printf("%d\n", recur(N)); return 0; }

BOJ 2751 정렬문제 1. 풀이 방식 : Merge Sort로 NlogN 타임에 구현 - 직접 머지 소스 구현 - stl을 사용한 구현 2. 유의 사항 : C++ 입출력을 사용시 TimeOut이 나옴 * Merge 코드 구현 #include #include using namespace std; #define MAX 1000000 int sort[MAX]; // 오름차순 정렬 // st ~ mid, mid + 1 ~ en void merge(int* list, int start, int mid, int end) { int i = start; int j = mid + 1; int k = start; int l; while (i

#include using namespace std; void init(char* str, bool* chk) { for (int i = 0; i > T; while (T--) { init(str,chk); prev_c = 0; cin >> str; for (int i = 0; str[i] != 0; ++i) { c = str[i]; if (c != prev_c && chk[c - 'a']) { --cnt; break; } chk[c - 'a'] = true; prev_c = c; } ++cnt; } cout

어렵게 생각하지않고 손으로 계산하듯이 풀면 풀립니다 이때 nCr = nCn-r 이 될수있음을 이용해서 n-r > n >> k; if (n == 0 && k == 0) break; if (n - k < k) k = n - k; ll Answer = 1; for (ll i = 1; i

해당문제는 이항계수문제로 n과 k가주어졌을경우 nCk % 10007을 한 결과를 구하는 문제입니다. nCk = n-1Ck-1 + n-1Ck로 나타낼수있습니다. 이를 DP를 이용해서 풀면 cache[1001][1001] 배열에 nCk의 값을 저장해두고 해당 값이 필요할경우 배열에 있는 값을 이용하면 문제를 더욱빠르게 풀수있습니다. #include #include using namespace std; //이항계수 // 점화식 nCk = n-1Ck-1 + n-1Ck typedef long long ll; const ll divideNum = 10007; ll cache[1001][1001]; ll Answer(int N, int K) { if (N == K || K == 0) return 1; ll& ret ..

이 문제는 입력이 약간 까다로운 문제인것같습니다. 입력을 deque에 입력한 후에는 chk라는 flag를 두어서 true이면 앞에서 연산을하고 false이면 뒤에서 연산을 하는 방식으로 해결했고 출력시 chk변수를 확인해서 true이면 앞에서 출력 false이면 뒤에서 출력해서 결과를 냈습니다. 주의해야할 점은 입력이 0일경우 주의해서 풀면 될것같습니다. (입력이 0일경우 D함수가 포함되있지않다면 출력은 []가 나와야합니다.) #include #include #include using namespace std; int main() { std::ios::sync_with_stdio(false); bool chk; // true이면 앞에서 false이면 뒤에서 bool ok; int C, n; cin >> ..

환형큐를 이용해서 문제 M 번째에 있는 수를 찾으면 쉽게 풀리는 문제입니다. #include #include using namespace std; void Josepus(int N, int M) { queue q; for (int i = 1; i M; Josepus(N, M); return 0; }

기본적인 DFS BFS 구현입니다. #include #include #include using namespace std; bool arr[1001][1001]; // 2차원 배열 bool check_arr[1001]; int N, M, V; // 정점 간선 시작점 void BFS(int start) { // BFS호출순서 queue q; q.push(start); check_arr[start] = true; cout v1 >> v2; arr[v1][v2] = true; arr[v2][v1] = true; } DFS(V); cout