author: wbjeon2k
MIT OCW 알고리즘 강의 추천
MIT Open Courseware (이하 MIT OCW) 는 Cousera와 Edx 보다도 더 오래된, 1세대 MOOC 사이트 입니다.
Cousera, Edx 등 interactive 한 자료를 제공하는 현대적인 MOOC 와는 달리, MIT 강의 자료들이 그대로 archiving 되어 있습니다.
그럼에도 불구하고, MIT OCW는 거의 모든 MIT 강의들의 강의 자료를 얻을 수 있다는 장점때문에 아직까지도 많이 이용되고 있습니다.
MIT OCW 에는 훌륭한 알고리즘 강의 자료들이 있습니다.
MIT OCW 에 있는 알고리즘 강의들이 어떤 것들이 있는지 소개드리고, 추천하고자 하는 이유를 말씀드리고자 합니다.
MIT 알고리즘 강의 구성
20210914 UPD
6.006 2020S YouTube 수업이 업데이트 되었습니다. 이전 6.006 은 2015년 버전 이었습니다.
2020년 버전은 2015년 버전 보다 Hashing 부분을 대폭 생략했고, 전체적인 난이도가 대폭 하향 되었습니다.
난이도와 범위 면에서 모두 다운그레이드 되어서 조금 더 개론에 가깝게 바뀌었고, DP 부분에서 새로운 예제들을 다룹니다.
전체적으로는 여전히 2015년 버전이 더 알차다고 생각합니다. 참고 바랍니다.
소개 드리는 강의들은 모두 YouTube에 녹화 강의 + 재생 목록이 있습니다!
6.006, 6.046j 참조 바랍니다.
MIT에서 학부생들을 대상으로 열리는 알고리즘 강의는 총 두 가지가 있습니다.
첫 번째 강의는 Introduction to Algorithms, 강의 번호는 6.006 입니다.
두 번째 강의는 Design and Analysis of Algorithms, 강의 번호는 6.046J 입니다.
두 과목 모두 제목이 기므로, 아래에서는 과목 번호로 지칭하겠습니다.
tmi: MIT EECS 강의들은 6.xyz 로 시작합니다. MIT OCW 이용시 참고 바랍니다.
6.006 Introduction to Algorithms
알고리즘 개론 이라고 되어 있지만, 초보적인 내용을 다루지 않습니다. 보통 모든 학교들의 ‘알고리즘’ 수업들과 구성이 동일합니다.
CLRS 를 바탕으로 진도를 나가며, 이는 많은 학교들과 유사합니다.
UNIST 알고리즘 강의 또한 CLRS를 사용하고 있습니다.
6.046 Design and Analysis of Algorithms
앞서 소개한 6.006 의 후속 수업입니다.
6.006 에서 배운 내용들을 조금 더 심화해서 배우는 과목입니다.
CLRS를 텍스트로 많이 쓰지 않고, 자체적으로 만든 lecture note 를 사용합니다. OCW에 모두 있습니다.
과목별 장점
각 과목은 목적과 수준이 다른만큼, 서로 다른 장점을 가지고 있습니다.
각자의 장점에 대해서 설명 드리도록 하겠습니다.
6.006 Introduction to Algorithms
6.006 강의의 장점은 문제에 대한 관찰력 제공 입니다.
UNIST 뿐만 아니라, 많은 일반적인 학교들의 알고리즘 강의는 CLRS 등 텍스트를 쫓아가기 바쁩니다.
많은 학교들은 커리큘럼에 알고리즘 강의를 한 번만 넣는 경우가 많기 때문에, 한 번의 과정에서 많은 주제들을 다루기 때문입니다.
따라서, 많은 알고리즘 강의들은 CLRS 를 줄줄 읽는 식으로 진행 됩니다.
X 알고리즘은 무엇을 하고, Y 알고리즘은 무엇을 하고…
이런 단순한 정보의 나열을 쫓아가면서 시험 2번 보면 학기가 끝이 나는게 보통입니다.
우리가 알고리즘을 배우는 목적은 문제를 해결하기 위한 방법 을 배우는 것입니다.
문제를 해결하기 위한 방법을 배우는것은 알고리즘 PS를 즐기는 Almight 회원분들의 목적과 일치합니다.
하지만, 문제를 해결 하기전에 더 중요한것은 문제를 관찰 하는 능력입니다.
6.006 강의는 문제를 관찰하는 다양한 관점을 제공하는 점에서, 다른 알고리즘 강의들 보다 훨씬 가치가 있습니다.
6.006 강의는 Erik Demaine 교수가 진행합니다. 엄청난 천재로 유명한 사람입니다.
천재들은 문제를 다양한 각도에서 관찰하는 능력을 선천/후천적으로 가지고 있습니다. 개인적으로 참 부럽습니다.
Erik Demaine 교수는 어떤 주제를 다른 주제와 즉흥적으로 연결시키는 것을 좋아합니다.
그리고 즉흥적으로 툭툭 던지는 멘트들 사이에서 저 같은 일반인들은 쉽게 떠올리기 힘든 개념들을 주워갈 수 있습니다.
가장 대표적으로 장점이 드러나는 부분은 DP 파트 입니다.
DP 개념을 설명하면서 그림을 그리더니, 갑자기 DP는 DAG 에서의 최단거리를 구하는 문제와 같다는 것을 보여줍니다.
너무 자연스럽게 설명을 하더니, 자기도 방금 처음 생각해봤다는 놀라운(?) 고백을 합니다.
저는 DP 를 처음 배웠을 때, memoization에 현혹되어서 그래프와 DP를 연결지어 생각하지 못했고, 꽤 오랜 시간이 지나서야 알게 되었습니다.
6.006 DP 수업을 들으면 단 15분 만에 알아갈 수 있으니, 엄청난 시간 절약이라고 생각합니다.
6.046 Design and Analysis of Algorithms
6.046 강의는 6.006의 후속 강의입니다.
6.006 에서 배운 알고리즘을 실제로 응용하는 과목입니다.
6.046 강의의 최대 장점은 PS 와의 높은 연관성 입니다.
6.046 에서 다루는 강의 주제들 중에는 PS 에서 아주 유명한 주제들이 많습니다.
많이 쓰여서 유명한 주제들도 있고, 악명 높기로 유명한 주제들도 있습니다.
PS와 관련도가 높은 주제들은 다음과 같습니다.
Convex Hull
FFT(Fast Fourier Transform)
Matrix Multiply
Range Trees(a.k.a **Segment Trees**)
Advanced DP
Greedy Algorithm, MST(Minimum Spanning Tree)
MCMF(Maximum Flow, Minimum Cut)
거를 타선이 없다…
여기 소개된 주제들은 난이도가 꽤(상당히) 있으면서도, 문제들이 아주 많이 있는 주제들 입니다.
solved.ac 에서 해당 태그들을 검색해서 확인할 수 있습니다.
사실 위에 소개된 주제들은 kks227 같은 PS 고수분들의 블로그를 보고도 충분히 배울 수 있습니다.
PS 만을 목적으로 한다면 6.046는 좋지 않은 선택입니다.
다만 6.046 강의가 PS 블로그들 보다 점하는 우위는 조금 더 탄탄한 이론적 배경 설명 입니다.
PS 자료들은 어떤 알고리즘을 소개하고 바로 문제 해결을 위한 적용으로 넘어가지만,
6.046 강의는 조금 더 이론적인 배경 소개를 충실히 한다는 장점이 있습니다.
정리하면서
위 두 개의 자료들을 모두 마스터 하는건 (매우) 어려운 일입니다.
필자인 저도 못했습니다.
아마 위 내용들을 모두 마스터 하면 ICPC 월파, Codeforce 레드 정도 수준이라고 생각합니다.
하지만 PS 자체를 즐기는 사람이라면, 한 번 쯤은 들어 볼만한 자료라고 생각합니다.
읽어주셔서 감사합니다.
ps. 1주차 코드리뷰를 진행하다가 생각이 나서 적어봤습니다.
앞으로도 Almight 블로그에 글이 많이 올라왔으면 좋겠습니다!