취업 준비 및 일상

https://www.acmicpc.net/problem/7616 7616번: 교실로 가는 길 각 테스트 케이스마다 "Case #:" 형식으로 케이스 번호를 출력한다. 그 다음, K개의 겹치지 않는 경로 (1번에서 출발해 2번으로 도착하는 경로)가 존재하면 K개 줄에 각 경로를 출력한다. 없는 경우 www.acmicpc.net 풀이 백준 2316번처럼 간선 뿐만 아니라 정점도 최대 한 번만 방문할 수 있으므로, '정점 분할'을 해 줍니다. 에드몬드-카프로 유량이 K 이상인지(==경로가 K개 이상인지) 확인하여, K개 이상일 경우 경로를 출력해줍니다. 유의할 점으로는, 에드몬드-카프에서 찾은 K개 증가 경로를 역추적하여 출력할 경우 제대로 된 결과가 나오지 않을 수 있습니다. 2 6 3 5 4 6 1 4 ..

https://www.acmicpc.net/problem/2316 2316번: 도시 왕복하기 2 N개의 도시가 P개의 양방향 길로 연결되어 있다. 이석원은 1번 도시와 2번 도시 사이를 오가며 워해머를 한다. 성실한 이석원은 두 도시 사이를 최대한 많이 왔다 갔다 하려 하는데, 이때 한 번 방 www.acmicpc.net 풀이 라이님 블로그를 참고했습니다. 점을 한 번만 표현하기 위해, '정점 분할'을 해줍니다: 점 U를 점 U, U'으로 나누어, 점 U와 U' 사이 유량이 1인 단방향 간선으로 연결합니다. 점 U에서 점 V로 가는 양방향 간선을 다음과 같이 표현합니다: U'->V 단방향 간선, V'->U 단방향 간선 이후 에드몬드-카프 알고리즘을 수행하면 됩니다. 코드 1 2 3 4 5 6 7 8 9 ..

개요 당연하게도, 코테를 준비하는데 있어서 네트워크 플로우는 '투머치'합니다. 코테를 준비하는데 있어서 바킹독 선생님이 다루는 범위도 과분하다고 할 정도로 충분하고(해당 문제집에는 위상 정렬, MST, 수학 등 출제 빈도가 낮은 알고리즘도 있습니다), 카카오와 같은 코테가 '빡센' 곳을 생각해도 트라이, 세그먼트 트리, KMP 정도만 추가하여 준비하는 것이 최선입니다. 그러나, 1) 최근에 본 현대모비스 알고리즘 경진대회, 그리고 네이버 코테(확실하지 않음: 시간이 없어서 문제 자체를 못 봤음...ㅠ)에 나왔으며, 2) 궁금하며 3) 솔브닥 티어좀 올리고 싶어서 흐름 네트워크에서의 최대 유량을 구하는 알고리즘을 공부, 정리하였습니다. 기본 개념 Everenew님 글: 대부분의 블로그 포스트가 종만북을 기..