드디어 백준 알고리즘 고급 강의 수강이 끝났습니다.
방학동안 알고리즘을 더 효율적으로 공부하기 위해 12월 31일 오후 11시쯤에 결제를 하고 듣기 시작했습니다. 1달동안 많은 것을 배웠습니다.
이 강의는 크게 5개의 챕터로 구성이 되어있습니다.
1. 그래프 알고리즘
처음에 오일러 회로에 대해 간단하게 배웁니다.
다음으로는 DFS-Tree를 이용해 그래프의 간선을 4가지(tree, back, front, cross edge)로 분류하는 방법을 배웁니다. 이렇게 분류한 간선들의 정보를 이용하여 SCC, 단절점, 단절선에 대해 배우고 다양한 문제들의 풀이들도 함께 배울 수 있습니다.
마지막에는 SCC를 이용한 2-SAT문제에 대해 배우게 됩니다.
2. DP 4
알고리즘 고급 강의 외에도 여러 가지 강의가 있는데, 그 곳에서 1~3을 다루고 이 강의에서는 4, 5를 다룹니다.
처음에 TreeDP문제를 풀어보고, 왼쪽과 오른쪽을 나누어 보면서 DP Table을 채우는 것, 왼쪽과 오른쪽으로 한 칸씩 뻗어나가며 DP Table을 채우는 것 등 다양한 종류의 DP문제에 대한 풀이를 들을 수 있습니다.
3. 문자열 알고리즘
KMP알고리즘으로 시작해서 Trie, Aho-Corasick, Suffix Array와 같은 문자열 알고리즘을 배웁니다.
각 알고리즘을 배운 뒤에는 바로 해당 알고리즘을 이용한 문제도 함께 풀어볼 수 있습니다.
4. 알고리즘 게임
Combinatorial Game 중에서 Impartial Game 문제를 다루는 챕터입니다.
유명한 조합 게임인 돌게임과 님게임을 풀어본 뒤, Sprague-Grundy Function에 대해 배워봅시다.
5. DP 5
확률/기댓값DP와 DP최적화 기법을 다룹니다.
앞부분에서는 다양한 기댓값DP문제를 풀어본 뒤, 뒷부분에서 3가지의 DP최적화 기법(Knuth-Opt, DnC-Opt, CHT)를 배우게 됩니다.
이 강의에서 가장 관심이 있던 부분은 그래프와 DP최적화였고, 그래서 결제하자마자 바로 들었습니다.
아직 그래프 알고리즘 챕터에서 다룬 문제 몇 가지와 Suffix Array는 완벽하게 이해가 가지 않았기 때문에, 강의에서 제공해준 pdf를 이용해 나중에 다시 공부해볼 계획입니다.
지금까지 2개의 알고리즘 학원을 다녔었습니다. 집 주변에 있는 학원에 1달 다녔었고, 목동/대치에 있는 학원에 1년 다녔습니다.
이 강의와 학원을 비교해보면, 이 강의가 훨씬 좋고 가격이 3배에서 4배 가깝게 쌉니다. C++을 어느정도 알고 있다면 학원 대신 code.plus 에서 인강을 듣는것이 훨씬 좋다고 생각합니다.
다만 이 강의에 대해 약간 아쉬운 점이 있다면 알고리즘의 정당성에 대한 증명이 없다는 것입니다. 정당성에 대한 증명을 알아보는 것도 재미있어 하는 사람으로써, 이 부분에 대해서는 꽤 아쉽습니다.
나중에 더 깊은 내용을 다루는 강의가 나오게 된다면 또 들어보겠습니다.