Divide and Conquer, Sorting and Searching, and Randomized Algorithms 강의 수강 후기

Coursera Standford University Algorithms 분야의 첫 번째 강의인 Divide and Conquer, Sorting and Searching, and Randomized Algorithms의 수강을 완료했다. 수강 기간은 2019년 12월 17일 ~ 2020년 1월 12일.

  1. Divide and Conquer, Sorting and Searching, and Randomized Algorithms
  2. Graph Search, Shortest Paths, and Data Structures
  3. Greedy Algorithms, Minimum Spanning Trees, and Dynamic Programming
  4. Shortest Paths Revisited, NP-Complete Problems and What To Do About Them

Tim Roughgarden 교수님 알고리즘 강의의 좋은점은 특정 패러다임(e.g., Randomized Algorithms)으로 분류되는 알고리즘(e.g., Random Contraction Algorithm)들 중 한 두개를 선택하여 동작 원리와 실행시간 분석을 증명을 포함하여 깊이있게 설명해준다는 점이다.

Divide and Conquer 알고리즘의 경우 알고리즘의 실행시간(~ # of lines of code)을 분석할 때, Recursion Tree 또는 The Master Method를 활용할 수 있는데, 매우 유용한 The Master Method를 처음 접했다는 사실이 의아했다. (학부, 대학원 때 수업을 아무리 대충 들었더라도 기억에 아주 없지는 않을텐데…)

The Master Method

Randomized 알고리즘을 분석하기 위해서는 Probability Theory의 몇 가지 기본 개념(Sample Space, Event, Random Variable, Expectation, Linearity of Expectation, Conditional Probability)들을 이해해야 한다. 이 역시 배운 기억이 없는…

Probability Theory를 활용한 QuickSort 실행시간 분석과정

증명 과정에서 특정 항을 같은 값을 가지는 다른 항으로 대체하거나, 특정 수식을 수학적으로 증명된 수식으로 대체하는 부분이 흥미로웠다.

Randomized Slection 알고리즘의 실행시간 분석과정에서, 재귀호출에 대한 기대값을 동전 던지기에 대한 기대값으로 치환

Karatsuba 알고리즘이나 Strassen 알고리즘처럼 변형된 수식을 도입하여 재귀 호출의 수를 줄이는 아이디어도 기억해두면 좋을 것 같다.

Strassen’s Algorithm

Programming Assignment #1~4는 모두 Go언어로 풀었는데 재밌었다. Go언어에 익숙하지 않아서 시간이 오래 걸리기도 하였지만, 그만큼 Go언어 코드 작성 능력을 향상시킬 수 있는 좋은 기회였다. 간단한 알고리즘 코드를 작성할 때도 상위 레벨에서 필요한 인터페이스를 먼저 설계하고, 그 인터페이스를 효율적으로 구현할 수 있는 자료구조를 선택하고, 인터페이스를 구현한 다음 유닛 테스트까지 꼭 작성해야 한다는 교훈을 얻었다. Random Contraction 알고리즘을 구현할 때 그래프 자료구조를 몇 번씩이나 다시 구현하게 된 원인은 그래프에 필요한 모든 인터페이스들을 종합적으로 고려하지 않았기 때문이었다.

매주 풀어야했던 Problem Set #1~4는 어려웠다. 뒤로 갈수록 점점 더 어려워져서 Final Exam 통과할 수 있을까 걱정이 컸는데, 다행히 Final Exam은 쉽게 나와서 한 번에 통과할 수 있었다. 영어가 부족하니 문제를 해석하는 것부터 버거운 경우도 있었고, 수학이 부족하니 수식을 다 세워놓고도 log 계산을 못해서 정확히 답을 도출하지 못하기도 했다. 때로는 자괴감을 느끼기도 했다.

가장 큰 소득은 실력이 부족하다는 것을 알게 된 것. 다음은 Divide and Conquer, Randomized 패러다임의 알고리즘을 설계할 때, 실행시간을 분석할 수 있는 수학적 도구를 얻게 된 것.

두 번째 강의는 구정 연휴 지나 1월 마지막 주에 시작할 예정이다. 그 사이에 수학의 기본기를 다질 수 있는 책을 찾아 보아야겠다.

Coursera에서 알고리즘 수업 듣기

Coursera에서 Standford 대학의 알고리즘 강의를 듣고 있다. 수학, 영어 기본기가 부족하여 버겁다는 생각을 자주 하지만, 얻는 것이 많아서 꾸역꾸역 해내고 있다.

  • 중간 관리자 역할을 3년 동안 하면서 굳었던 머리를 말랑말랑하게
  • 기술 주제에 대한 영어 듣기 능력 향상
  • 알고리즘 문제 풀이 및 코딩(a.k.a. Problem Solving)에 재미를 붙이기 위한 준비 단계

알고리즘은 대학교, 대학원 과정에서 가장 어렵고 피하고 싶은 과목이었고, 고등학교 때도 수학을 그다지 좋아하지 않았다. 이 강의를 들으면서 알고리즘과 알고리즘을 설명하는데 필요한 수학이 가진 가치를 느끼고 난 후에는 생각이 많이 바뀌었다.

가장 큰 소득은 2012년 G사의 코딩 인터뷰 1차에서 떨어진 이유를 깨닫게 된 것이다. 인터뷰어는 수식으로 알고리즘의 타당성을 설명해주길 기대했는데, 이 강의에서 반복되는 과정이 바로 그것이다. 그때의 나는 시그마 기호조차 제대로 사용하지 못했다.

매주 코딩 숙제를 Go언어로 풀어보는 즐거움은 보너스.

AWS Solutions Architect Associate 시험 후기

7월 7일에 시험을 예약하고 8월 4일에 강남역 1번 출구 쎄임페이지에서 시험을 보았다.

100일 안 된 딸을 키우는 과정에 있었고 회사 일도 만만치 않았기 때문에 공부할 시간을 내기가 쉽지 않았다. 시간도 시간인데 매일 밤 육아퇴근 후에는 에너지가 부족해서 제대로 공부를 할 수 없었다. 대부분의 공부는 주말 아침 7시에 도서관에 가서 1시간 30분 정도 연습문제를 풀고 집으로 돌아와 집안일, 육아 중 틈틈히 문제해설과 AWS 문서를 읽으며 개념을 정리하는 식으로 이루어졌다. 시간이 부족해서 중간에 휴가를 하루 사용하기도 했다.

https://www.whizlabs.com/aws-solutions-architect-associate/

Whizlabs의 연습문제를 유료결제($19.95) 후 이용했다. 60문제로 구성된 시험 7개를 풀어볼 수 있는데, 영어로 된 60문제를 쉬지 않고 한 번에 푸는 것은 꽤나 집중력을 요하는 일이라 처음에는 쉽지 않았다. 문제를 다 풀고나면 해설을 확인할 수 있는데, 문제와 관련된 AWS 문서 내용과 링크가 있어서 좋았다. 해설을 읽으며 새롭게 알게된 내용은 개인 Confluence에 정리했고, 시험 3일 전부터는 정리해 놓은 내용을 빠르게 다시 읽으며 머리 속에 흩어져있던 개념들을 재정렬했다.

초반에 생소한 문제들이 줄지어 나왔고 컨디션 난조로 영어도 눈에 잘 안 들어와서 당황했다. 시간은 흘러가고 진도는 나가지 않았다. 30분 추가 시간을 신청하지 않은 것을 후회했다. 다행히도 뒤로 갈수록 단답형 문제들, Whizlabs에서 풀어본 것과 같은 문제들이 나오면서 여유를 찾을 수 있었다. 어려운 문제는 우측 하단 Flag 버튼을 이용해 표시해 놓으면 나중에 다시 풀어보기 좋은데, 20문제 넘게 푼 후에야 이 버튼을 발견해서 아쉬웠다. End Test 버튼을 누르기 전에 합격을 예상했고, 다행히 예상은 틀리지 않았다.

원하는 결과를 얻었지만 아쉬움은 남았다. 분명 시험을 준비하는 과정을 통해 AWS를 더 많이 알게 되었지만, 시험을 통과하기 위한 요령을 부린 것에 지나지 않았기 때문이다. 현업에서 사용해본 서비스의 종류는 EC2, RDS, API Gateway, Lambda 정도로 굉장히 한정적이고 실제로 리소스를 생성하고 설정하는 일은 다른 팀에 의해서 이루어지다보니 진짜 경험이 많이 부족했다.

11월 말에는 Professional에 도전할 생각이다. 이번에는 시험 통과를 위한 공부가 아닌, 진짜 실력을 갖추기 위한 공부를 제대로 해보려고 한다.

영어책 필사

오래 전에 구입해놓고 읽지 않았던 마지막 강의 영한대역 책을 펼쳐 필사를 시작했다.

하루에 한 페이지, 느리지만 꾸준히

만년필을 쓰는 재미는 또 하나의 덤

한 문장씩 외워서 쓰려고 노력하다보면 영어 문장을 어떻게 구성해야 하는지, 어떤 상황에서 어떤 시제와 어떤 전치사를 사용해야 하는지 조금씩 알게 된다.

이 책을 쓴 랜디 포시 교수님이 재직했던 CMU에서 5주 동안 공부한 경험도 있고,

YouTube에서 마지막 강의 동영상도 인상 깊게 보아서,

책에 담긴 그의 이야기가 더 가깝게 느껴진다.

많은 사람들의 존경을 받았던 한 사람으로부터 배울 수 있어서 필사는 나에게 단순한 영어공부보다 더 의미가 큰 작업이다.

올해는 영어를 공부하는 게 아니라 익히고 싶다. 그래서 한 권의 책, 한 편의 영화를 반복해서 보면서 나에게 필요한 표현들을 습득하려고 한다. 멀지 않은 미래에 영어를 읽고, 쓰고, 말하는데 큰 어려움을 느끼지 않기를 바라며…