w04화 알고리즘 관련 정주원 코치님의 슬랙 메시지 모음

내일 모레면 4주에 걸친 알고리즘 주간이 끝난다. 이제 C 실습에 들어갈 것이다. 여태 알고리즘과 관련한 통찰에 대해 계속해서 인라이트닝해주시는 부분이 좋았으므로 기록해둔다.

3월 8일 오후 5시경

지난 W01 발제 때 영어가 가능하면 leetcode를 참조해 보라고 말씀드렸습니다.
그 예시를 말씀 드립니다. (이미 찾아서 활용한 분들도 계실것이라 생각합니다.)

• 9663 N-Queen: 52. N-Queens II 와 같은 문제입니다. Solutions를 통해 다양한 풀이 방법을 관찰할 수 있으며, 선행 문제인 51. N-Queens 를 통해 구체적으로 어떤 말 배치들이 가능한지 만드는 경우도 알아볼 수 있습니다.
• 2750, 2751, 10989 수 정렬하기 1, 2, 3: 912. Sort an Array 의 Editorial과 solutions 에서 각종 정렬 알고리즘의 전략과 장단점, 특징들을 알아볼 수 있습니다. leetcode 912번 문제는 백준 2751과 거의 동일합니다.
• 14888 연산자 끼워넣기: 282. Expression Add Operators 가 똑같은 문제는 아니지만 풀이 방식은 동일합니다.

leetcode 뿐 아니라 다른 정보도 참조할 수 있습니다.
여러분들의 학습 능력 향상에 도움이 되길 바랍니다.

3월 16일 오후 6시경

컴퓨팅 사고로의 전환도 3주차에 접어들었습니다.
어떠신가요? 컴퓨터에게 내가 원하는 대로 일처리를 시키기 쉬워 지셨나요?

1. 혹시 아직도 뭐가 뭔지 모르겠다면

내가 생각한 것을 프로그램으로 만들 수 있는지 자기 자신에게 질문해 보십시오.
이 과정의 가장 근본적인 목표는 내가 원하는 작업을 컴퓨터에게 시키는 능력을 키우는 것입니다.
일단, 내가 원하는 것을 컴퓨터에게 쉽게 시킬 수 있다면 잘 따라가고 있다고 생각합니다.
미래에 내가 원하는 것, 해내야 할 작업이 뭐가 될지 모르기 때문에 정형화된 문제들로 연습하는 것이고
이왕이면 효율적으로 빠르게 컴퓨터에게 일을 시키기 위해
계산 복잡도를 고려하고, 문제 유형을 나누어 익히고,
정해진 시간 안에 프로그램을 짜는 연습을 하는 것입니다.

2. 재귀 함수 (recursive function)를 만드는 것에 익숙해지면 매우 유용하게 쓰실 수 있습니다.

재귀 함수라는 말은 처음 듣겠지만, 보다보면 고등학교때 수열의 점화식이 떠오르시는 분들 계실 겁니다.
네, 맞습니다. 기본 아이디어는 수학적 귀납법을 사용하는 것이고, 고등학교 수열과 다른 점이라면 점화식에서 일반식을 내가 계산하지 않아도 컴퓨터가 대신 몇번째 숫자가 몇인지 계산해 준다는 점이 다릅니다.

혹시 기억 못하시는 분들을 위해

• 점화식: $a_{k+1} = a_{k} + 1, a_1 = 1$ 와 같이 다른 수와의 연관을 표현한 식
• 일반식: $a_{n} = n$ 와 같이 일반적인 함수 형태로 나타낸 식

2주차에서 분할정복 문제를 풀고 2주차 시험문제 1번을 풀면서 느끼셨겠지만, 분할정복 문제는 재귀함수로 구현하면 틀리지 않게 구현하기 좋습니다. 그리고, 분할정복(divide and conquer)이라는 전략은, 사실상 거의 모든 문제를 푸는데 적용할 수 있는 기초 전략이기도 합니다.

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

