본문 바로가기

전체 글

1197 최소 스패닝 트리 mst 기본 문제 요즘에 너무 복붙만 해서 블로그 못 보면 문제를 못 풀 것 같았다. 그래서 아예 초심으로 돌아가서 그냥 백지에다 정리한 다음 풀었다. 암튼 문제를 풀기 전 백지에 두어번 적어보면서 풀었다는 걸 강조한다. 풀이는 간단하다. - Edge 입력받기 - 가중치 기준으로 정렬한다 - 가중치가 작은 것부터 더해간다 시간 복잡도는? - 정렬이 nlogn (eloge) - edge 확인하면서 유니온파인드 find, merge -> 이것도 nlogn (elogv) - e가 10만 이하라 시간복잡도 터지지 않는다 #include #include #include #include #include #include #include #include #include #include #include #include .. 더보기
9226 도깨비말 알고리즘 주에 3문제 풀기 위해서 쉬운 문제라고 빠르게 풀었다. 시작 점을 기준으로 한바퀴 순회하는 걸 깔끔하게 짜서 뿌듯하다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define xx first #define yy second #define all(x) (x).begin(), (x).end() using namespace std; using i64 = long long int; using ii = pair; using iis = pair; using ii64 = pair.. 더보기
14615 Defend the CTP!!! 1. bfs로 시도했다 -> 시간초과 2. 한번 확인한 경우는 값을 저장해놓으면 빨라지지 않을까? -> 시간초과 3. cin으로 빠른 입출력을 사용하면? -> 시간초과 3진 시간초과로 다음 문제로 넘어갔다. #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define xx first #define yy second #define all(x) (x).begin(), (x).end() using namespace std; using i64 = long long int; using ii.. 더보기
24778 Cracking The Safe 많은 고민을 했는데도 결국 생각해내지 못했다.. 그런데 언젠가 푼 적이 있는 것 같다? 생각해보니 십자뒤집기 문제와 비슷했다. 경우의 수가 얼마 없으니 모든 뒤집는 경우를 다 구해보고 풀면 되겠다 싶었다. https://burningjeong.tistory.com/616 10472 십자뒤집기 어렵다.. 예시 직접 구해보려다가 최소 3번도 못하고 있다ㅋㅋㅋ 3*3이라 전부 구해도 될 것 같은데? 그런데 전부 구하는 방법도 모르겠다. -- 아 문제를 덜 읽었다. 흰색 보드를 클릭해서 입력으 burningjeong.tistory.com 이처럼 9개밖에 안 될 때는 모든 경우로 문제를 풀 수 있다는 걸 떠올려보자. 그런데 이전 문제 풀 때와 다른 점이 있었다. 바로 0, 1로 이루어진 게 아니라 0, 1, 2,.. 더보기
9367 관리 난항 아.. 시뮬레이션..... 못풀었다. 어렵다 . #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define xx first #define yy second #define all(x) (x).begin(), (x).end() #define NOT_USING -1 #define INCONSISTENT -1 using namespace std; using i64 = long long int; using ii = pair; using iis = pair; using ii64 = pair.. 더보기
20390 완전그래프의 최소 스패닝 트리 #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define xx first #define yy second #define all(x) (x).begin(), (x).end() using namespace std; using i64 = long long int; using ii = pair; using iis = pair; using ii64 = pair; using iii = tuple; struct Edge { i64 u, v, d; }; i64 par[10005]; i64 f.. 더보기
16493 최대 페이지 수 입력이 작아서 모든 경우의 수를 다 구해도 되겠다 싶었다. 비트마스크로 모든 경우를 다 구해서 페이지 합산, 일 합산을 구한다. 일 합산이 기한보다 작은 경우 최대 페이지 수를 구한다. 끝~ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define xx first #define yy second #define all(x) (x).begin(), (x).end() using namespace std; using i64 = long long int; using ii = pair; .. 더보기
14621 나만 안되는 연애 그래프의 최단 거리를 구해야 하기 때문에 MST를 사용하면 되겠다 싶었다. 그런데 MST를 일년 전에 공부했고 자료도 정리해놓지 않아서.... 다시 이해하는데 오래 걸렸다. 그리디하게 가장 edge를 구해놓고 가장 짧은 것부터 뽑아서 계산한다. Union Find로 해당 간선이 이미 계산된 간선인지 확인한다. 코드는 1. 학교 입력 받으면서 유파 초기화 2. 여-남 경우에만 간선을 추가한다 3. 간선을 오름차순으로 정렬한다 -> 그리디하게 가장 짧은 것부터 뽑기 위해서 4. 가장 짧은 길이부터 뽑아서 더한다, 간선을 몇 개 더했는지도 계산한다 5. 간선이 n - 1개가 아닌 경우 노드를 전부 확인 안 했으니 -1을 출력한다 #include #include #include #include #include .. 더보기

티스토리툴바