kth990303의 코딩 블로그

이분매칭 (Bipartite Matching) Maximum Flow를 구하는 방법에는 Dinic Algorithm이 존재한다. 그런데, 모든 간선의 flow가 1이고, 이분 그래프 형태로만 존재한다면 bipartite Matching을 시도할 수 있다. (예를 들어 남녀가 미팅을 하며 각자가 원하는 짝을 1명씩 선택할 때, 최대 수로 성사시킬 수 있는 경우의 수는 이분 매칭으로 구할 수 있다.) 참고로 먼 옛적에는 Blossom Algorithm (1961)으로 최대 이분매칭 수를 O(EV^2)에 구했었다. 최악의 경우 O(V^4)까지 나올 수 있었던 셈. 원리가 궁금하다면 소멤 글을 참고해보자. https://www.secmem.org/blog/2020/04/18/Blossom/ 이분매칭의 시간복잡도..

지난 포스팅에 knapsack은 탑다운보단 바텀업을 짜는 것이 훨씬 유리하다고 작성한 적이 있다. (아래 포스팅 참고) https://kth990303.tistory.com/207 [Knapsack] 냅색은 웬만해선 바텀업으로 짜자 knapsack dp를 알고 있는가? 아래 문제는 굉장히 유명해서 모두들 알고 있을 것이다. (0-1 knapsack의 Standard) https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100.. kth990303.tistory.com 이번 포스팅에선 knapsack 문제 유형을 익혀보고 공부해보는 시간을 가져볼 것이다. knapsack에서 개인적으로 중요하다 생각하는 것은 아래와 같다. 이 ..

그룹원 한분께서 요청해주신 문제를 해결하면서 degree sequence 라는 개념을 알게 됐다. Warming Up 요청해주셨던 문제는 아래와 같다. 한 번 풀어보도록 하자. (degree sequence 개념을 몰라도 해결이 가능하다.) https://www.acmicpc.net/problem/23578 23578번: 비 오는 날 피에스고등학교의 교장 이환이는 학교를 매우 사랑한다. 그래서 이환이는 매일 점심시간에 학교의 모든 건물을 돌아다닌다. 비가 오는 어느 날, 이환이는 학교 곳곳을 돌아다니고 싶었지만 비 www.acmicpc.net 불만을 최소화하기 위해서는 최소한의 다리로 건물을 연결해야 하며, 따라서 mst를 금방 떠올릴 수 있다. 그러나, 단순 mst 문제는 아니고, 차수에 따라 답이 달..

knapsack dp를 알고 있는가? 아래 문제는 굉장히 유명해서 모두들 알고 있을 것이다. (0-1 knapsack의 Standard) https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 위 문제는 N 범위가 워낙 작아서 탑다운이든 바텀업이든 다 뚫린다. 이 문제만 보면 어떻게 풀어도 상관없겠다는 생각이 들 수 있다. 탑다운? 써도 상관없을 것 같은데? 나도 웬만한 dp는 탑다운으..

이왕 블로그 만든 김에, 제가 블로그를 만든 이유인 백준 포스팅을 하나 하려고 합니다. 코딩에 익숙하지 않으신 편이면, 사고는 되는데 구현이 힘든 경우가 많습니다. "아, 나는 이렇게 이렇게 풀어야 함은 아는데, 코드로 구현을 못하겠다... 답답하네." "설마 이렇게 푸는게 맞겠어? 너무 복잡한데" 이러한 한탄은 대부분 코딩 경험이 적어서, 또는 현재 하고 있는 언어(ex. C++) 문법이 익숙하지 않아서일 확률이 거의 80% 이상입니다. 간단하게 문제 하나 보고 가시죠. www.acmicpc.net/problem/1233 1233번: 주사위 지민이는 주사위 던지기 게임을 좋아하여 어느 날 옆에 있는 동호를 설득하여 주사위 던지기 게임을 하자고 하였다. 총 3개의 주사위가 있다. 그리고 이 주사위는 각각..