어떻게 완벽 대신 충분히 좋게

완벽은 잠시 내려놓는다

어려운 문제가 있다. 완벽한 답을 찾으려면 모든 경우를 다 따져야 하는데, 그 수가 어마어마하다.
끝까지 가면 분명 가장 좋은 답이 나오기는 해요. 그런데 그게 언제 끝날까?
눌러서 한번 세어 보자.

완벽한 답을 끝까지 따지면 이렇게 된다. (경우의 수가 불어나 시간이 폭발 → 끝이 안 보여요)

수가 너무 빨리 불어난다. 몇 개만 늘어도 따질 것이 몇 배씩 많아진다.
그러니 완벽한 답을 끝까지 기다리는 것은 현실적이지 않을 때가 있다. 그렇다고 손을 놓을 수는 없어요.

충분히 좋은 답을, 빨리

여기 한 가지 생각이 있다. 꼭 최고가 아니어도 괜찮다면 어떨까?
완벽을 노리는 대신 그냥 빠르게 '그럭저럭 좋은 답'을 뽑아 보는 것이다. 탐욕에서 했던 것처럼 눈앞의 좋은 것을 척척 골라 가면서 말이에요.

빠른 어림 답 vs 완벽한 답을 견준다. (어림 답은 순식간에 · 차이는 조금뿐)

어림 답은 눈 깜짝할 새 나왔는데, 완벽한 답과 차이가 별로 나지 않는다.
조금 부족하지만 쓸 만하다. 많은 경우에 이 정도면 충분해요.

얼마나 좋은지 보장한다

그런데 걱정이 하나 있다. '그럭저럭 좋은 답'이라는 말을 믿어도 될까? 혹시 엄청 나쁜 답이면 어떡하지?
그래서 똑똑한 방법들은 약속을 함께 준다. '이 답은 최고보다 많이 나빠지지는 않는다'는 약속이에요.

최적의 1.5배 이내를 보장한다. (어떤 답이 나와도 이 선 안 → 최악이 막혀 있어요)

이것이 정말 멋진 점이다. '최적의 1.5배 안'처럼 선을 그어 두면 답이 아무리 나빠도 그 선을 넘지 못한다.
완벽하지는 않아도 얼마나 모자랄 수 있는지 우리가 정확히 안다. 막연한 추측과는 완전히 달라요.

정확도와 시간을 맞바꾼다

결국 이것은 저울이다. 시간을 더 쓰면 답이 더 정확해지고, 시간을 아끼면 답이 조금 거칠어진다.
어느 쪽이 좋다고 딱 정할 수는 없어요. 급하면 빠른 쪽, 정밀해야 하면 정확한 쪽이다.
버튼으로 시간을 늘리고 줄이며 둘 사이를 골라 보자.

시간을 더 쓰면 더 정확하고, 덜 쓰면 덜 정확하다. (어디서 멈출지는 우리가 골라요)

이 저울은 알고리즘 전체를 꿰뚫는 마음이다. 빠른 길과 정확한 길, 간단한 길과 꼼꼼한 길.
우리는 매번 무엇을 내주고 무엇을 얻을지 골라 왔다. 좋은 방법을 안다는 것은 이 저울을 잘 읽는 것이에요.

여기까지 온 길

긴 길을 걸어왔다. 순서대로 풀기에서 시작해 줄 세우고, 찾고, 비용을 재고, 나누고, 잇고, 골랐다.
어떤 문제는 정말 어렵다는 것도, 그래도 충분히 좋은 답이 있다는 것도 보았다.
눌러서 그 길을 한 번에 돌아봐요.

이 영역이 준 네 가지를 차례로 정리한다. (좋은 방법 · 빠르기 · 전략 · 한계를 알고 타협)

모든 문제를 완벽하게 풀 수는 없다. 하지만 그것이 무력하다는 뜻은 아니다.
빠른 방법과 똑똑한 전략을 쓰고, 한계를 알고 현명하게 타협하면 어려운 문제 앞에서도 쓸 만한 답을 손에 쥘 수 있다.
그것이 알고리즘이 우리에게 주는 힘이에요.