PS와 개발을 공부하자

Guestbook

방명록쓰기 폼
  • 2017.10.25 00:23 비밀댓글입니다
  • sgc109 2017.10.25 00:27 신고 수정했습니다!
  • qda3 2017.10.11 01:22 신고 http://sgc109.tistory.com/200
    안녕하세요.. 취업땜에 ps 준비하려고 하는데 처음이라 너무 어렵네요.. 도움좀 부탁드립니다.
    mcmf 문제에서 Edge를 int to, cap, cost, rev; 이렇게 정의하셨고,
    G[from].push_back({ to, cap, cost, (int)G[to].size() }); 이렇게 초기화 하셨는데
    rev 변수가 무슨 의미를 갖는지 도저히 모르겠네요...

    아 그리고 edgeIdx, par 배열도 무슨뜻인지 알 수있을까요?
    par 는 parent 같긴한데.. edge Idx 는 의미를 잘 모르겠네요..

    그리고 시험같은 거에서 문제 푸실때 저런 코드를 그냥 다 머리속으로 작성을 하시는건가요?
    아니면 알고리즘같은건 미리 어느정도 작성해두신걸 이용하시는건지..

    진짜.. 대단하시네요...... 존경합니다... 많이 배우고가요..
    배워도 의미가 있을지 모르겠지만 엉엉 ㅠㅠ
  • sgc109 2017.10.18 20:09 신고 우선 네트워크 플로우에서 유량 그래프를 인접행렬로 구현하는 방법이 있고 인접리스트로 구현하는 방법이있어요. 그런데 두 가지 방식의 장 단점이 있거든요. 우선 인접행렬은 구현이 간편하다는 장점이있지만 노드의 수가 많은경우에는 2차원 배열을 선언할 수 없는 경우가 있고, 두 노드 사이에 간선이 여러개 있는경우에도 처리하기가 힘들어져요. 그래서 인접리스트 형식으로 작성하기 위해서 아예 간선 자체를 구조체로 만들어 준거구요. 간선 구조체 내에는 간선이 가리키는 노드번호인 to, 용량인 cap, 비용인 cost, 그리고 rev 가 있는데요. rev가 뭐냐면, 유량 그래프를 만들때에는 무조건 반대방향 간선을 만들어주잖아요? 그런데 인접행렬에서는 단순히 2차원 배열의 두 인덱스를 바꿔서 넣어주면 되지만 인접리스트에서의 2차원 인덱스는 노드 번호와는 전혀 상관이 없거든요. 그래서 그 인덱스를 그래프를 형성할 때 각 에지를 만들때마다 미리 구해서 넣어주는거에요. 반대방향 간선을 만들어주는 이유는 플로우를 공부하셨다면 아실거라
    믿습니다.

    그리고 플로우에서 핵심이 augmenting path(증가경로) 를 찾는거잖아요? 이 증가경로를 찾은 뒤에는 이 경로 상에 존재하는 모든 간선들에 흘릴 수 있는 최대의 유량을 흘려줘야해요. 그러기 위해서 경로를 찾은뒤 sink 부터 src 까지 역추적을 해야하구요. 인접 행렬에서는 증가경로를 찾을 때 각 노드의 parent 만 표시해줘도 간단히 가능하지만 인접리스트에서는 parent 뿐만아니라 해당 간선이 G 라는 인접 리스트의 면번째 인덱스에 존재했는지를 기록해주어야해요. 그래서 edgeIdx 라는 배열을 선언해서 증가경로를 구할 때 다음 노드로 넘어갈
    때마다 par랑 동시에 기록을 해준거구요.

    그리고 오프라인 대회같은 경우에는 직접 생각하면서 구현하고 온라인 대회처럼 미리 만들어 놓은 코드를 사용해도 되는 경우에는 직접 라이브러리화 시켜놓은 코드를 그대로 가져다 써요. 아마 대부분의 분들이 이렇게 하실거라고 생각해요. 플로우 코드는 기니까요.. ㅎㅎ

    그리고 아마 제대로 이해를 하시고 여러번짜보시면 한동안 안짜셔도 생각하면서하면 충분히 구현할수있다고 생각해요. 정말 오랜만에 구현할때는 좀 생각이 안나거나 속도가 안나올순있죠 그래서 오프라인대회 전에 한번씩 다시 구현해보고 가시는분들도 많은것같아요. 도움이되셨나요? ㅎㅎ
  • 2017.08.19 15:43 비밀댓글입니다
  • sgc109 2017.08.19 17:58 신고 행렬 dp 에 대해 검색해보세요! 행렬 dp를 공부하시면 분명 풀수있으실거에요