본문 바로가기

백준

20026 Fix Wiring 와악 처음에 문제 이해를 못했다. mst로 최대 최소를 구한다고??? 최소는 알겠는데 최대? 알고보니 모든 경우의 수 중 최대를 구하게끔 잘 연결해야 하는 거였다. 그림에도 나와있지만 불필요한 연결에 최솟값을 주면 그게 최대가 된다. 이리저리 그려가면서 생각해보니 답이 나왔다. #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 .. 더보기
2406 안정적인 네트워크 문제 처음 읽었을 때는 바로 이해 안 됐지만 그려보니 바로 이해됐다. 일단 집합과 집합을 연결하는 최소 비용을 고르면 된다. 그래서 먼저 같은 집합으로 묶어놓고 같은 집합이라면 패스하도록 구현했다. #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 = pa.. 더보기
22116 창영이와 퇴근 풀이 자체는 쉬웠다. 인접 배열을 전부 간선으로 만들고 또 MST 돌려야지. 그리고! 전에 북님이 알려준대로 find(s) == find(e)인 순간이 최대 경사의 최솟값이 돼서 종료하면 되겠다 싶었다. 그런데 한 열 번은 틀렸다........... 인덱스를 따로 관리하니 너무너무너무 헷갈렸다...... 틀린 이유 1. 첫 번째 시도 노드 번호를 형식으로 붙이기 어려워서 이걸 전부 인덱스를 따로 붙였다. 0 1 2 3 4 5 6 7 8 이런 식으로 그러면 인덱스가 n * n - 1 사이즈까지 가는데, parent 배열의 사이즈는 n까지 잡았다. 그래서 out of bound 에러가 떴다. 그 이후 또 찾아보려고 했는데 도저히 원인을 몰라서 울고 싶었다. 알고보니... 2. 두 번째 시도 로직 문제와 in.. 더보기
16398 행성 연결 이 문제 보자마자 그냥 행렬로 들어온 MST구나~ 싶었다. 그런데 순간 Cij의 최댓값이 10^9이라 어 숫자가 큰데?? 그런데 N은 1000이라 좌표압축이 필요하겠다 싶었다. (왜 이렇게 생각했지? 퇴근하고 바로 풀어서 그랬나보다) 그렇게 생각만 하고 일주일 뒤 오늘 바로 좌표압축부터 공부했다. 직접 손코딩하면서 또 코드 안 보고 짤 수 있도록 익혔다. 그러곤 문제 다시 읽으니 좌표압축이 굳이 필요 없는 문제였다... 해결~ #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #def.. 더보기
13905 세부 와 mst 분류 몰랐다면 못 풀었을 것 같다. 이번 기회에 mst만 쭉쭉 풀면서 감 잡아봐야겠다. 일단 작은 수는 안 지나는게 이득이라 먼저 큰 수만 남긴다. (역 mst?) 그러곤 출발지에서 도착지로 bfs로 구하면 되겠다 싶었다. 여담이지만 마찬가지로 bfs도 손으로 적으면서 다시 익혔다. 두어번 적으면 외워지더라. 그래서 mst도 bfs도 이제 블로그 코드 안 보고 짤 수 있다! 그런 든든한 마음으로 문제를 풀기 시작했다. 막힌 부분이 두 부분 있었는데, 1. bfs에서 간선을 계산할 때 가중치 정보도 필요했다. -> 최선인지 모르겠지만 다음 노드와 가중치를 함께 저장했다 for (auto e: edge){ if (Find(e.u) == Find(e.v)) continue; Merge(e.u, e... 더보기
1647 도시 분할 계획 -마을을 두 개로 분할한다 - 분리된 두 마을 사이 길은 필요없다 - 마을 안에서 임의의 두 집 사이 경로는 항상 존재 - 마을에는 집이 하나 이상 있어야 한다 - 길의 유지비는 최소 으음..... 마을을 두 개로 어떻게 나눠야 할지 모르겠다. 마을을 나누기 위해서 다리를 1개를, 2개를 등등 여러 개 끊을 수 있는데 이걸 어떻게 나눠야하지? 그러곤 알고리즘 방에 질문 올리고 그래프로 더 그려보면서 생각했는데 방법이 떠올랐다. MST를 그리면 최소 간선들만 남는다. (나는 다각형이 나올거라 착각했다) 그럼 그 최소 중 하나만 잘라내면 마을을 두 개로 분리할 수 있다. 그 하나가 최대인 걸 잘라야 하는 거고... 허.... 뭔가 반으로 나누면서 길을 없앨 수 있고 -> 그럼 반으로 나눌 때 최대한 많은 길.. 더보기
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.. 더보기

티스토리툴바