백준 알고리즘 강의 후기(코드플러스): 네트워크 플로우 & 최소 비용 최대 유량
2021. 1. 19. 06:23
반응형
코드플러스에서 백준 알고리즘 강의(알고리즘 고급으로 가는 연결고리)를 듣고 작성한 후기입니다.
1700 - 네트워크 플로우
강의: 최대유량
포드풀커슨 배움 : DFS이용 O(EF)
에드먼드-카프 배움: BFS아용 O(VE^2)
네트워크플로우->그래프설계능력이 중요
강의: 이분매칭(최대유량으로 많이 푸는 문제)
강의: 최소컷(최대유량으로 많이 푸는 문제)
학교 가지마!
강의: 최소버텍스커버(최대유량으로 많이 푸는 문제)
정점 집합 S가 있을 때, 모든 간선의 양 끝점중 하나가 S에 포함되어 있어야 함
Minimun Vertext Cover
Konig's theorem
이분그래프 최소 버텍스커버
이분그래프일때만 최소매칭으로 풀수있다는 뜻
돌멩이 제거
행과 열의 조합을 가지는 이분 그래프를 만든다.
행과 열을 연결해서 그래프를 만들면 된다.
강의: 최대독립집합 Maximum Independent Set
그래프의 정점 집합
집합에 포함된 모든 정점끼리를 연결하는 간선이 없어야 함 -> 양 끝점이 다 포함되어 있지 않거나 하나만 포함되어야 함
NP-Hard, 즉 풀수 없다는 뜻
'최소 버텍스 커버'과 다른 점은 그건 '적어도 하나' '최대독립집합'은 '최대 하나'
컨닝 2
1701 - 네트워크 플로우 (연습)
소수 쌍
주차장
게시판 구멍 막기
N-Rook
백준 2570 비숍2
행과 열이 아니고 대각선에 번호를 메겨서 문제를 해결해야 한다.
백준 17412 도시 왕복하기 1
최대유량
백준 2316 도시 왕복하기 2
정점을 반 쪼개고 인아웃, 즉 최대유량 문제
체스판 2
천하제일 게임 대회
완전 중요한 간선
스타 대결
틀렸습니다
숫자판 만들기
1710 - 네트워크 플로우 2
1720 - 최소 비용 최대 유량
1721 - 최소 비용 최대 유량 (연습)
1722 - 최소 비용 최대 유량 (도전)
반응형
