나 요리학원 출신임

X에서 출발해 X로 돌아올 수 있는지 없는지 판단하는 문제다Cycle이 있으면 안되는 문제다.하지만 양방향 간선끼리의 Cycle은 방향을 알아서 지정하면 되므로 문제가 안된다..! 따라서 양방향인 간선들은 무시하고 단방향인 간선들로 그래프를 그린다그리고 Cycle을 찾으면 된다! Cycle을 찾는 함수를 사용해도 괜찮고 플로이드를 써도 괜찮다! 소스코드(Cycle detect)12345678910111213141516171819202122232425262728293031323334353637383940414243#include #include #include using namespace std;int n, arr[111][111], check[111];vector Graph;bool isCycle(int..

더 게임 오브 데.. 스.. 어렵다...K개 간선을 지나서 A->B로 갈 수 있다면 death 아니면 life다.생각이 안나서 폭풍도움을 받고 A^k을 하고 A[i][j]가 1이라면i->j라는 사실을 알았따... 생각해보니까 이산수학에서 transitive closure로 나온 것 같다.길이가 n인 path가 있으려면 A^n해서 확인했었다...!잘 기억해둬야겠다.. 행렬곱 n^3 * K(1,000,000) 이니까 정직하게 곱하면 시간안에 못푼다..!그래서 A^k를 log만에 구하는 방법으로 구현해야한다! 하지만 내 소스는 결국 틀렸다 ㅎㅎ..60..%..백준의 코드를 보며 공..부..하고.. 풀었다..!코드 깨끗하게 잘짜는 연습 해야겠다 ㅎㅎ 소스코드123456789101112131415161718192..

방학에 못풀어서 넘어간 문제다다익스트라로 풀면 되는데 K개의 도로를 포장한다는게 굉장히 걸린다 다익스트라를 돌리면서 dp를 사용하여 풀 수 있다.d[here][cnt] 테이블을 잡고 here까지 오는데 cnt개의 도로를 포장했을 때로 생각하면 된다 기존 다익스트라 +만약 cnt d[here][cnt] 라면 도로를 포장해준다 소스코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859#include #include #include #include #include using namespace std;int n, m, k;vector Graph;int d[10010][..

영우는 바쁘다. 기숙사 청소를 해야하는지 알려줘야 한다BFS 그냥 돌리면 시간초과가 난다..!그냥 돌리면 방문한 곳을 다음에 다시 또 방문하게된다! 방법은 바로 이전에 방문한 곳을 체크해 두고 방문 안했을 경우에만 큐에 넣는다! 소스코드1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162#include #include #include #include using namespace std;int arr[333][333];bool check[333][333][2];int n, m, k, t;int dx[8] = { -1,-2,-2,-1,1,2,2,1 };in..

시작점에서 끝점까지 가는데 가장 긴 경로를 출력하고 그때 지나가는 길의 수출력하는 문제다..! 가장 긴 경로 구하는건 쉬웠는데 지나온 길 찾는게 어려워따 ㅎㅎ백준의 도움을 받아따 ㅎㅎ 문제는 위상정렬을 이용해서 풀었다! 위상정렬로 가장 긴 경로는 d[next] = max(d[next] , d[here]+cost)로 구할 수 있다 그리고 지나온 경로는 역으로 그래프를 만들어서 방문한 점중에 가장 긴 경로와 지나온 거리가 같다면 카운트를 올리는 식으로 했다! DAG에서 가장 긴 경로 구하는 문제로 기억해둬야지 ㅎㅎ 소스코드123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657..

정점 N개, 간선 N-1개 트리가 주어지고 루트를 알려준다.그리고 루트에서 리프노드로 가면 탈출 가능할 때리프노드에 탈출을 막는 사람을 몇명 둬야하는지 찾는 문제이다. 탈출을 막는 사람과 탈출 하려는 사람의 속도는 같다. 처음에 시도한 방법은 dfs를 돌려서 리프노드에 도착했을 때 루트와 가장 가까운 두갈래 이상의 길을 찾아서 그 정점에 거리를 넣었다.그리고 마지막에 정점을 다 보며 거리가 들어있으면 루트에서 그 정점까지 거라와 들어있는 거리를 비교해서 수를 세는 것이였는데바로 망했다 ㅎㅎ 7퍼에서 틀린다. 생각해보니 예외가있따 ㅎㅎ 문제를 푸는 방법을 봤따 ㅎㅎ푸는 방법은1. 각 정점에서 루트까지 거리와 가장 가까운 리프까지 거리를 구한다2. 모든 정점을 돌아보며 3. 루트가 아니고 && 리프까지 거리..

정점과 간선이 n,m(

교차하는 케이블의 수를 세는 문제다펜윅트리 or 머지소트로 풀수있다..!처음에 세그먼트트리로 풀었는데 계속 시간초과가 나길래방법이 틀린 줄 알았는데 map을 써서 시간초과가 났따 ㅎㅎ 문제를 푸는 방법은 1. 펜윅트리를 만든다. 초기값은 모두 02. 1~n까지 탐색을하며 B에서의 나의 위치 뒤에있는 것의 합을 더한다!3. 그리고 나의 위치를 트리에서 1로 바꿔준다 교차점의 수를 세는 것이므로 A의 앞에있던 공장이 B에서는 뒤에있다면 교차점이 생긴다. 그래서 뒤에 1이 몇개있는지만 세어주면 된다! 소스코드 - 펜윅트리12345678910111213141516171819202122232425262728293031323334353637383940#include #include #include using nam..

3개의 증가수열을 고르고 그 때의 비용이 최소를 찾는 문제다N^2 DP로 풀었다 d[pos][cnt]로 테이블을 잡고 pos까지 봤고 cnt개 더 고를 수있을 때로 문제를 풀었다 문제 풀고 틀려서 보니 메모이제이션을 안했다 ㅎㅎ소스 잘 봐야겠따..! 소스코드1234567891011121314151617181920212223242526272829303132333435363738394041424344#include #include #include #include #include #include #include #include #include #include #define ll long long#define inf 1e17using namespace std;ll arr[3030], cost[3030];int ..

dfs순서로 방문한다는 점을 이용해서 답을 찾으면 된다 나는 set충이므로 set을 사용했다..! 1. set에 방문한 정점을 담는다2. 새로운 정점을 방문했다면 그 이전 정점이 부모다(부모에서 자식으로 가므로)3. 이미 방문한 정점이면 건너뛴다4. set의 크기 == 정점 수 소스코드12345678910111213141516171819202122#include #include #include using namespace std;int n;int arr[200020], ans[200020];sets; int main() { scanf(" %d", &n); for (int i = 0; i