코치님 말씀

컴퓨팅 사고로의 전환 마지막 주가 지나고 있습니다.

어떠신가요? 이미 소프트웨어 개발자가 된 것 같나요? 아직 뭐가 뭔지 모르겠나요?

1. 혹시 아직도 뭐가 뭔지 모르겠다면 내가 생각한 것을 프로그램으로 만들 수 있는지 자기 자신에게 질문해 보십시오.

이 과정의 가장 근본적인 목표는 내가 원하는 작업을 컴퓨터에게 시키는 능력을 키우는 것입니다.

일단, 내가 원하는 것을 컴퓨터에게 쉽게 시킬 수 있다면 잘 따라가고 있다고 생각합니다.

미래에 내가 원하는 것, 해내야 할 작업이 뭐가 될지 모르기 때문에 정형화된 문제들로 연습하는 것이고 이왕이면 효율적으로 빠르게 컴퓨터에게 일을 시키기 위해 계산 복잡도를 고려하고, 문제 유형을 나누어 익히고, 정해진 시간 안에 프로그램을 짜는 연습을 하는 것입니다.

2. 눈치 빠른 분들은 알고 계시겠지만 각 주의 keyword 들은 서로 연관이 있습니다.

• 분할 정복은 재귀함수로 구현하기 좋습니다.
• 이분 탐색은 분할 정복의 한 가지 방법입니다.
• 재귀 함수를 반복문(loop)으로 바꿀 때 스택을 사용하면 쉽게 바꿀 수 있습니다. (문제에 따라서는 스택을 안 쓰고도 바꿀 수 있습니다.)
• DFS는 재귀로 구현하면 매우 쉽게 구현할 수 있고 반복문으로 구현하려면 스택을 사용하면 됩니다.
• BFS를 구현할 때 큐(queue)를 사용하며, 큐를 priority queue로 바꾸면 Dijkstra 알고리즘이 됩니다.
• DP(dynamic programming)도 분할 정복을 구현하는 방법들 중 한 가지 방법이며, 따라서 재귀 함수로 구현하기 좋습니다. (솔직히 점화식이 보이는데 이걸 깨닫지 못한다면...)
• DP 문제를 단순 재귀 함수로 구현하면 같은 함수가 여러번 불리는 경우가 있으므로 한번 계산한 함수는 그 결과값을 저장하는 기법을 사용하는데 그 기법을 memoization이라고 부릅니다.
• 1주차의 완전탐색 문제를 3주차에 다시 보면 문제의 graph를 탐색하는 방법으로 생각할 수 있다는 걸 깨달을 수 있습니다.

각각의 풀이 방법을 외우려고 하지 않고 이런 연관성을 가지고 보면, 컴퓨터로 풀 수 있는 문제의 모양을 보는 데 도움이 되리라고 생각합니다.

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

• k-차원 array를 만들고 array를 채워 나가는 DP의 풀이 방식, 소위 bottom-up 방식의 풀이는 가끔 이해하기 어려운 경우가 있습니다. 사실 bottom-up 방식은 재귀를 이용한 top-down 방식을 (stack 없이) 반복문으로 만든 겁니다. 이렇게 만들어 놓고 보면 상당량의 최적화, 특히 공간 최적화를 더 할 수 있는 경우가 많기 때문에 이 방식의 풀이를 좋아하시는 분들이 계신데... 일단은 이해가 중요합니다. 이해 할 수 있는 풀이를 먼저 찾는 것을 권장합니다.
• Python은 cache decorator를 제공하여 top-down DP 구현을 쉽게 만듭니다. (function argument == array index)