알고리즘 문제를 보자마자 BFS나 최단 경로부터 떠올릴 때가 있다. 그런데 코드에 들어가기 전에 멈춰야 할 질문이 있다. 내가 그린 점 하나는 무엇이고, 선 하나는 무엇을 허용하거나 막는가. 이 둘을 문장으로 적어 보면, 비슷해 보이던 문제도 서로 다른 그래프가 된다.
나는 그래프를 배우는 첫 연습을 공식 암기보다 이 문장을 쓰는 일로 시작하고 싶다. 점과 선을 예쁘게 그리는 데서 끝나지 않고, 그림이 원래 질문을 보존하는지 확인하는 것이다. 답을 구하는 알고리즘이 정확해도, 다른 문제를 그림으로 옮겼다면 우리가 원한 답은 나오지 않는다.
같은 시간표에서 서로 다른 질문이 나온다
설명을 위해 공유 프린터 세 대를 쓸 수 있는 작은 작업실을 가정해 보자. 출력 작업 A는 9시부터 9시 30분, B는 9시 20분부터 9시 50분, C는 9시 40분부터 10시까지 프린터 한 대를 독점한다. 실제 운영 기록이 아니라 모델을 생각하기 위해 만든 예시다.
먼저 묻고 싶은 것이 필요한 프린터의 최소 대수라면, 점은 작업이고 선은 시간이 겹치는 두 작업 사이의 충돌이다. A와 B, B와 C 사이에는 선이 있고 A와 C 사이에는 없다. 같은 색을 같은 프린터로 해석하면 A와 C는 한 대를 나눠 쓸 수 있고, B는 다른 한 대를 쓴다. 이 예에서는 두 색으로 충분하다.
그런데 출력 전에 자료 수집과 교정이 끝나야 한다는 질문을 풀고 싶다면 어떻게 될까. 이번에는 점이 작업 단계가 되고, 선은 먼저 끝나야 하는 관계가 된다. 수집에서 교정으로, 교정에서 출력으로 향하는 화살표가 필요하다. 시간 충돌을 나타내던 선에 방향만 덧붙여서 해결할 수 있는 것은 아니다. 선의 뜻 자체가 달라졌다.
여기에 이동 시간을 최소화하는 질문을 더하면 또 달라진다. 점이 장소가 되고 선에 걸리는 시간이 붙을 수 있다. 하나의 현실에 정답 그래프가 하나만 있다고 생각하면 이 차이를 놓친다. 그래프는 현실의 축소 모형이지만, 무엇을 남길지는 풀고 싶은 질문에 따라 정한다.
교재를 읽을 때 정의 옆에 반례를 적는다
Mikhail Lavrov의 공개 교재 Start Doing Graph Theory는 첫 장에서 여러 문제를 그래프로 바꾸어 묻는다. 지도에서는 인접 관계를 남기고, 상태가 바뀌는 퍼즐에서는 전체 상태 하나를 점으로 삼는다. 원문 예시를 그대로 따라 쓰기보다, 점의 선택이 문제마다 달라지는 이유를 읽는 데 도움이 된다.
특히 상태를 점으로 삼는다는 생각은 낯설다. 눈앞에 물건 세 개가 있다고 반드시 점도 세 개여야 하는 것은 아니다. 한 점이 물건 전체의 배치를 뜻한다면 가능한 배치만큼 점이 생긴다. 반대로 물건 하나를 점으로 두는 편이 자연스러운 문제도 있다. 그림에 무엇이 등장하는지와 모델에서 무엇이 하나의 단위인지는 따로 생각해야 한다.
그래서 정의를 적은 다음에는 그 정의에 맞지 않는 예를 하나 만든다. 프린터 예라면 같은 작업을 두 점으로 중복해서 적었을 때, 끝나는 시각과 시작 시각이 같은 작업을 겹친다고 처리했을 때를 살펴볼 수 있다. 여기서는 프린터를 즉시 넘길 수 있다고 가정했지만, 준비 시간이 필요하면 선을 만드는 규칙부터 달라진다.
이때 반례는 알고리즘의 약점을 찾는 데만 쓰이지 않는다. 내가 말로 적은 규칙의 빈칸을 찾는 데도 쓸 수 있다. ‘시간이 겹친다’는 한 문장 안에 준비 시간, 중간에 멈출 수 있는지, 한 작업이 여러 대를 쓰는지 같은 조건이 숨어 있다. 현실에 필요한 조건을 빼놓았다면 계산을 더 빠르게 해도 결과는 실용적이지 않을 수 있다.
작은 그래프를 손으로 확인한 뒤 코드를 고른다
다음 연습에서는 점 다섯 개 정도만 남겨 보고 싶다. 입력의 각 항목이 어느 점에 대응하는지, 두 항목 사이에 선을 넣은 이유가 무엇인지 하나씩 설명한다. 선이 없는 두 점도 골라서 왜 연결하지 않았는지 적는다. 존재하는 관계만 설명할 때보다 빠진 관계를 설명할 때 규칙이 더 잘 드러나기도 한다.
그 뒤에는 원하는 출력이 무엇인지 쓴다. 경로 하나인가, 필요한 색의 수인가, 함께 고를 수 있는 점의 묶음인가. 같은 그림을 놓고도 답의 형태가 달라질 수 있다. ‘이 그래프를 풀어라’는 문장은 아직 문제를 충분히 말해 주지 않는다. 어떤 성질을 구하려는지까지 있어야 풀이를 선택할 수 있다.
손으로 답을 예상할 때에는 그 답보다 더 좋은 것이 왜 불가능한지도 짧게 적어 본다. 프린터 예에서는 A와 B가 겹치므로 한 대로는 부족하다는 하한을 얻고, 실제 두 대 배치를 써서 충분하다는 것도 보인다. 숫자 2를 얻는 일과 그 숫자를 믿을 이유를 갖는 일 사이에 이 작은 설명이 있다.
물론 모든 현실을 그래프로 바꾸는 것이 이득은 아니다. 관계가 계속 변하거나 꼭 필요한 정보가 선 하나에 담기지 않으면 다른 모델이 더 단순할 수 있다. 처음부터 큰 라이브러리를 고르기보다, 점과 선으로 옮겼을 때 질문이 더 명확해졌는지 먼저 묻는 편이 좋겠다.
공부한 양을 확인할 때에도 새 알고리즘 이름을 몇 개 알게 됐는지보다 한 문제를 다른 사람에게 다시 설명할 수 있는지 보고 싶다. 오늘 읽은 정의를 닫고, 익숙한 일정 하나를 점과 선으로 바꿔 본다면 어떨까. 그 그림의 점 하나와 선 하나가 무엇을 뜻하는지, 지금 한 문장으로 말할 수 있을까.
이어 읽기: 작은 프로그램을 읽는 연습, 줄 수보다 입력과 끝을 정해보기
공개 원문을 참고하고 AI의 도움으로 구성한 글입니다. 가상의 예시는 본문에 구분했으며 제품이나 원문의 실험을 직접 실행한 후기는 아닙니다.
