LoCeL
문제 해결 과정에서 항상 중시해야 할 것들 (1) 본문
우리는 살아가면서 수많은 문제를 마주하게 되고, 수많은 해법으로 문제들을 해결하게 됩니다. 모든 사람들은 그 종류에 관계없이, 문제를 해결하며 살아가고, 이왕이면 문제를 잘 해결하는 사람이 되고 싶습니다. 오늘 할 이야기는 알고리즘 문제 해결을 중심으로, 어떻게 생각하고 공부해야 문제를 잘 해결할 수 있는지, 최근 문제의 풀이법과 공부법을 바꾸면서 제가 느낀 것을 써 내려가 보고자 합니다. 물론 누군가에게는 아주 당연한 이야기가 될 수도 있고, 값진 이야기가 될 수도 있을 것 같습니다.
요즘 컴퓨터공학을 공부하는 사람이라면, 또는 그 분야의 직업을 갖고 싶은 사람이라면 알고리즘 문제 해결(이하 Problem Solving의 준말인 PS라 칭합니다)을 한 번쯤은 들어보거나, 경험해보았을 것입니다. 처음 공부를 시작할 때를 떠올려 봅시다. 책이나, 블로그의 내용을 순서대로 따라가며 배우는 경우가 대다수일 것입니다. 기본적인 알고리즘과 자료구조를 모두 공부하고 나면 배운 것을 응용할 수 있는 문제를 해결하거나, 더 어려운 새로운 알고리즘을 공부하곤 합니다. 어느 쪽이 더 낫다고 말할 수는 없습니다. 개인이 더 재밌고 도움이 될 것 같은 방향으로 나아가는 것이 공부니까요. 하지만 대부분의 목표는 같습니다.
문제를 잘 풀 수 있게 해 주세요...
모두의 염원입니다. 취업, 자기만족, 대회 입상 등 그 목적은 모두가 다르지만, 결국 이것으로 귀결됩니다. 하지만 문제를 정말 잘 푸는 사람이 되기란 어렵습니다. 공부를 충분히 했다는 생각이 들면, 자신의 실력이 궁금하여 코드포스 등의 대회를 나가곤 합니다. 그때마다 내가 기대한 만큼 문제를 해결하지 못하고, 나중에 풀이를 보면 생각보다 간단해서 아쉬웠던 적이 있을 것입니다.
분명히 책, 인터넷 등으로 알고리즘 공부를 열심히 했습니다. 그런데 왜 막상 문제를 보면 머리가 막막해지고 올바른 풀이와는 점점 거리가 멀어질까요?
주어진 이차방정식의 해를 구해야 하는 상황이라고 해봅시다. 아주 간단한 이 문제의 풀이 방법은, 생각보다 다양합니다. 수학을 공부해보신 분이라면, 곧바로 인수분해와 근의 공식을 떠올리실 것이고, 더 나아가 수치해석을 공부하셨다면, 뉴턴-랩슨 방법을 떠올리실 겁니다. 여기서 나온 수학 용어들은 문제의 분류와 풀이 방법 두 가지로 나눌 수 있습니다. 이차방정식의 해를 구하는 것이 바로 문제의 분류가 되고, 인수분해, 근의 공식 그리고 뉴턴-랩슨 방법이 곧 주어진 문제의 풀이 방법, 해법이 됩니다.
그렇습니다. 문제 풀이는 문제의 분류와 문제의 풀이 방법들을 미리 아는 것에서 출발합니다.
문제가 주어졌을 때, 어떤 문제인지 아는 것은 아주 중요합니다. 그러면 새로운 문제를 보아도, 기존에 풀어봤던 것들 중에서 똑같은 문제를 찾을 수 있고, 난이도가 다르게 체감이 되겠죠. 이미 풀이를 알고 있기 때문입니다.
그뿐만이 아니라, 문제의 특성, 성질을 관찰하고 분석하는 데에 있어, 어떤 문제인지 잘 파악하는 것은 항상 중요합니다. 그리고 문제의 풀이 방법을 아는 것이 중요하다는 사실은 아무래도 잘 아실 것 같습니다.
문제의 분류와 풀이 방법, 이 두 가지를 기반 지식이라고 부르겠습니다. PS를 하면서 이 문제는 회의실 배정과 똑같아! 이 문제는 전에 풀어봤던 minimum vertex cover와 똑같아! 이 문제는 maximum clique문제야!라고 비슷한 것들을 떠올리는 것이 모두 문제의 분류입니다. 물론 모든 문제가 특정 분류에 속하기는 어려울 수 있습니다. 저는 문제 상황과 조건, 구해야 하는 답을 잘 정리하는 것 역시 문제의 분류를 잘 아는 것이라 주장하고 있습니다. PS에서 말하는 풀이 방법은 흔히 책을 보면서 배우는 다익스트라, 탐욕 법, 동적 계획법과 같은 알고리즘 들이나, 힙, 스택, 세그먼트 트리와 같은 자료구조 등이라고 할 수 있겠습니다. 이 둘을 잘 알아야 문제를 잘 해결할 수 있습니다.
가령 최단경로를 묻는 문제가 출제되었는데, 문제의 분류인 최단경로, 문제의 풀이 방법인 최단경로 알고리즘, 둘 중에 하나라도 모르면 문제를 해결할 수 없을 것입니다. 결국 문제의 분류와 풀이 방법을 아는 것은 문제 해결에 있어서 기본 중의 기본이라고 할 수 있습니다.
이번에는 새로운 문제를 해결해봅시다.
$x = \sqrt {1 + \sqrt{1 + \sqrt{1 + \cdots}}}$ 일 때, x의 값을 구해봅시다.
저 무한한 제곱근을 반복적으로 계산할 수 있을까요? 컴퓨터로 어느 정도 계산은 할 수 있겠지만, 근사치를 얻을 뿐, 정확한 값을 얻을 수는 없습니다. 그러나 $x$를 제곱하면 기존의 $x$에 $1$을 더한 것과 같다는 것으로부터, $x^2 = x + 1$이라는 사실을 알 수 있고, 이 이차방정식을 해결하면 x는 황금비의 값과 같습니다. 여기서는 이차방정식을 어떻게 해결하건 간에, $x$를 제곱하면 $x+1$과 같아지고, 그것이 이차방정식이라는 것을 알아차리는 게 중요했습니다. 이차방정식에 대한 것을 빠삭하게 알고, 그 풀이법을 모두 안다고 해도, 이 문제가 이차방정식을 사용한다는 것을 모르면 이차방정식에 대한 그 방대한 지식이 한순간에 아무 쓸모가 없어집니다.
위의 무한 제곱근 문제에서 가장 중요한 것은, "어떤 복잡한 표현으로 이루어진 값을, 잘 정리하고 다시 쓰면 그 값에 대한 이차방정식으로 다시 쓸 수 있다"는 겁니다. 예시는 무한한 제곱근을 실제로 연산하려고 시도하는 것이 아니라, 해당 문제의, 해당 식의 핵심을 파악하여 이차방정식이라는 더 쉬운 형태로 변형하고자 했습니다. 이처럼 문제의 핵심을 관찰해서 풀이과정을 이끌어내는 과정이 중요합니다. 예시의 문제는 풀이를 내는 과정이 단순한 편이지만, 실제로 PS를 하다 보면 떠올리기 어렵고, 복잡한 아이디어가 필요한 순간이 찾아오기도 합니다. 항상 문제의 풀이를 알았으면, 풀이의 흐름과 각 단계의 논리성만큼이나 그 문제의 풀이가 어떤 사고 과정 속에서 나왔는지가 중요합니다.
문제의 핵심을 관찰하는 사고 과정과 발상, 그리고 그 핵심을 통해 문제의 풀이를 이끌어 내는 모든 과정을 저는 분석적 사고라 하겠습니다. 문제를 해결할 때는 이 문제에서 시작해서, 그 풀이과정이 어떤 발상과 사고 과정에서 나오게 되었는지를 되짚어보아야 합니다. 문제를 풀고 나서 다시 공부를 할 때는, 단순히 문제의 풀이, 풀이의 흐름, 그 풀이의 각 단계의 논리적 관계, 풀이의 동작 과정을 깊이 이해하는 것에서 그치는 것이 아니라, 문제에서 어떻게 그 풀이 과정이 나왔는지 역추적하는 분석적 사고의 훈련도 필요합니다. 분석적 사고의 훈련이 곧 문제를 잘 해결하는 방향과 가깝다고 할 수 있겠습니다.
이번에는 간단한 알고리즘 문제인 회의실 배정을 예로 들겠습니다.
회의실 배정은 $s_i$에 시작해서 $e_i$에 끝나는 회의들이 총 $N$개가 있을 때, 오직 하나의 회의실에 회의들을 겹치지 않게 최대한 많이 배정하는 문제입니다. 만약 1시에 시작해서 3시에 끝나는 회의, 2시에 시작해서 4시에 끝나는 회의, 3시에 시작해서 5시에 끝나는 회의가 있다면 1시와 3시에 시작하는 회의를 선택하면 회의를 가장 많이 배정할 수 있습니다.
그렇다면 어떤 회의들부터 배정해야 할까요?
수많은 배정 방법 중에, 가장 빨리 시작하는 회의부터 배정하는 것을 떠올릴 수 있습니다. 왜냐하면 더 늦게 시작하는 것을 고르면, 앞에 비는 시간이 생기기 때문에 그만큼 회의를 적게 배정할 것 같다고 떠올릴 수 있기 때문이죠. 게다가 해야 할 일을 빨리 시작하고 보는 게 앞으로 더 많이 할 수 있다는 직관적인 생각도 듭니다.
가장 빨리 시작하는 회의부터 배정하는 것이 정말로 최선의 방법이라고 할 수 있을까요?
이미 떠올리신 분들도 계시겠지만, 반례가 존재합니다. 만약 일찍 시작한 회의가, 너무너무 오래 걸려서 그 사이에 다른 회의를 전혀 배정하지 못한다면 어떨까요? 1시에 시작해서 10시에 끝나는 회의, 2시에 시작해서 3시에 끝나는 회의, 4시에 시작해서 5시에 끝나는 회의가 존재한다면, 1시에 시작하는 것을 제외한 나머지를 모두 선택하면 총 2개로 가장 회의를 많이 배정할 수 있습니다.
여기서 "가장 빨리 시작하는 것부터 배정하는 것이 정말로 최선의 방법일까?"라는 질문을 던졌습니다. 옳다고 생각하고 떠올린 풀이에 의문을 제기하고, 옳지 않을 거라고 가정하고, 그 반례를 찾아냈습니다. 문제 해결 과정에서는 나의 풀이가 틀릴 수 있음을 인지하고, 실제로 틀렸는지 확인해보기 위해 여러 상황을 가정해보거나, 사고 과정을 되짚어 보면서 논리적 결함이 있는지 찾아보는 것이 필요합니다. 이것이 비판적 사고입니다. 더 정확히는 새로운 지식을 배우거나, 문제의 풀이를 냈을 때, 그대로 옳다고 받아들이지 않고 항상 회의적인 자세로 해당 주장의 근거 혹은 옳지 않다는 근거를 찾는 과정입니다. 일반적으로는 정보를 객관적으로 분석하고 합리적인 판단을 하는 능력을 뜻합니다.
비판적 사고는 틀린 풀이를 찾아내는 데에만 쓸모 있는 것이 아닙니다. 실제로 현업에서 어떤 문제를 해결하려고 할 때, 그 문제를 해결하는 다양한 방법들의 장점과 한계점을 비교하고, 그중에 가장 나은 것을 선택하는 것이 한 예시가 될 수도 있습니다. 항상 새로운 지식을 배울 때, 비판적 사고를 가지고 지식을 받아들이는 과정에서 의문을 던지고 그 답을 구하며 공부를 한다면, 그 지식에 대해 더 깊이 있는 이해를 가지고, 더 폭넓은 응용을 할 수 있을 것입니다. 항상 새로운 지식과 풀이에 의문을 던지며 증명이나 반증을 하는 비판적 사고는, 앞서 언급했던 분석적 사고에도 많은 영향을 끼치곤 합니다.
지금까지 기반 지식, 분석적 사고, 비판적 사고가 무엇인지, 그리고 그것들이 문제 해결(특히 PS)에서 어떤 역할을 하는지 알아보았습니다. 항상 지식을 탄탄하게 가지고 있어야 하며(기반 지식), 문제를 잘 파악하고 분석하여 유의미한 관찰을 해서 올바른 풀이를 이끌어내는 연습을 해야 하고(분석적 사고), 틀린 풀이는 왜 틀렸는지 이유를 제시하고, 새로 배우는 지식에 대해 항상 질문을 던지려고(비판적 사고) 하는 것이 중요합니다. 저는 이 3가지를 통해 최근 많은 실력 성장을 이루었습니다. 문제 해결을 처음 시작하시는 분들, 문제 해결을 공부했지만 문제가 잘 풀리지 않는 분들께서 이 글을 보고 많은 도움을 받았으면 하는 바람입니다. 분석적 사고와 비판적 사고의 알고리즘 문제 해결에서의 적용에 대한 더 자세한 이야기로 돌아오도록 하겠습니다. 긴 글 읽어주셔서 감사합니다.
이 글을 쓰기까지 많은 도움을 주신 한동규(@queued_q) 선배님께 감사인사를 드립니다.