이분 매칭5 [자바] 백준 11378 - 열혈강호 4 (java - 풀이4개) 목차 문제 : boj11378 필요 알고리즘 개념 네트워크 플로우(최대 유량) 애드몬드 카프 등의 네트워크 플로우(최대 유량) 알고리즘을 알고 있어야 한다. 단, 자바의 경우 빠른 입출력까지 사용해야 애드몬드 카프 알고리즘으로 시간 초과 없이 통과 가능하다. 이분매칭 네트워크 플로우에서 이분 그래프로 구성이 가능할 시 사용 가능한 이분매칭 알고리즘을 사용하면 네트워크 플로우보다 더 빠른 시간내에 통과 가능하다. 이 경우엔 자바라도 빠른 입출력 없이도 여유롭게 통과 가능하다. 풀이 1과 풀이 2에서 최대 유량을 이용한 풀이를 한다. 풀이 3과 4에서는 이분매칭을 통해 풀어본다. 각 풀이는 네트워크 플로우 또는 이분매칭 알고리즘의 기본적인 구현 방식을 알고있다는 전제하에, k개의 추가된 일을 어떻게 처리하는.. 2022. 12. 18. [자바] 백준 3683 - 고양이와 개 (java) 문제 : boj3683 필요 알고리즘 개념 이분 매칭 이분 매칭으로 풀 수 있긴 한데, 아이디어 떠올리기가 좀 많이 어려운 편인거같다. ※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다. 풀이 아이디어 생각하기도 어려웠고, 이분 매칭으로 처리하려고 해도 모델링이 상당히 어려운 문제였다 ㅠ. 이분 매칭에서 좌측에 고양이를 좋아하는 사람, 우측에 개를 좋아하는 사람을 둔다. 그리고 좌측에서 우측으로 고양이를 좋아하는 사람이 싫어하는 개를 .. 2022. 9. 17. [자바] 백준 1867 - 돌멩이 제거 (boj java) 문제 : boj1867 Minimum Vertex Cover 문제이다. 즉, 최소한의 정점만을 선택했을 때, 모든 간선들이 양 끝점 중 하나는 선택된 정점이어야 한다. 이 문제의 경우 열 번호와 행 번호를 각각 정점으로 두고, 돌멩이가 존재하는 위치를 간선으로 두자. 그럼 예제 입력 1의 경우 다음과 같이 그래프로 변경해볼 수 있다. 3 4 1 1 1 3 2 2 3 2 이 때 Minimum Vertext Cover는 다음과 같다. 이 때, 행과 열에 대해 이분그래프로 나타낼 수 있으므로 쾨니그의 정리(위키)를 적용해볼 수 있다. 복잡하게 써있지만 결론은 이분그래프에서 Minimum Vertext Cover는 이분 그래프의 최대유량 문제와 동일하다는 의미이다. 이분그래프의 최대유량이므로 이분 매칭(MIT .. 2022. 5. 30. [자바] 백준 1671 - 상어의 저녁식사 (boj java) 문제 : boj1671 문제에서 제시된 상황이 그래프로 표현 가능한 경우 그래프로 바꿔서 생각해보는 것이 이득인 경우가 많다. 이 문제의 경우에도 주어진건 상어의 크기, 속도, 지능으로 3개나 되지만, 사실 그래프의 간선으로 생각해본다면 값이야 어떻든 조건을 만족한 경우 그냥 방향이 있는 간선 하나가 추가될 뿐이다. 예시 입력 1을 그려보면 다음과 같다. 간선은 [먹는쪽 -> 먹히는쪽]으로 연결할 것이다. 5 4 5 5 10 10 8 5 7 10 8 7 7 8 10 3 그럼 동일 정점을 좌우로 둬서 다음과 같이도 그려볼 수 있다. 결국 최대한 많이 잡아먹으면 남아 있는 수가 최소가 되므로, 최대유량 문제인데 이분그래프 이므로 이분매칭을 사용해서 좌측의 상어가 우측의 상어를 먹는다고 생각해보자. 그리고 좌.. 2022. 5. 26. 백준 1575 자바 - 졸업 (BOJ 1575 JAVA) 문제 : https://www.acmicpc.net/problem/1575 코드 : https://github.com/NaHwaSa/BOJ_BaekjunOnlineJudge/blob/master/01500/BOJ_1575.java 생각해야 할 부분이 많은 까다로운 문제였다. 그래도 1시간정도 걸렸으니 그저께 8시간 걸려 풀었던 문제 보다는 훨씬 나았다. 플래도 가끔씩 풀어지긴 하는데, 아직 내 실력으론 풀어도 보통 1시간 이상은 기본으로 걸리는 것 같다. 나중에 한 번 틀리고 나서 본건데, 6개월 전부터 '맞았습니다'가 하나도 없는 문제였다. 미리 채점 현황을 봤다면 아예 시도를 안해봤을수도 있을듯 ㄷㄷ 처음에 틀리고 나서는 나도 저 중에 하나가 되겠거니 했는데, 자기 전에 맞아서 꿀잠 잘 것 같다. 0.. 2021. 10. 26. 이전 1 다음
