(구) 알고리즘 고급으로 가는 연결고리

1. 다이나믹 프로그래밍 3

비트마스크를 이용해 상태를 나타내고 그 상태를 다이나믹에 이용해 봅니다. 약 10개의 문제를 풀게 됩니다.

마지막으로는 한 문제를 5가지 서로 다른 점화식을 통해서 풀어봅니다.

2. 네트워크 플로우

그래프에서 가장 중요한 알고리즘인 네트워크 플로우를 배웁니다.

최대 유량이 무엇인지를 배우고, 최대 유량을 구하는 두 가지 알고리즘인 Ford-Fulkerson과 Edmond-Karp에 대해서 배웁니다.

이분 매칭, 민 컷, 최소 버텍스 커버, 최대 독립 집합에 대한 이론과 내용을 공부하고, 문제 풀이에 응용해 봅니다.

이 챕터는 알고리즘보다 그래프를 만드는 방법이 중요하기 때문에, 약 15가지 문제를 이용해 그래프 모델링을 연습해봅니다.

3. 최소 비용 유량 (MCMF)

최대 유량 문제에서 최소 비용문제가 추가되면 최소 비용 유량 문제가 됩니다. 이를 영어로 줄여서 MCMF라고 합니다.

MCMF도 그래프 모델링이 중요하기 때문에, 네트워크 플로우 챕터처럼 그래프 모델링하는 연습을 해봅니다.

4. 세그먼트 트리 활용하기

구간의 최소값과 합을 구할 때 사용한 세그먼트 트리를 다른 문제 풀이에 이용해봅니다.

먼저, 분할 정복과 함께 세그먼트 트리를 사용하는 방법을 배우고, 최소값을 찾는 방법을 이용해서 K번째를 찾는 방법을 배웁니다.

5. 네트워크 플로우 문제 풀이

여러가지 네트워크 플로우 문제를 풀어봅니다.

포함되어 있는 문제

1. 다이나믹 프로그래밍 3

2. 네트워크 플로우

3. 최소 비용 유량 (MCMF)

4. 세그먼트 트리 활용하기

5. 네트워크 플로우 문제 풀이

01챕터: 다이나믹 프로그래밍 3

문제 풀기 1맛보기00:17:31

문제 풀기 200:18:25

문제 풀기 300:13:20

02챕터: 네트워크 플로우

네트워크 플로우00:16:58

이분 탐색00:03:38

이분 매칭00:20:05

최소 컷00:07:20

최소 버텍스 커버00:16:36

03챕터: 최소 비용 유량 (MCMF)

MCMF00:16:19

문제 풀기 100:16:07

문제 풀기 200:21:59

04챕터: 세그먼트 트리 활용하기

최소값 찾기00:29:17

합 구하기00:13:57

합 구하기 200:20:07

K번째 찾기00:07:42

05챕터: 네트워크 플로우 문제풀이

문제 풀이 100:20:38

문제 풀이 200:20:26

문제 풀이 300:12:28

문제 풀이 400:11:24

문제 풀이 500:19:54

Problem Solving with Algorithms

(구) 알고리즘 고급으로 가는 연결고리