분류 전체보기327 [열혈] 단순한 서버-클라이언트 코드 구조의 이해 서버, 클라이언트 코드의 가장 단순한 버전을 이해하기 위한 글 1. 네트워크 프로그래밍과 소켓의 이해 네트워크 프로그래밍 : 네트워크로 연결된 서로 다른 컴퓨터가 서로 데이터를 주고받을 수 있도록 하는 것 소켓 : 물리적으로 연결된(ex. 인터넷) 네트워크 상에서의 데이터 송수신에 사용하는 운영체제가 제공하는 sw장치. 네트워크 망의 연결에 사용되는 도구. 네트워크를 통한 두 컴퓨터의 연결을 의미하기도 한다. 네트워크 프로그래밍을 소켓 프로그래밍이라고도 한다. 서버의 소켓 생성과정 1. socket() : 소켓 생성 2. bind() : IP주소와 PORT번호 할당 3. listen() : 연결요청 가능 상태로 변경 4. accept() : 연결요청 수락 클라이언트의 소켓 생성 과정 1. socket().. 2020. 10. 19. 최대 유량 - 디닉 jason9319.tistory.com/150 blog.naver.com/kks227/220808685331 위 두 블로그에서 공부했습니다. 특히 코드는 jason님의 코드를 많이 참고했습니다. $O(V^2E)$ 1. bfs로 각 정점마다 소스로부터 얼마나 떨어져있는지 의미하는 level 배열을 초기화 해준다. 싱크에 도달할 수 있다면 2. 소스-싱크 경로상 차단 유량을 구해준다. dfs에 지금까지 최소 유량을 같이 보내주고 반환값을 이후 최소 유량으로 설정하면 쉽게 구할 수 있다. 차단 유량이 0보다 크다면 반복한다. dfs할 때 역방향 간선 때문에 한 정점을 여러번 접근할 수 있다. work배열로 정점 u를 여러 번 접근하더라도 dfs 진행에 있어서 다음 정점 v를 중복해서 접근하지 않도록 한다. w.. 2020. 10. 9. 이분매칭 blog.naver.com/kks227/220804885235 라이님 블로그에서 공부했음을 밝힙니다. 설명은 라이님 블로그 정독 이분그래프에서 최대 매칭 수를 반환한다. 하나의 class의 모든 정점을 돌면서 각 정점마다 최악의 경우 모든 간선을 확인하게 된다. $O(VE)$ Hopcroft-Karp Algorithm($O(E\sqrt{V})$)로 대체 가능하다. www.acmicpc.net/problem/17412 각 소마다 원하는 축사가 있다. 가장 많은 소를 축사에 배정하라. 이분매칭 const int MAX = 201; //A[i] : A그룹의 i번째와 매칭된 B그룹의 정점번호 int n, m, A[MAX], B[MAX]; vector g[MAX]; bool vst[MAX]; //A그룹의 정점 u.. 2020. 10. 7. 최대 유량 - 에드몬드 카프 blog.naver.com/kks227/220804885235 라이님 블로그에서 공부했음을 밝힙니다. 설명은 라이님 블로그 정독. $O(min(VE^2, Ef))$ 단방향 그래프인 경우 1. capacity를 적절한 간선에만 뚫어줘야 한다. 2. 역방향 간선도 인접리스트에 같이 추가해줘야 한다. (capacity로 구분되는 것) 양방향인 경우, u-v, v-u간선에 모두 capacity를 뚫어줘야 함. www.acmicpc.net/problem/17412 각 소마다 원하는 축사가 있다. 가장 많은 소를 축사에 배정하라. 소를 향하는 더미 노드와 간선, 축사에서 향하는 더미노드와 간선을 추가해서 capacity가 1인 최대유량을 흘려주면 된다. 단방향 그래프임에 주의. 소 n마리 축사 m개인데, 축사의 정.. 2020. 10. 7. 이전 1 ··· 9 10 11 12 13 14 15 ··· 82 다음
