Network Flow 관련 문제 해결에 대하여 조언을 구하고자 합니다.

  • chiller123
    chiller123

    안녕하세요. PS에 입문한지 얼마 되지 않은 학부생입니다.
    최근에 JMBook을 보면서 네트워크 유량에 대한 공부를 하는 중입니다.

    보통 문제가 주어졌을 때, 해당 문제에 대해서 어떤 주제인지 미리 알고 풀기 시작하는 것은 문제 해결력을 기르는데 방해 요소가 된다는 것을 알고 있습니다.

    하지만, 네트워크 유량 관련 문제는 접근도 중요하지만, 어떠한 형태의 Input이 주어졌을 때 그것들을 유량관련 알고리즘을 적용시킬수 있는 그래프로 "모델링"하는 것이 가장 중요하다고 느껴졌습니다.

    문제에서 요구하는 것이 무엇인지 안다한들, 표현할 수 없다면 말짱 도루묵이라는 생각이 들었기에 네트워크 유량 관련 문제들을 최대한 많이 모아서 풀어봄으로써 이러한 어려움을 극복할 수 있을 것이라고 생각하였습니다.

    이에 따른 문제는 네트워크 유량에 관련해서는 관련 정보가 매우 적다는 것입니다.

    다른 빈출 주제 (예: DP)들의 경우, 비단 ACM ICPC 뿐만 아니라 다른 PS Contest에서 많이 나오는 주제이기도 하고, 관련 서적이나 웹 상에서 찾을 수 있는 많은 문제 관련 정보를 바탕으로 단계적 접근이 가능하다고 느낍니다. 실제로 구글링을 해보아도 많은 문제에 대해서 접근법이 소개되어 있는 사이트들이 많았습니다.

    반면에, 유량 관련 문제들은 검색으로 인해 구할 수 있는 문제수가 상대적으로 적다보니, 제가 생각했던 "문제를 모아서 Step-By-Step 방식의 실력 향상"은 어려워보입니다.

    결론을 말하자면, 이 분야의 문제를 해결을 위한 실력을 향상시키기 위해서 어떻게 접근을 하면 좋을까요? 그저 지금 단계에서는 이론적인 지식을 더 습득하는게 더 좋을까요?

    추가로, 제 글의 내용에 있어서 옳지 않은 내용이 있다면 지적을 해주시면 감사하겠습니다. (__)


    5년 전
2개의 댓글이 있습니다.
  • 장홍준
    장홍준

    저도 많이 부족하지만, flow 문제들의 경우 모델링이 중요하여 문제를 많이 풀어보는 게 좋을 것 같다는 말씀에 동의합니다.
    도움이 될까싶어 https://www.acmicpc.net/workbook/view/68 를 공유합니다.


    5년 전 link
  • chiller123
    chiller123

    BOJ에 저런 문제집이 있었군요.. 정보 제공 감사합니다.


    5년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.