• 분할 정복은 재귀함수로 구현하기 좋습니다.
• 이분 탐색은 분할 정복의 한 가지 방법입니다.
• 재귀 함수를 반복문(loop)으로 바꿀 때 스택을 사용하면 쉽게 바꿀 수 있습니다. (문제에 따라서는 스택을 안 쓰고도 바꿀 수 있습니다.)
• 반대로 반복문은 재귀 함수로 바꿀 수 있습니다. loop 변수를 재귀 함수의 argument로 쓰면 쉽게 만들 수 있죠?
• 정수론이란 키워드는 우리가 다루는 문제는 정수(integer)밖에 다루지 않을것이라는 암시를 줍니다. 정수는 수의 극히 일부분이므로 수학의 아주 작은 부분만 활용하게 됩니다.
  • 참고로, 여러분의 computer에게 0.1 + 0.2를 연산하라고 하면 뭐라고 답하는지 확인해 보십시오. 왜 그런지 파헤치기 시작하면 시간낭비일 수 있으니, 그냥 "2진수와 10진수의 차이와 용량의 한계 때문이다" 정도로만 알고 계십시오. (IEEE 754를 보는 시간에 차라리 2's-complement를 이해하는 것이 낫고, 2's-complement를 이해할 시간에 다른 알고리즘을 이해하는 게 지금은 효율적이라고 봅니다.)

각각의 풀이 방법을 외우려고 하지 않고 이런 연관성을 가지고 보면, 컴퓨터로 풀 수 있는 문제의 모양을 보는 데 도움이 되리라고 생각합니다.
과연 이번 주의 그래프 문제들은 지난 주의 키워드들과 어떤 연관성을 가지고 있을까요?

4. 주어진 시간 안에 문제를 푸는 연습을 추천합니다.

• 주어진 시간이라는 압박 하에 푸는 연습을 한 것과 안한 것의 차이가 있다고 생각합니다.
• 시험 시간에 한 문제도 못 푸는 분들은 난이도, 하, 중 문제를 늦어도 30분 안에는 구현하도록 연습하시는 것을 추천합니다. (이미 아는 문제부터 연습해 보세요)
• 4개월 후에는 난이도 하 문제는 5~20분 안에 풀 수 있도록, 문제를 읽고 30초 안에 풀이 방법을 말할 수 있도록 훈련 되어있는 것이 좋습니다.
  • 이 과정이 코딩 테스트를 위한 과정은 아닙니다만, 주어진 시간 안에 푸는 연습이 안되면 코테나 면접에도 도움이 안 됩니다.
  • 칠판 코딩 면접을 생각해 보면, 면접관이 질문했는데 30초를 기다려도 답을 들을 수 없다면 다음 문제로 넘어갈 수 밖에 없습니다.
  • 현실적으로 면접에서 한 문제에 30분 이상을 할애하기 어렵습니다.

도움되시길 바랍니다.

3월 28일 오후 2시경

컴퓨팅 사고로의 전환 마지막 주가 지나고 있습니다.
어떠신가요? 이미 소프트웨어 개발자가 된 것 같나요? 아직 뭐가 뭔지 모르겠나요?

1. 지금 쯤이면 검색해서 나오는 결과가 다 정답이 아니고, 어떤 글은 정말 형편없이 쓰여졌다는 것을 깨달으셨을거라 생각됩니다.

좋은 글과 글쓴이는 찾아내는 것도 지식 정보화 사회에서는 정말 중요한 능력입니다.
ChatGPT가 제대로 답을 하는지 자기 나름대로 소설 쓰면서 헛소리를 하는지 알아볼 수 있어야 ChatGPT도 쓸 수 있습니다.
좋은 글, 좀 더 정확히는 나한테 맞는 정보 소스를 찾고, 내가 알게 된 것을 차곡차곡 쌓아 올리는 능력도 기르셨기를 바랍니다.

2. 지난 주와 이번 주의 keyword 들은 어떤 관계가 있었는지 생각해 보셨나요?

• 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 very lucky 입니다. O(log n) 이 됩니다.
• recursive call 로 문제를 풀었는데 iteration으로 바꿔보니 쓸데없는 부분들이 보여서 optimize 합니다.
• 문제의 모양이 순서대로 처리하거나, 동굴 탐험처럼 들어갔다가 나왔다는 반복하는 모양이 보이면 queue나 stack을 사용할 수 있습니다.
• 관계(relation)가 있다면 graph로 표현할 수 있습니다.
  • 관계들이 크게 하나로 되어있는지 조각조각인지는 connected component 수를 세어보면 압니다.
  • 그래프는... 사실, 수도 없이 많은 응용방법이 있습니다.

다음 주 부터는 다른 과정이 시작됩니다.
컴퓨팅 사고로의 전환 마무리 잘 하시길 바랍니다.