알고리즘 문제풀이 리뷰4

근래에 solved.ac 시즌 마감 소식을 들어서 아껴놨던 스프라그그런디 문제들이랑 이분매칭 문제들을 짧은시간안에 여러개 해결해보았다.

 

그리고 이후로는 부족한 구현실력, dp, 기하학 쪽 육각형을 채워나갈 생각이다.

 

이분매칭 문제들의 핵심은 알고리즘 그 자체 보다는 그래프 디자인인것같다. 이분탐색 처럼 문제가 이분매칭이다 라는 것을 눈치채는게 중요한것 같다.

 

https://www.acmicpc.net/problem/1671

상어의 저녁식사 P3

분류 : 이분매칭

이 문제는 읽어보면 이분매칭의 느낌을 준다. 상어가 두마리를 잡아 먹을 수 있다는 점이 열혈강호3와 비슷한 테크닉으로 해결할수 있어보인다. 하지만 문제는 예제에서 나오는 능력치가 동일한 상어이다. 이와 같은경우를 index별로 잘 정렬해서 이분매칭을 돌려줘야된다.

 

https://github.com/sjmjys954646/Algorithm/blob/master/boj1000-1999/boj1671.cpp

 

https://www.acmicpc.net/problem/1574

룩어택 P3

분류 : 이분매칭

이분매칭이라는 것을 알고 문제를 접근하니 관찰할 수 있었다. 그리고 비슷한 유형으로 비숍2 등이 있는데 이들 역시 같은 테크닉으로 해결이 가능하다. 룩을 가로에 배치하는 노드, 세로에 배치하는 노드를 이분매칭 시켜주면 최대값을 얻을 수 있다.

 

https://github.com/sjmjys954646/Algorithm/blob/master/boj1000-1999/boj1574.cpp

 

 

https://www.acmicpc.net/problem/1348

주차장 P2

분류 : 이분매칭, 그래프이론, 이분탐색

근래 봤던 문제중에 제일 괜찮은 문제 같다. 이는 문제를 그래프화 시키는 디자인이 핵심이다. 각 C마다 P로 가는 거리를 BFS()로 미리 다 구해놓고 "이분탐색"을 이용하여 이분매칭을 돌린다. 탐색값은 모든 차가 주차하는데 걸리는 시간을 parametric search로 구한다.

 

https://www.acmicpc.net/problem/15573

해당문제가 이분탐색, 그래프이론 문제이니 도움이 될것이다.

 

https://github.com/sjmjys954646/Algorithm/blob/master/boj1000-1999/boj1348.cpp

 

 

https://www.acmicpc.net/problem/11014

컨닝 2 P2

분류 : 이분매칭

 

저번에 dp, 비트마스킹으로 컨닝 1을 풀었는데 컨닝 2는 시간초과문제 때문에 이를 해결할수 없다. 이 문제를 보면서
"쾨닉의정리"라는 개념에 대해서 알게 되었고 결과적으로는 자리를 최대로 배치하기 위해서는 컨닝 할수 있는 노드들을 최대로 배치하고 이를 전체에서 제외하면 되는 풀이로 해결 할 수 있다. 이를 생각해 내는 것이 매우 어렵다고 생각한다.

 

https://github.com/sjmjys954646/Algorithm/blob/master/boj11000-11999/boj11014.cpp