컴퓨터과학으로 풀 문제 발견

학교 급식 센터의 배달 차가 날마다 근처 학교 열 곳에 들렀다가 돌아온다. 운전기사는 늘 같은 순서로 다니지만, 순서를 바꾸면 더 짧게 다닐 수 있을 것 같다. 이 불편함은 컴퓨터과학으로 풀 수 있는 문제일까? 열 곳의 순서를 모두 따져 보면 확실한 답이 나오겠지만, 그 순서는 몇 가지이고 시간은 얼마나 걸릴까? 들를 곳이 스무 곳이라면 어떻게 될까? 주변에서 문제를 찾았을 때 먼저 무엇을 따져야 할까?

4.1.1불편함을 문제로 바꾸기

프로젝트는 주변의 불편함을 컴퓨터가 풀 수 있는 문제로 바꾸는 데서 시작한다. 그러려면 입력과 출력, 목표를 분명히 정한다. 배달 순서 문제라면 입력은 학교들 사이의 거리 표이고, 출력은 들르는 순서이며, 목표는 전체 거리를 가장 짧게 하는 것이다. 이렇게 정하면 이 문제가 그래프에서 모든 정점을 한 번씩 지나 돌아오는 가장 짧은 경로를 찾는 문제, 곧 외판원 문제임을 알 수 있다. 이미 알려진 문제 꼴로 바꾸면, 그 문제에 쓰이는 방법과 그 한계를 빌려 올 수 있다.

그림 1에서 들를 곳의 수를 바꾸어 보자. 열 곳이면 약 180만 가지라, 1초에 1억 개의 경로를 검사하는 컴퓨터로 0.02초면 모두 따져 확실한 답을 찾는다. 열다섯 곳이면 약 6500억 가지로 2시간 가까이, 스무 곳이면 약 \(1.2 \times 10^{18}\)가지로 380년이 넘는다. 그래서 열 곳 남짓이면 완전 탐색으로 풀고, 그보다 많으면 동적 계획법이나 가까운 곳부터 들르는 어림 방법으로 충분히 좋은 답을 찾는다.¹

4.1.2문제를 고르는 기준

찾은 문제가 프로젝트로 알맞은지는 몇 가지 기준으로 판단한다. 해결하면 실제로 누군가에게 도움이 되는가. 필요한 자료를 구할 수 있는가. 지금까지 배운 탐색, 동적 계획법, 그래프 같은 방법으로 풀 수 있는가. 문제의 크기가 정해진 시간과 컴퓨터로 감당할 만한가. 그리고 다른 사람의 개인 정보나 권리를 침해하지 않는가. 잔반 줄이기, 등굣길의 혼잡, 시간표 짜기, 동물 찻길 사고처럼 주변에는 이 기준을 만족하는 문제가 많다. 문제의 크기를 먼저 어림해 보면 어떤 방법을 써야 할지도 정해진다.

4.1.3예제 풀이

경로 수는 \(10!/2 \approx 1.8 \times 10^6\)에서 \(14!/2 \approx 4.4 \times 10^{10}\)으로 약 2만 4천 배가 된다. 따라서 시간도 약 \(0.02 \times 24000 \approx 480\)초, 곧 8분이다.

아침에 몇 분을 쓸 수 있다면 14곳까지는 완전 탐색이 가능하다. 그런데 15곳이면 그 15배인 2시간, 16곳이면 다시 16배인 32시간이 되어 하루 안에 끝나지 않는다. 즉 들를 곳이 하나 늘 때마다 시간이 그 수만큼 곱으로 늘어난다. 그래서 프로젝트를 설계할 때는 지금의 크기뿐 아니라 앞으로 늘어날 크기까지 어림하고, 15곳을 넘을 것 같으면 처음부터 어림 방법을 함께 준비한다.

아래 탐구 카드에서 주변의 불편함을 찾아 컴퓨터과학으로 풀 문제로 바꾸고, 문제의 크기와 쓸 방법을 정해 보자.

1. 외판원 문제는 도시가 많아지면 정확한 답을 빨리 찾는 방법이 알려지지 않은 대표적인 문제이다. 그래도 연구자들은 정교한 가지치기로 8만 곳이 넘는 도시의 최단 경로를 정확히 찾은 기록을 세웠다.