[Coursera] Algorithms, Part I 수강 후기

 

Kevin Wayne, Albert Sedgewick 의 Algorithms, Part 1

 

저번주 월요일에 Princeton 의 Algorithms, Part 1 과정을 마쳤다. 이 과정은 Coursera 에 있으며 과거(대략 2010년대로 추정)에 촬영한 영상을 온라인으로 수강 할 수 있다. 또한 이 강좌는 Robert Sedgewick 의 Algorithms 책의 내용을 두 부분으로 나누어 Part 1, Part 2 로 제공하고 있다. 강의를 수강하게 된 계기는 코드숨에서 시작한 알고리즘 스터디로 인해서였다. 스터디 시작 전에 해당 강의에 대한 이야기가 나왔는데 강의까지 들어두면 좋을 것 같아 시작하게 되었다. 

 

해당 강의의 특징을 꼽자면 프린스턴에서 자체적으로 개발한 라이브러리를 기반으로 코드를 작성하기 때문에 알고리즘 작성에 있어서는 FAQ 에 있는 답변 및 API 공식 문서의 도움을 받을 수 있다는 점과 강의마다 알고리즘을 시각화하여 보여주기 때문에 내용을 이해하기에 용이하다는 점이다. 그리고 이 강의에 대해 이야기를 시작하면 거의 모든 사람이 과제에 대한 이야기를 할 것 같은데, 그만큼 과제가 중요하고 많은 시간을 할애해야 한다. 그러므로 과제에 시간을 많이 쏟을 수 있는 사람이 수강하는 것을 추천한다. 주에 1~3 개의 클래스를 작성하는데, 개략적으로 주당 15시간 가량 걸렸던 것으로 기억한다. (대부분의 시간은 이론을 이해하는데 소요되었다) 

 

이 강의를 들으면서 좋았던 부분을 꼽자면 Robert Sedgewick 교수가 직접 Red-Black Tree 에 대한 이야기를 했다는 것이다. 정말 이해하기 쉽게 말씀하셔서 감탄했다. 그리고 알고리즘을 직접 만든 사람들의 일화들을 들을 수 있어서 좋았다. 

 

과제의 시작은 정말 무서웠다. 첫 번째 과제는 `Permutation` 에 대한 내용이었는데, 이 과제를 기준으로 수료의 여부가 갈렸을 것 같다는 생각이 들 정도로 무서운 내용의 과제였다. Union-Find 을 이용하여 각 site 의 무작위로 열림을 고려해야 하는데 과제를 여러 번 읽고서야 과제의 의도를 이해했다. 그리고 과제는 몬테카를로 시뮬레이션을 기반으로 작성해야 했는데 이 시뮬레이션을 이해하는 데에도 많은 시간이 소요되었다. 그러나 시뮬레이션을 작성하는 데에는 오랜 시간이 소요되지 않았다. 

 

두 번째 과제는 자세히 생각이 나지 않는다. (띠용) `Deque` 와 `RandomizedQueue` 의 내용을 작성해야 하는 코드였는데, 해당 데이터 스트럭쳐를 작성해야 했던 것으로 기억한다. 연결 리스트를 활용해야 했다.

 

세 번째 과제는 미완성이다. 당시 시간이 너무 없어서 제대로 완성하지 못했고, 과제를 통과할 정도로만 작성해서 제출했던 기억이 난다. `Collinear` 에 대한 내용이었는데, 점들의 집합에서 선을 인식하는 프로그램을 작성하는 내용이다. Point 에서 평면의 점을 나타내고, LineSegment 에서 평면에서 선분을 나타내는 API 를 작성하고, BruteCollinearPoints 는 4개의 점을 검사해서 동일한 선분에 있는지 확인하는 내용이 들어가고, FastCollinearPoints 는 BruteCollinearPoints 의 향상된 버전으로 slope 를 기준으로 점의 상태를 계산하는 방향으로 작성해야 한다. 아무튼 작성해야 할 것도 많고 생각해야 할 것도 많은 내용이었다.

 

네 번째 과제는 `8 Puzzle` 에 대한 내용이었는데, 퍼즐 게임의 구현이다. hamming() 으로 잘못된 위치에 있는 타일의 개수를 반환하고, manhattan() 로 타일들이 목표 위치까지의 manhattan 거리의 합을 반환한다. 아무튼 이 과제는 주로 타일의 위치와 이동 가능한 상태, 그리고 목표에 도달하였는지 확인하는 등의 기능을 작성해야 했다.

 

다섯 번째 과제는 `Kd Trees` 에 대한 내용인데, 2차원 트리를 구현하는 두 가지 데이터 타입을 작성하는 과제였다. 하나는 Brute Force 으로 작성하고, 다른 하나는 2d-Tree 를 활용해 작성하면 되는 내용이다. 

 

지금 드는 생각은 `Part 2 를 들을 수 있을까 ?` 이다. 과제를 제출하는 순간은 정말 좋았는데 거기까지의 과정이 너무 고통스러웠다. 회사 다니면서 스터디에 참여하는 것도 시간이 빠듯한 일인데 해당 강의까지 들으며 과제를 제출하려니 5주간 공부를 제외하고 다른 일은 할 수가 없었다. Part 2 수강은 코드숨 알고리즘 스터디 중반 즈음 다시 생각해봐야겠다.

 

 

작성한 소스는 다음 레파지토리에 있다. 

소스 : https://github.com/caoyu-dev/Algorithms_Part_I

GitHub - caoyu-dev/Algorithms_Part_I

 

강의 : https://www.coursera.org/learn/algorithms-part1

Algorithms, Part I