최적 멈춤(Optimum Stopping) 알고리즘
결혼을 백화점 쇼핑에 비유한 이야기가 있다. 1층부터 올라가면서 괜찮은 상대를 고르는데 적절한 대상이 나타나면 멈추고 결정을 해야 한다. 어느 순간에 멈추고 배우자를 고를 것이냐가 핵심이다. 그런데 한 가지 원칙이 있다. 마음에 들 때까지 위로 올라가며 고를 수는 있지만 다시 아래층으로 내려갈 수는 없다. 그렇다면 어느 지점에서 결정을 해야 할까? 이럴 때 어떤 기준을 가지면 좋을까?
예를 들어 직원을 한 명 뽑는다고 생각해보자. 지난 일주일 동안 몇 사람 면접을 봤는데 신통치 않다. 지금 이 사람은 그런대로 괜찮다. 하지만 더 괜찮은 사람이 나타날 수도 있으니 결정을 미룬다. 그리고 일주일 더 면접을 봤는데, 마땅한 사람이 없다. ‘그때 그 사람을 뽑았어야 했는데’하며 후회가 밀려온다. 이럴 때는 37% 지점에서 멈추라는 최적 멈춤(optimum stopping) 알고리즘이 도움이 된다. 선택을 위해 멈춰야 하는 순간은 전체 소요시간의 37% 정도의 시점이 가장 좋다는 것이다.
집을 구할 때도 마찬가지다. 한 달 동안 집을 구해야 한다면 열흘 동안은 이곳저곳을 다니며 살펴본다. 그때는 마음에 들어도 결정하지 않는다. 그리고 11일(37%) 정도에 결정하는 것이 가장 성공 확률이 높다. 이 최적 멈춤 알고리즘은 일상의 꽤 많은 문제들에 적용할 수 있다.

후회 최소화 알고리즘
지금 다니는 회사가 마음에 드는데, 더 나이 들기 전에 내 사업을 시작하고 싶은 생각도 있다. 이럴 때는 어떻게 하면 좋을까? 아마존을 만든 제프 베조스가 좋은 사례다. 그는 아마존을 창업하기 전 뉴욕의 투자회사 D. E. Shaw에서 고액연봉을 받는 안정적인 자리에 있었다. 그런데 온라인 서점 사업을 너무 하고 싶었다. 그의 보스에게 얘기했더니 ‘신중하게 생각하라’는 조언을 들었다.
하지만 그는 결국 자신의 사업을 시작하기로 결심한다. 그가 결정을 내리는 기준은 심플했다. 바로 후회 최소화 알고리즘이다. 그는 80세가 되었을 때 스스로에게 “좋아, 내 인생에 후회는 없어. 있어도 아주 적지.”라고 말하고 싶었다.
후회에는 두 종류가 있다. 해본 일에 대한 후회와 하지 않은 일에 대한 후회다. 해본 일이 대한 후회는 짧지만, 안 해본 일에 대한 후회는 오래 간다. 인생의 중대사를 결정해야 할 때 후회 최소화 알고리즘을 적용해보자.

최저 사용빈도 알고리즘
옷장이 꽉 차서 정리를 해야 한다면 어떻게 할까? 우선, 나름의 기준을 정해서 안 입을 옷을 골라낸다. 그리고 남은 옷은 꺼내 입기 쉽게 정돈한다. 한마디로 정리정돈이다. 정리가 먼저고, 정돈이 나중이다.
컴퓨터의 메모리 장치도 이런 원리로 만들어졌다. 컴퓨터 과학자들은 어떤 것들을 간직하고, 그것을 어떻게 정리할지 수십 년간 고민했다. 그러다 1946년 폰 노이만이 기억 계층구조 개념을 생각해냈다. 정보를 모두 기억장치에 저장하는 대신, 다시 쓸 가능성이 높은 정보를 따로 모아 저장하는 것이다. 이것이 캐싱(Caching)이다. 자주 사용하는 정보를 작업기억장치에 담아 보관함으로써 매번 속도가 느린 주기억장치에 접근할 필요를 없앤 것이다.
문제는 ‘캐시가 꽉 찼을 때 어떻게 정리정돈을 것인가’이다. 세 가지 옵션이 있다. 첫째, 무작위 퇴거(Random Eviction) 방식이다. 캐시에 새 데이터를 추가할 때 기존의 데이터에 무작위로 덮어씌우는 것이다. 완벽하진 않지만, 아주 나쁘지도 않다. 캐시를 어떻게 관리하든 캐시를 가졌다는 것만으로도 시스템은 더 효율적이다. 둘째는 선입선출(FIFO, First-in, First-out) 즉, 가장 오래된 데이터를 버리는 것이다. 셋째는 최저 사용빈도(LRU, Least Recently Used) 방식이다. 가장 오랫동안 쓰지 않은 데이터를 버리는 것이다. 이 중 세 번째(LRU)가 가장 효과적이다. 지금까지 거의 사용하지 않은 테이터는 앞으로도 사용하지 않을 가능성이 높기 때문이다.

이 개념을 도서관에 적용하면 재미난 사실을 생각할 수 있다. 도서관의 핵심은 ‘어떤 책을 어디에 보관할 것이냐’이다. 그래서 최근에 가장 많이 대출된 책을 가장 찾기 쉬운 곳에 배치해야 한다. 따라서 신간코너는 뒤편에 두고, 가장 최근에 반납된 책을 중앙 통로에 배치하는 것이 효율적이다. 가장 최근에 대출해간 책은 다른 사람들이 다시 찾을 가능성이 높기 때문이다. 그러면 서가정리 과정이 편해지고, 사람들이 멀리 움직일 필요도 없다.

이처럼 알고리즘은 핵심을 뽑아내는 기술이다. 무엇이 핵심인지를 가려내고 정렬해서 순서를 매기는 과정이다. 사실 인공지능도 알고리즘 설계를 어떻게 하느냐에 따라 품질이 좌우된다.