알고리즘

[백준 1967/C++] 트리의 지름

//1967 트리의 지름 #include #include using namespace std; vector tree; vector visited; int leaf_node = 0; int radius = 0; void dfs(int root, int parent, int weight){ if(tree[root].size()==1 && root!=1){ //무방향 그래프 -> 리프노드면 부모 노드 하나만 존재 if(radius < weight){ radius = weight; leaf_node = root; } return; } for(int i = 0 ; i < tree[root].size() ; i++){ if(tree[root][i].first != parent) dfs(tree[root][i].fi..

[백준 5639/C++] 이진 검색 트리

//5639 이진 검색 트리 #include #include using namespace std; vector preorder; void postorder(int idx, int left, int right) { if(left > right){ return; } int node = preorder[idx]; int right_node = right + 1; for(int j = left ; j node){ right_node = j; break; } } postorder(idx+1, idx+1, right_node - 1); postorder(right_node, right_node, right); cout num){ //if(num==-1) break; // 제출시 주석처리 (디버깅용) preorder..

[백준 15681] 트리와 쿼리

//15681 트리와 쿼리 #include #include using namespace std; vector tree; vector visited; vector dp; int nodeCount(int R) { for (int i = 0; i < tree[R].size(); i++) { int new_node = tree[R][i]; if (visited[new_node]) //이미 방문한 정점 continue; visited[new_node] = true; dp[R] += nodeCount(new_node); } return dp[R]; } int main() { ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); int N, R, Q,..

[백준 14503] 로봇청소기

#include #include using namespace std; int ans = 0; int N, M; vector board; int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, -1, 0, 1}; void clean(int r, int c, int d){ if(r = N+1 || c = M+1) return; // 범위 체크 //다음 방향 int ny = r + dy[d]; int nx = c + dx[d]; //네 방향 모두 청소가 되어있음 if(board[r+dy[0]][c+dx[0]] && board[r+dy[1]][c+dx[1]] && board[r+dy[2]][c+dx[2]] && board[r+dy[3]][c+dx[3]]){ //d if(board[r+dy[..

[백준 2011] 암호코드

// 2011 암호코드 #include #include #define SIZE 1000000 using namespace std; int main (){ string code; vector dp(5000, 0); cin >> code; bool avail = true; if(code[0]=='0'){ avail = false; } else dp[0] = 1; for(int i = 1 ; i < code.length() ; i++){ int cur = code[i]-'0'; int pre = code[i-1] - '0'; //dp[1] if(i == 1) { if (pre*10 + cur 불가능한 암호 avail = false; } else dp[i] = 1; // ex) 51, 52 ... } conti..

[백준 12852] 1로 만들기 2

//12852번: 1로 만들기 2 #include #include #include #define SIZE 1000001 using namespace std; int main (){ int X, cur, ans; cin >> X; vector dp(SIZE, 0); vector path(SIZE, -1); queue q; q.push(X); while(!q.empty()){ cur = q.front(); q.pop(); //종료 조건 if(cur==1){ ans = dp[cur]; break; } //연산 1 if(cur % 3 == 0 && !dp[cur/3] ){ dp[cur/3] = dp[cur] + 1; path[cur/3] = cur; q.push(cur/3); } //연산 2 if(cur % 2..