[회고] 06. WEEK05 알고리즘이 끝나고!

00. 코치님의 말씀

컴퓨팅 사고로의 전환 마지막 주가 지나고 있습니다. 어떠신가요? 이미 소프트웨어 개발자가 된 것 같나요? 아직 뭐가 뭔지 모르겠나요? 지금 쯤이면 검색해서 나오는 결과가 다 정답이 아니고, 어떤 글은 정말 형편없이 쓰여졌다는 것을 깨달으셨을거라 생각됩니다. 좋은 글과 글쓴이는 찾아내는 것도 이 지식 정보화 사회에서는 정말 중요한 능력입니다. 좋은 글, 좀 더 정확히는 나한테 맞는 정보 소스를 찾는 능력도 기르셨기를  바랍니다.

 

01. 알고리즘이 폭풍처럼 지나갔다!

5주의 시간이 지났다. 하루하루는 폭풍 같았고 되돌아보니 느리지만 천천히 시간이 지난 거 같다. 알고리즘 주차가 끝나가니 개발자에게 자료구조의 중요성에 대해 느끼게 되었다. 다양한 자료구조들이 있고 그것들을 적재적소에 쓸 수 있는게 정말 좋은 개발자의 자질이라 생각이 든다. 아직은 나 소프트웨어 개발자야!라고 당당히 말하지는 못할 것 같지만 언젠가... 스택, 큐를 자유자재로 써보고 시간 복잡도, 공간복잡도를 줄여보는 고민들을 할 때 당당히 나 이제 개발자 다 됐구나!라고 느낄 수 있을 것 같다.

 

02. 의장님의 말씀은 항상 옳은말만......

"항상 시간과 자원은 유한하다." 의장님이 티타임에서 말씀해 주셨다. 마지막 4주 차에 가장 와닿았던 말이다. 4주 차에는  csapp 책과 함께 알고리즘 문제를 풀었어야 했는데, CSAPP에 사용할 시간을 알고리즘에 모두 사용했다. 나에게 시간이 유한함에 한탄하며 잠을 최대한 줄였었는데, 결국 나의 체력에 늦잠 자고 후회하는 모습의 반복이었다. 그래서 내게 주어진 시간에 최선을 다하고 그 시간을 최대한 잘 활용해보려 한다. 

공부할 때도 습관을 고쳐야 한다. 이해가 안 되면 될 때까지 파보자 모르겠으면 혼자 하지 말고 같이하자 혼자보다 둘이 빠르고 둘보다 셋이 빠르다 이해한 건 정리하고 내 것으로 만들자! 남은 4개월도 할 수 있다!!

 

보고 또 볼 코치님의 말씀

• DFS는 재귀로 구현하면 매우 쉽게 구현할 수 있고 반복문으로 구현하려면 스택을 사용하면 됩니다.
• pre/in/post-order에 따라서 stack에 넣는 순서가 살짝살짝 바뀝니다.
• BFS를 구현할 때 큐(queue)를 사용하며, 큐를 priority queue로 바꾸면 Dijkstra 알고리즘이 됩니다.
• priority queue를 사용해서 항상 weight가 증가하도록 만든 것이기 때문에 edge weight가 음수가 되면 이 알고리즘이 제대로 동작하지 않습니다.
• 꼭 그래프가 아니더라도 평면 구조도 옆의 칸과 인접해 있다는 개념으로 graph로 생각할 수 있습니다.
• 1주차의 완전탐색 문제를 3주차에 다시 보면 문제의 graph를 탐색하는 방법으로 생각할 수 있다는 걸 깨달을 수 있습니다.
• 사실 recursive function의 호출 구조를 그려보면 tree 혹은 DAG (directed acyclic graph)가 됩니다.
• 그래프를 돌아다닌 경로를 최소화 하면 tree가 됩니다.
• minimum spanning tree와 all-pairs shortest path는 다릅니다.
• DP (dynamic programming)도 분할 정복을 구현하는 방법들 중 한 가지 방법이며, 따라서 재귀 함수로 구현하기 좋습니다.
• DP 문제를 단순 재귀 함수로 구현하면 같은 함수가 여러번 불리는 경우가 있으므로 한번 계산한 함수는 그 결과값을 저장하는 기법을 사용하는데, 그 기법을 memoization이라고 부릅니다.

