(구) 알고리즘 고급

1. 그래프 알고리즘 3

먼저 오일러 회로를 구하는 방법을 배웁니다. 그 다음 강한 연결 요소 (SCC)을 구하는 Kosaju's Algorithm과 Tarjan's Algorithm을 배웁니다. 여기서 DFS Tree에 대한 내용도 배웁니다.

그 다음, Tarjan's Algorithm을 응용해 단절점과 단절선을 구하는 방법을 배우고, 문제 풀이로 응용해 봅니다.

마지막으로 배우는 내용은 2-SAT 문제 입니다.

2. 다이나믹 프로그래밍 4

다이나믹 프로그래밍 4에서는 지금까지 다루지 않았던 다양한 유형의 다이나믹 문제를 풀어봅니다.

트리 다이나믹, 왼쪽과 오른쪽을 왔다갔다 하면서 푸는 다이나믹, 다이나믹 점화식을 통해서 정답을 역추적하는 방법, 확률 다이나믹, 왼쪽과 오른쪽에서 시작해서 가운데로 모이는 다이나믹을 배웁니다.

3. 문자열 알고리즘

문자열 매칭 알고리즘을 배우는 챕터입니다.

KMP, Trie, Aho-corasick, Suffix Array에 대한 내용을 배웁니다.

4. 알고리즘 게임

알고리즘 게임 챕터에서는 조합 게임(Combinatorial Game) 문제 중에서 Impartial Game 문제를 푸는 방법을 배웁니다.

돌 게임(Subtraction Game), 님 게임 (Nim Game)을 푸는 방법을 배우고, The Sprague-Grundy Function을 이용해 조합 게임 문제를 푸는 방법을 배웁니다.

그 다음 다양한 님 게임 변형 문제의 Grundy Number를 구해봅니다

5. 다이나믹 프로그래밍 5

기댓값 DP와 DP 최적화 (Dynamic Programming Optimization)을 배웁니다.

DP 최적화에서는 Knuth Optimization, Divide & Conquer Optimization, Convex Hull Optimization을 배웁니다.

포함되어 있는 문제

1. 그래프 알고리즘 3

2. 다이나믹 프로그래밍 4

3. 문자열 알고리즘

4. 알고리즘 게임

5. 다이나믹 프로그래밍 5

01챕터: 그래프 알고리즘 3

오일러 회로맛보기00:12:25

SCC00:10:28

단절점, 단절선00:18:28

단절점, 단절선00:10:22

02챕터: 다이나믹 프로그래밍 4

문제 풀기 100:22:11

문제 풀기 200:12:29

문제 풀기 300:15:24

03챕터: 문자열 알고리즘

KMP00:14:05

KMP 문제 풀이00:11:10

Trie, Aho-corasick00:22:37

Suffix Array 100:13:53

Suffix Array 200:14:55

Suffix Array 300:12:28

04챕터: 알고리즘 게임

돌 게임00:11:02

님 게임00:08:49

Sprague Grundy Function00:09:06

05챕터: 다이나믹 프로그래밍 5

확률/기대값 다이나믹 100:11:39

확률/기대값 다이나믹 200:13:20

확률/기대값 다이나믹 300:06:40

확률/기대값 다이나믹 400:15:39

Knuth Optimization00:09:18

Divide & Conquer Optimization00:08:05

Convex Hull Optimization00:09:51

Problem Solving with Algorithms

(구) 알고리즘 고급