백준 알고리즘 강의 후기(코드플러스): 네트워크 플로우 & 최소 비용 최대 유량

코드플러스에서 백준 알고리즘 강의(알고리즘 고급으로 가는 연결고리)를 듣고 작성한 후기입니다.

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

비숍2

행과 열이 아니고 대각선에 번호를 메겨서 문제를 해결해야 한다.

백준 17412 도시 왕복하기 1

도시 왕복하기 1

최대유량

백준 2316 도시 왕복하기 2

도시 왕복하기 2

정점을 반 쪼개고 인아웃, 즉 최대유량 문제

체스판 2

천하제일 게임 대회

완전 중요한 간선

스타 대결

틀렸습니다

숫자판 만들기

Problem Solving with Algorithms