짱아의 개발 기록장

전형적인 백트래킹 문제여서 간단하게 코테 보기 전에 연습하기 좋은 문제인 것 같다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 // n과m (7) #include #include #include using namespace std; int n, m; vector v; vector ans; void choose(int num) { if(num==m){ for(int i=0; i

플로이드 와샬로도 충분히 풀 수 있는 문제지만,,, 그냥 다익스트라를 n번 돌리는 방식으로 구현했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 // 서강그라운드 #include #include #include #include using namespace std; int n, m, r, a, b, c; int item[102] = {0, }; vector v[102]; int ..

어떤 알고리즘으로 문제를 풀지를 고민하는 데 엄청 시간이 오래 걸렸다. 다른 분들의 풀이를 참고한 결과 bfs와 tree를 사용해서 푸는 문제였고 이전에 반드시 방문해야하는 방 => before 이전에 반드시 방문해야하는 방을 방문하지 않아 잠시 보류를 하는 방 => after 을 표시하여 적절하게 구현해주는 문제였다. 문제를 풀어도 30번 테케가 계속 틀려서 찾아보니 0번방은 반드시 이전에 방문해야하는 방이 존재하면 안된다는 조건을 걸어주어야 했다. 0번방이 start지점이기 때문에 before[0]!=0이라면 false를 리턴해주었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 ..

R연산을 할 때 그냥 reverse를 써서 구현하다가... 시간초과가 났다. 시간초과나는 것이 당연한게 최악의 경우를 생각해보면, n이 10만개+ R연산이 10만개 => 10만*10만이 되어서 터진다... 그래서 투포인터로 구현해야한다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 9..

문자열처리문제였다. 단순히, 문제에 나와있는 고려사항들을 다 처리해주면 쉽게 구할 수 있다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 // 단어 뒤집기 2 #include #include using namespace std; string s; int main() { getline(cin, s); string ans = ""; string tmp = ""; bool check = false; for(int i=0; i0){ reverse(tmp.begin(), tmp.end()); ans += tmp; tmp = ..

너무 전형적인 유니온 파인드 문제이다. 바로 사이클이 형성되는 순간 exit(0)해서 프로그램을 빠져나오도록 구현했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 // 사이클게임 #include using namespace std; int n, m, a, b; int connect[500001] = {0, }; int find(int a){ if(a==connect[a]){ return a; } return connect[a] = find(connect[a]); } int main() { cin>>n>>m; for(int i=0; ia>>b; int from = find(..

트리를 DFS와 DP를 활용해서 푸는 문제이다. 트리를 DFS로 구현하되, 시간 절약을 위해서 DP를 사용한 형태이다. 가장 핵심 아이디어는, 내가 얼리어답터이면 -> 자식이 얼리어답터이던 아니던 상관없다. 내가 얼리어답터가 아니면 -> 자식은 반드시! 얼리어답터이어야 한다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364// SNS#include #include #include using namespace std; const int MAX = 1000001;int n, u, v;vector connect[MAX]; // 친구 관계vecto..

가장 최소의 수를 구하는 그리디 문제였다. dp를 사용해서 푸는 방법도 있지만, 직관적으로 판단한다면 더 쉽게 풀 수 있다. 5로 나누어떨어지지 않는다면, 2를 계속 빼는 식으로 계산했다. 최종적으로, 5로 나누어 떨어지지 않아서 while문을 빠져 나왔다면 1) 2로 나누어떨어지는 경우이거나, 2) 아예 2와 5로 떨어지지 않는 수이다. ex) 3, 1... 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 // 거스름돈 #include #include using namespace std; int n; vector v; int dp[100001] = {0, }; int main() { cin>>n; int c..