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언어로 풀어보는 즐거움은 보너스.

그로스 아이큐

경영 전략에 대해서는 아직 관심이 크지 않아서 끝까지 읽진 않았다.

핵심 아이디어만 추려보면 아래와 같다.

기업이 성장하기 위해서는 현재 상황에 맞는 여러 전략(성장 경로)을 선택하여 최적의 타이밍에 최적의 순서로 실행해야 한다. 단 하나의 방법은 존재하지 않는다.

여러 기업의 성장을 성공적으로 이끌어내고 있는 저자 티파니 보바는 이 책에서 10가지 성장 경로를 제시하고,

  1. 고객 경험
  2. 고객층 침투
  3. 시장 가속화
  4. 제품 확장
  5. 고객, 제품 다각화
  6. 판매 최적화
  7. 고객 이탈 최소화
  8. 제휴 관계
  9. 협조적 경쟁
  10. 비인습적 전략

각 성장 경로별로 실제 기업의 사례를 3가지씩 소개한다. 특정 기업의 사례가 특정 성장 경로 아래 놓여 있지만, 읽어보면 여러 성장 경로를 동시에 혹은 순차적으로 추진한 것을 알 수 있다.

한 사람의 삶을 경영할 때도 같은 아이디어를 적용해볼 수 있을 것 같다. 과거에 통했던 방법이 현재에도 유효하리란 보장이 없기 때문에, 현재의 상황을 면밀히 분석하여 효과적인 행동들을 신중히 선택하고 우선순위, 타이밍, 순서를 고려하여 실행해야 한다.