Hello coding

비트마스킹을 사용한 완전탐색dp[cur][visited]: 현재 도시가 cur, 현재까지 방문한 도시 리스트가 visited일 때 앞으로 남은 모든 도시를 경유하는 게 필요한 최소 비용int cost[16][16] = {0,};int dp[16][1> n; for(int i=0;i> cost[i][j]; } } cout

map bfs + mstint n, m;int parent[11] = { 0, };int big[11] = { 0, };int island[11][11];int visited[11][11] = {0,};vector>v;int minEdge[11][11];int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int idx = 0;int find(int x){ if(parent[x] == x) return x; else return parent[x] = find(parent[x]);}void uni(int x, int y){ int rx = find(x); int ry = find(y); if(rx != ry) { if (big[rx] q; idx++; island..

구간 전체를 한 번에 처리하기 어렵다.최소 높이를 기준으로 좌우로 나눌 수 있다.ㅡ> 분할 정복 시도vector arr;ll sol(int l, int r){ if(l==r) return arr[l]; int mid = (l+r)/2; ll lmax = sol(l,mid); ll rmax = sol(mid+1, r); ll ret = max(lmax, rmax); int b = mid; int e = mid+1; ll y = min(arr[b], arr[e]); ll pmax = 2*y; while(b>l || e arr[e+1]){ b--; } else{ e++; } y=min(y, min(arr[b], arr[e])); pmax = max(pmax, (e-b+1)*y); } ret =..

Segment Tree 사용 조건1. 연산이 결합 법칙을 만족2. 연산에 항등원이 존재 - 리프노드에 원본 데이터를 입력vector tree;int main() { int n; cin >> n; int height = 0; while((int)pow(2, height) > tree[i]; } build(treeSize-1); //update(node + leftNodeIndex - 1, val); //query(start + leftNodeIndex - 1, end + leftNodeIndex - 1) return 0;} - build, query, update 함수를 연산에 따라 작성//구간합void build(int i){ while(i>1){ tree[i/2] += tree[i]; i--; }}..

위상정렬로 최장 경로를 구한 후 해당 경로 찾기그래프에서 역추적 + DP로 경로 구하기vector world[10001];vector reverse_world[10001];bool visited[10001] = {false,};int idx[10001] = {0,};int dis[10001] = {0,};int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n, m; cin >> n >> m; for(int i=0;i> u >> v >> w; world[u].push_back({v, w}); reverse_world[v].push_back({u, w}); idx[v]++; } int start, end; cin >>..

사이클 없는 그래프에서 선후관계를 따질 때 ㅡ> 위상정렬(먼저 해야한다, 의존 관계, 선행 작업...)vector v[501];int idx[501] = {0,};int work_time[501] = {0,};int final_time[501] = {0,};int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int n; cin >> n; for(int i=1;i> t; work_time[i] = t; int b = 0; while(b!=-1){ cin >> b; if(b!=-1) { v[b].push_back(i); idx[i]++; } } } queue q; for(int i=1;i

같은 집합은 union으로 묶고 find로 같은 집합인지 확인int parent[51] = { 0, };int big[51] = { 0, };vector party[51];int find(int x){ if(parent[x] == x) return x; else return parent[x] = find(parent[x]);}void uni(int x, int y){ int rx = find(x); int ry = find(y); if(rx!=ry){ if(big[rx] > n >> m; for(int i=0;i> know_person; int x, y; if(know_person!=0) cin >> x; for(int i=0;i> y; uni(x, y); x = y; } for(int i=0;i>..

그래프 데이터가 없는 bfs 문제. 문제 흐름에 따라 그래프를 역으로 그리는 방식.가능한 모든 상태를 탐색해야 할 때 ㅡ> 그래프 탐색 고려int sender[6] = {0, 0, 1, 1, 2, 2};int receiver[6] = {1, 2, 0, 2, 0, 1};bool visited[201][201];bool answer[201];int bottle[3];void bfs(){ queue q; q.push({0, 0}); visited[0][0] = true; answer[bottle[2]] = true; while(!q.empty()){ pii now = q.front(); q.pop(); int a = now.first; int b = now.second; int c = bottle[2..

중복된 문자에 대한 조합 다루기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 += ..

조합인데 수가 너무 클 때 ㅡ> DP말고 그냥 확률 연산int main() { ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); vector v; int m, k; int hap = 0; cin >> m; for(int i=0;i> x; v.push_back(x); hap += x; } cin >> k; double prob = 1; double ans = 0; if(m==1 || k==1) { cout = k) { for(int j=0;j