Hello coding

백준 DP모음

1947번 [선물 전달]완전 순열: 일렬로 배열한 대상들의 위치를 재조정했을 때, 모든 대상이 자기 위치에 있지 않도록 하는 배열 방법 점화식: D[n] = (n-1)(D[n-1] + D[n-2])ll dp[1000001];int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n; cin >> n; dp[1] = 0; dp[2] = 1; for (ll i = 3; i  13398번 [연속합 2]수가 하나 제거되면 2부분으로 나뉜다. ㅡ> 2개의 dp배열 사용int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; vector v; int ..

백준 1256번 [사전]

dp로 조합 다루기int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll n, m, k; string ans = ""; cin >> n >> m >> k; ll dp[201][201]; for (int i = 0; i 1000000000) dp[i][j] = 1000000001; } } if (dp[n + m][n] = 0; i--) { if (cnt == 0) { ans += "a"; } else if (i+1 == cnt) { ans += "z"; cnt--; } else if (dp[i][cnt] >= k) { ans += "a"; } else { ans += "z"; ..

백준 1722번 [순열의 순서]

팩토리얼을 이용한 순열 구현next_permutation보다 시간복잡도 빠름ll fac[21];vector v;bool visited[21] = { 0, };int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, q; cin >> n >> q; fac[0] = 1; for (int i = 1; i > k; for (int i = n-1; i >= 0; i--) { ll cnt = 1; for (int j = 1; j > x; v.push_back(x); for (int j = 1; j

백준 2343번 [기타 레슨]

이진 탐색, 매개 변수 탐색이진 탐색의 start, end, mid을 배열의 값에만 국한시키지 말고 문제와 관련된 매개 변수로 해본다.ㅡ> 정렬된 배열이 아니더라도 이진 탐색 사용 가능N, M int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n, m; cin >> n >> m; vector v; int end = 0; int start = 0; for (int i = 0; i > x; v.push_back(x); end += x; start = max(start, x); } while (start mid) { count++; sum = 0; } sum += v[i]; } if (count > m)..

인접 리스트를 미리 받아놓지 않고 재귀 함수를 돌리면서 다음 깊이를 찾아가는 DFS같은 조건으로 크기를 키워갈 때 사용 고려int n;bool isPrime(int num) { for (int i = 2; i > n; DFS(2, 1); DFS(3, 1); DFS(5, 1); DFS(7, 1); return 0;}

병합 정렬(분할 정복) nlogn 정렬을 sort()가 아닌 직접 구현해야 할 때(과정을 봐야할 때) ㅡ> 병합 정렬vector v;vector tmp;ll res = 0;void merge_sort(int s, int e) { if (e - s tmp[index2]) { v[k] = tmp[index2]; k++; index2++; res += (index2 - k); } else { v[k] = tmp[index1]; k++; index1++; } } while (index1 > n; v = vector(n, 0); tmp = vector(n, 0); for (int i = 0; i > x; v[i] = x; } merge_sort(0, n - 1); cout

우선순위 큐 규칙에 따른 정렬 ㅡ> 우선순위 큐struct compare { bool operator()(int x, int y) { int x_abs = abs(x); int y_abs = abs(y); if (x_abs == y_abs) return x > y; else return x_abs > y_abs; }};priority_queue, compare> pq;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int n; cin >> n; for (int i = 0; i > x; if (x == 0) { if (pq.size() == 0) cout

deque + 슬라이딩 윈도우 일정한 범위 유지 ㅡ> 슬라이딩 윈도우범위의 앞뒤에서 사건 발생 ㅡ> dequeint main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); deque mydeque; ll n, l; cin >> n >> l; for (ll i = 1; i > x; ll s = mydeque.size(); if (s == 0) { mydeque.push_back({ i, x }); } else { for (ll j = s-1; j >= 0; j--) { if (mydeque[j].second

투 포인터, 이분탐색 시간복잡도 n ㅡ> logn 만들 때 고려시작 포인트 잡기포인터 이동규칙 세우기종료 조건 만들기포인터가 경계값에 있을 때 따지기#include #define ll long long#define pii pair#define pll pair#define tpi tuple#define tpl tuple#define all(x) x.begin(), x.end()#define INF 0x3f3f3f3f#define MOD 100000007using namespace std;int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); vector v; ll n; cin >> n; ll start = 0; ll end = n-1; ll..

구간 합 + 나머지(mod) 배열 + 합 ㅡ> 구간 합 저장나머지 ㅡ> (A + B) % C = ((A%C) + (B%C)) % Cll arr[1000001] = { 0, };ll idx[1001] = { 0, };ll combination(ll x) { if (x == 1) return 1; return (x * (x - 1)) / 2;}int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); ll res = 0; ll n, m; cin >> n >> m; for (ll i = 0; i > x; arr[i + 1] = (arr[i] + x)%m; idx[arr[i + 1]]++; } for (ll i = 1; i 1) { res ..