---

3. DP에 대해서 좀 더 이야기 하자면...

• k-차원 array를 만들고 array를 채워 나가는 DP의 풀이 방식, 소위 bottom-up 방식의 풀이는 가끔 이해하기 어려운 경우가 있습니다.
• 사실 bottom-up 방식은 재귀를 이용한 top-down 방식을 (stack 없이) 반복문으로 만든 겁니다. 이렇게 만들어 놓고 보면 상당량의 최적화, 특히 공간 최적화를 더 할 수 있는 경우가 많기 때문에 이 방식의 풀이를 좋아하시는 분들이 계신데... 일단은 이해가 중요합니다. 이해 할 수 있는 풀이를 먼저 찾는 것을 권장합니다.
• Python은 cache decorator를 제공하여 top-down DP 구현을 쉽게 만듭니다. (function argument == array index)
• 사족으로 말씀드리면, Scala라는 언어는 아예 array index와 function argument의 표현 방식이 똑같습니다. (예: a(1) - array a의 2번째 내용일수도 있고, function a에 첫번째 argument를 1로 하여 호출한 결과일 수도 있음.)
• "점화식을 알면 DP를 쉽게 짤 수 있는데 점화식을 어떻게 만들지 모르겠다"라고 하시는 분들 계실텐데, 맞습니다. 점화식을 만드는 것 자체가 문제를 푸는 것이고, 좀 더 정확하게는 문제를 어떻게 잘 자를 수 있는가를 찾는 과정입니다. 사실 1주차 재귀, 2주차 분할정복에서부터 필요했던 능력입니다.
• 가끔 보면, 문제를 딱 보고 어떻게 자르면 되는지 알아차리기를 원하시는 분이 계시는데, 그 정도의 능력은 저는 재능의 영역으로 봅니다. 솔직히 이게 되면 못 풀 문제 없죠. 저는 특정 사람들만 알아듣는 말로 "직사의 마안"을 가졌다고 표현합니다. 그렇다고, 노력해도 기를 수 없는 능력이냐 하면... 뭐, 하다 보면 늘기는 합니다.
• Greedy로 풀 수 있으려면, "매 결정 단계에서 최선을 다 하면 global optimum에 도달할 수 있다"라는 증명이 되어야 합니다. 무조건 대충 최선을 구하도록 짜면 정답이 나오는 것이 아닙니다.
  
  

---

4.  지금까지 풀었던 문제들을 생각해 보면

• 일단 어떻게 풀어야 할지 잘 모르겠으면 답이 될 수 있는 모든 것을 다 해 봅니다. - brute force
• 문제를 자를 수 있으면 잘라 봅니다. - divide & conquer

• 문제를 자른 모양이 원 문제와 같은 모양이 되면 lucky 입니다. - recursion
• 똑같은 argument를 가진 recursive call이 많으면 caching 합니다 - memoization, top-down DP
• 문제를 반으로 자를 수 있으면 very lucky 입니다. log n 이 됩니다.

• recursive call 로 문제를 풀었는데 iteration으로 바꿔보니 쓸데없는 부분들이 보여서 optimize 합니다.
• 문제의 모양이 순서대로 처리하거나, 동굴 탐험처럼 들어갔다가 나왔다는 반복하는 모양이 보이면 queue나 stack을 사용할 수 있습니다.
• 관계(relation)이 있다면 graph로 표현할 수 있습니다.

• 관계들이 크게 하나로 되어있는지 조각조각인지는 connected component 수를 세어보면 압니다.
• 그래프는... 사실, 수도 없이 많은 응용방법이 있습니다.

 

뽕수작가님의 알고리즘 진도표 작품