[ABP: 최적멈춤문제]

멈춰야 할 때와 나아가야 할 때의 사이 어딘가

최적화 (optimization) 문제는 주어진 조건에서 최적의 결과물을 만들 수 있는 (혹은 보상을 얻을 수 있는, 혹은 피해를 최소화할 수 있는 등등) 방법을 찾는 문제입니다. 수학, 컴퓨터과학 뿐만 아니라 공학, 나아가 사회과학에서도 다양하게 활용되고 연구되는 주제이기도 합니다. 최적화 문제에서 자주 언급되는 케이스로서 이른바 '비서 채용 문제 (secretaty selection problem)'라고 부르는 문제가 있습니다. 이 문제는 다음과 같습니다.

당신은 비서를 한 명 채용하기 위해 후보자들을 면접하려 합니다. 채용하려는 후보는 N명 있습니다.
1. 면접은 1:1로 한 명씩 차례대로 합니다.
2. 면접 이후, 후보자에게 바로 합/불을 알려줘야 합니다.
3. 불합격한 후보자는 다시 부를 수 없습니다.
4. 특정 후보자에게 합격을 통보하는 순간 뒤에 몇 명의 후보자가 있든, 면접을 종료합니다.

N명의 후보 중, 분명 최고의 자질을 가진 후보가 포함되어 있을텐데, 그 후보자를 찾기 위해서는 몇 번의 면접을 봐야 할까요? 문제를 쉽게 이해하기 위해 100명의 후보자가 있고, 최적의 후보자를 찾기 위해 100명다 면접을 보는 상황을 생각해 봅시다. 이 경우 우리는 최적의 후보를 뽑지 못 할 가능성이 매우 높다는 것을 쉽게 추측할 수 있습니다. 왜냐하면 100번째 후보까지 오는 동안, 99명의 후보자들에게는 불합격을 날렸을 것이기 때문입니다. 마지막 후보가 최적의 후보일 수도 있겠지만, 그것보다는 앞선 99명의 불합격자 속에 최적의 후보가 포함되었을 확률이 훨씬 높을 것입니다. 반대로 첫번째 후보자를 만나자마자 합격시키는 것 역시 최적의 후보를 찾기에는 좋은 방법이 아닙니다. 당연히 뒤에 기다리고 있는 99명의 후보자 pool에 최적의 후보가 포함되어 있을 확률이 높을 것이기 때문입니다. 따라서 우리는 첫번째도 아니고 끝번째도 아닌, 중간 어디쯤에서인가 면접을 마쳐야 할 것임을 예상할 수 있습니다. 관건은 그 최적의 멈춤 지점이 어디쯤인가에 대한 것입니다. 대충 절반 정도니까 50번째 정도까지 하면 될까요? 그렇지만 수학적 분석을 해보면 그보다 더 먼저 멈춰야 합니다. 그렇게 해도 사실 최적의 후보를 찾을 확률은 50%가 안 됩니다. 생각보다 실망스러운 결과일 수도 있지만, 그래도 1%의 확률보다는 나으니 이 전략을 한 번 알아볼 필요가 있겠습니다.

그림 1. N = 3인 경우, 최적 멈춤 문제의 사례 (출처: 권석준)

예를 들어 N = 3인 상황을 생각해 보겠습니다. 우리에게는 A, B, C 세 후보자가 있고, 실제로 이들 중, 가장 높은 점수를 보유한 후보자는 C > B > A 순이라고 해 보겠습니다. (물론 채용하는 측에서는 이들의 점수를 면접 전에는 알 수 없습니다.) 여기서 채용하려는 측이 2번째에서 멈추는, 즉, 인터뷰는 1번만 하는 전략을 쓴다고 생각해 봅시다. 그러면 그림 1에 보인 것 같이, 6개의 경우의 수가 있을 것이고, 각 경우에 대해 이 전략의 성공 확률을 계산할 수 있습니다. 1번 경우는 첫 면접자가 A였고, 전략에 따라 A는 무조건 탈락합니다. 두번째 면접 본 B를 채용하게 되죠. 그렇지면 B는 점수 상으로는 중간이므로 1번 경우는 실패하게 됩니다. 2번 경우는 어떨까요? 마찬가지로 첫 면접은 A였고, A를 탈락시킨 후, C를 채용하는데, C가 최고 점수를 가지고 있으므로 2번 경우는 성공입니다. 3번 경우는 어떨까요? 첫 면접자 B를 탈락시킨 후, A를 면접하는데 채용하는 측은 A의 점수가 이미 탈락시킨 B보다 낮음을 확인했으므로, A도 탈락시키고 남은 후보자인 C를 채용합니다. 따라서 3번 경우도 성공입니다.이런식으로 하나씩 따져 보면 6개의 경우의 수 중, 성공으로 이어지는 경우의 수는 3개임을 알 수 있습니다. 즉, 면접을 한 번만 시행하는 전략은 성공률이 50%에 이르는 셈입니다. 마찬가지로 계속 따져 보면 N = 4일 경우 마찬가지로 1번 면접 전략이 최적이고 성공률은 45.83%가 됩니다. N=10 일 경우 3번 면접 전략이 최적이고 성공률은 39.87%, N=1000쯤 되면 최적의 면접 전략은 369번 면접에, 성공률은 36.81%가 됩니다. 이러한 경우의 수 카운트를 계속해볼 수도 있겠지만, N이 늘어날수록 경우의수는 N^2에 비례하여 커지게 되므로 N이 큰 수일 때는 이러한 휴리스틱 방법을 활용하는 것이 매우 어려워집니다. 물론 간단한 프로그래밍으로 계산해 보는 것도 가능합니다. 관심있는 분들은 아래의 파이썬 코드를 참고해서 시도해 보시기 바랍니다.

# Python3 Program to test 1/e law for

# Secretary Problem

import random

import math

e = 2.71828;

# To find closest integer of num.

def roundNo(num):

if(num < 0):

return (num - 0.5)

else:

return (num + 0.5);

# Finds best candidate using n/e rule.

# candidate[] represents talents of n candidates.

def printBestCandidate(candidate, n):

# Calculating sample size for benchmarking.

sample_size = roundNo(n / e);

print("\n\nSample size is",

math.floor(sample_size));

# Finding best candidate in sample size

best = 0;

for i in range(1, int(sample_size)):

if (candidate[i] > candidate[best]):

best = i;

# Finding the first best candidate that

# is better than benchmark set.

for i in range(int(sample_size), n):

if (candidate[i] >= candidate[best]):

best = i;

break;

if (best >= int(sample_size)):

print("\nBest candidate found is",

math.floor(best + 1),

"with talent", math.floor(candidate[best]));

else:

print("Couldn't find a best candidate");

# Driver code

n = 8;

# n = 8 candidates and candidate

# array contains talents of n

# candidate where the largest

# number means highest talented

# candidate.

candidate = [0] * (n);

# generating random numbers between 1 to 8

# for talent of candidate

for i in range(n):

candidate[i] = 1 + random.randint(1, 8);

print("Candidate : ", end = "");

for i in range(n):

print((i + 1), end = " ");

print("\nTalents : ", end = "");

for i in range(n):

print(candidate[i], end = " ");

printBestCandidate(candidate, n);

==================

N이 커지면 성공률은 대략 어디로 이르게 될까요? 수렴하는 것일까요? 그렇다면 몇 번째에서 멈춰야 할까요?

그림 2. r 전략 유도 과정 (출처: 권석준)

큰 N에 대해서는 어떻게 최적의 멈춤 지점을 찾을 수 있을까요? 위의 방식을 일반화한 전략을 r 전략이라고 합니다. 이는 r-1 명까지 면접한 후 이들을 다 탈락시킨 후, r번째 면접보는 후보자에 대한 판단을 하는 것입니다. 이 후보자가 이전의 r-1 명의 후보자보다 더 우수하다면 그를 채용하고, 그렇지 않다면 r+1 번째를 채용합니다. 이 전략이 성공할 확률을 계산해 봅시다.

우선 최적의 후보자가 r번째에 있을 확률을 계산해야 합니다. 이는 당연히 1/N 일 것입니다. 만약 그 후보자가 r+1번째에 있고, 그 후보자를 채용해야 한다면, 그 후보자 바로 이전 순서인 r번째 후보자의 면접 점수가, 다시 그 이전에 다 탈락시킨 r-1 명의 후보자 pool의 최고 점수자보다 낮아야 할 것입니다. 왜냐하면 r번째 후보자의 점수가 r-1 후보자 pool 최고 점수보다 크다면 r번째 후보자가 채용될 것이기 때문입니다. 이러면 r+1번째에 위치한 후보자까지 기회가 오지 않으므로, 최적의 후보자를 놓치게 됩니다. 마찬가지 방식으로 최적의 후보자가 r+i번째에 있고, 그 후보자를 채용해야 한다면, r번째부터 r+i-1번째 후보자까지 총 i명의 후보자 중, 그 누구도 앞선 r-1명의 후보자 최고 점수보다 높으면 안 됩니다. 이 확률은 (r-1)/(i-1)이 될 것입니다. 이제 그림 2에 보인 바와 같이, i가 r부터 N까지 가능한 경우를 다 살펴서 이 확률들의 합을 계산하면 됩니다. 간단한 계산을 이용하면 최적의 r은 0.36789...*N 임을 확인할 수 있습니다. 여기서 0.36789...는 다름 아닌 1/e (e는 자연상수) 입니다. 이를 이용하면 이제 N이 큰 수일 때도 일반화된 최적 멈춤, 그리고 그 확률을 계산할 수 있습니다. 물론 r은 자연수이어야 하므로 N/e에 가장 가까운 자연수를 찾아야 할 것입니다. 예를 들어 N = 100 이라면, r은 38이 됩니다. 따라서 100명의 후보자가 있는 경우라면, 일단 37명의 후보자는 면접하자마자 무조건 탈락시켜야 합니다. 대신 그 37명의 pool에서 얻은 최고의 면접 점수는 일종의 커트라인 정보를 제공해주게 되는 셈이 됩니다. 38번째 후보자부터는 이 커트라인을 넘는 순간부터 채용되기 때문입니다. 이렇게 해서 최적의 후보자를 찾게 될 확률 역시 1/e로 수렴합니다. 즉, 최적의 후보자를 찾을 확률은 36.789%~37% 정도 되는 셈입니다. 대략 1/3 조금 넘는 성공률인데 이 정도 성공률이 높은지 낮은지는 판단하는 사람의 몫입니다만 결코 높은 성공률이라고 단정하기는 어려울 것입니다.

물론 모든 채용이나 최적 후보 선택이 다 이러한 방식을 따라야만 하는 것은 아닙니다. 집단 면접을 할 수도 있고, 동시에 시험을 보는 방법도 있으니까요. 그렇지만 만약 이러한 방식이 주된 방식이라면 100번 중 63번 정도는 최적의 후보자가 그 자리에 앉아 있지 않을 것이라는 추정도 가능합니다. 최적의 후보자는 최적의 자리로 가지 못 하고 그에 못 미치는 후보자가 그 자리에 앉아 있다면 그 조직은 오래 가지 못 할 것 같다는 생각을 할 수도 있습니다. 그렇지만 생각보다 많은 조직들은 꽤 정교하게 후보자를 찾아내고 발굴하여 적재적소에 잘 배치합니다. 물론 그렇지 못 한 조직들은 점점 어려워지겠지만요. 63%나 되는 실패 확률을 내포하고 있음에도 불구하고, 왜 많은 조직들은 꽤 견실한 후보자를 잘 찾아서 업무에 배치한 것 같은 느낌이 드는 것일까요? 단순히 최적의 후보자를 못 찾아도 차점자를 잘 찾아서 교육시켰기 때문일까요? 물론 그런 이유도 있겠습니다만, 더 흥미로운 이유가 있습니다.

그림 3. 최적 멈춤 문제의 다양한 시나리오 (출처: https://horizon.kias.re.kr/6053/)

위에서 알아본 최적 후보 찾기 혹은 최적 멈춤 문제의 가장 중요한 가정은 '1등'을 찾을 확률이었습니다. 그렇지만 이 기준을 좀 낮춰 보면 어떨까요? 예를 들어 N=100인 경우, 1등을 찾는 문제는 상위 1%를 찾는 문제로 환원됩니다. 그런데 만약 이 기준을 상위 10%, 상위 25% 등으로 좀 낮춰 본다면 어떨까요? 그러면 추정컨대, 그 기준에 합당한 후보자를 찾을 확률은 더 높아지게 될 것입니다. 실제로도 그럴까요? Miller와 Todd가 수행한 컴퓨터 시뮬레이션 결과*를 참고해 보면 흥미로운 결과를 알 수 있습니다. 그림 3에 보인 바와 같이, 상위 10%로 기준을 낮추면 성공 확률은 83%까지 높아지고, 면접 횟수고 전체의 14% 정도만 하면 됩니다. 예를 들어 100명의 후보자 중, 상위 10% 안에 드는 후보자를 찾기 위해서는 13명의 후보자만 면접한 후, 14번째부터는 해당 후보자가 앞의 13명 중 최고 점수를 넘는지만 보면 되는 것입니다. 이렇게 해서 상위 10%를 찾을 확률은 83%까지 높아지게 됩니다. best만 채용하는 것을 고집했을 경우, 성공 확률이 37% 정도 밖에 안 된 것에 비해, 이 경우는 무려 83%까지 성공 확률이 높아졌으니 엄청난 개선이 된 셈입니다. 만약 상위 25%로 기준을 더 낮춘다면 결과는 더 극적으로 바뀝니다. 성공 확률은 92%까지 더 올라가고, 면접은 7% 선에서 마치면 됩니다. 예를 들어 100명의 후보자 중, 상위 25%에 속하는 후보자를 한 사람 뽑는다고 가정하면, 면접은 6명까지만 보면 됩니다. 그리고 7번째 후보자부터는 앞의 6명보다 점수가 높은지를 확인해서 채용하면 됩니다. 이렇게 적게 면접을 봐도 상위 25% 이내의 '적격' 후보자를 찾을 확률은 무려 90% 넘기게 되니, 거의 대부분 성공하게 되는 셈입니다.*

*Miller, G. F. and Todd, P. M., Mate choice turns cognitive, Trends in Cognitive Sciences vol. 2, no. 5, PP. 190-198, 1998

이러한 확률 게임을 살펴 보면 왜 우리 사회에 있는 수많은 조직들이 '최고'의 후보자가 아닌, 자신들이 정한 기준, 예를 들어 상위 XX% 같은 기준으로 후보자를 뽑아도 그럭저럭 조직이 굴러가게 만들 수 있는지 알 수 있습니다. 상위 10% 정도면 충분히 우수한 후보자이고, 이들을 뽑기 위해 면접을 아주 많이 치르지 않더라도 그 적격 후보자를 찾아낼 확률이 80%를 넘어가기 때문이죠. 물론 모든 채용이 이러한 방식으로 이루어지는 것도 아니고, 점수의 상위 %로 후보자를 평가할 수 있는 단순한 방식이 모든 조직에 통용되는 것도 아닙니다. 그렇지만 이는 꽤 많은 점을 시사하고 있다고 볼 수 있습니다.

이러한 전략을 개인이 활용할 수도 있을까요? 사실 이를 위해서는 내가 가용한 N이 얼마인지가 중요합니다. 예를 들어 어떤 사람이 주차장에 갔다고 생각해 봅시다. 빈 자리를 찾기 위해 주차장을 한 바퀴 도는 시간이 1분이라고 가정하겠습니다. 만약 내가 주차를 할 수 있을때까지 10분의 시간이 주어진다면 내게는 10번의 시도 기회가 있는 셈이므로 N=10이 됩니다. 여기서 나는 건물 엘리베이터와 가장 가까운 주차 자리를 찾고 싶습니다. 그러면 최적의 자리를 찾기 위해 몇 번 뺑뺑 주차장을 돌아야 하는 것일까요? 가장 가까운 자리를 찾는 것을 고집한다면 적어도 4바퀴를 돌고, 5바퀴째부터 적극적으로 평가하면서 찾아야 할 것입니다. 물론 다른 경쟁자도 같이 그 자리를 찾고 있을 수 있으므로 최적의 자리를 찾을 확률은 1/e 보다는 좀 떨어지겠지만, 그래도 이 전략은 꽤나 훌륭하게 작동할 수 있습니다.

그렇지만 N이 정해져 있지 않다면 어떻게 할까요? 어떤 싱글이 결혼하기 위해 몇 번의 소개팅에 나가야 할까요? 이론적으로라면 소개팅에서 이상형을 만날 확률은 37% 정도 될 것이지만 이는 N이 충분히 클 때입니다. 보통 사람은 N=100 수준의 소개팅을 할 여력도 가능성도 거의 없습니다. 그리고 내가 몇 번의 소개팅을 할 수 있을지에 대해서도 전혀 확신이 없습니다. 만약 내가 소개팅할 수 있는 횟수가 10번이라면 4번째까지의 소개팅 상대는 거절하고 5번째부터를 찾아야 할 것입니다. 그렇지만 그 횟수가 사실 알고보니 5번이었다면 3번째까지의 소개팅 상대만 거절해야 합니다. 그리고 그 횟수가 알고보니 3번이었다면 1번째까지의 상대만 거절해야 합니다. 10번, 5번, 3번 등의 횟수에 따라 최적 멈춤이 달라지는데, 문제는 내가 그 횟수를 모른다는 것입니다. 그래서 사실 N을 미리 '강제로' 고정해줄 수 있는 결혼정보회사 등에 가입하는 것이기도 합니다. 그렇다면 N을 정해주는 결혼정보회사에 가입하는 경우를 생각해 보겠습니다. 정보회사마다 비즈니스 모델은 다르지만, 그 회사의 매출과 성장은 회원들의 성혼률 향상에 달려있습니다. 따라서 회사 입장에서는 신규 회원을 받았을 때 그 회원이 최대한 자신의 이상형과 매칭되게 만드는 것이 중요해집니다. 어떤 회원은 사람 만나는 것이 부담스러운 스타일이라면, 그래서 최대한 만날 수 있는 횟수가 4번이라면 10번, 20번짜리 소개팅 상품은 의미가 없을 것입니다. 위의 분석에 따르면 이 회원에게 추천할 수 있는 상품은 5명을 만날 수 있는 옵션이 걸린 상품일 것입니다. 그렇게 되면 이 회원은 최적 멈춤 전략에 따라 3번까지의 만남을 뒤로 하고, 4번째 상대와 미팅하며 이상형을 찾을 확률을 조금이라도 더 높여볼 수 있을 것입니다. 물론 소개팅은 비서 채용과는 달리, 재시도할 수 있는 확률도 있으므로 조금 더 성공 확률은 높아지겠지만, 대체적인 경향은 크게 바뀌지는 않습니다.

우리의 모든 삶이 최적 멈춤 문제처럼 확률에 따라 다 정해지지는 않습니다. 그렇지만 이러한 전략이 내포하고 있는 것을 캐치하고 활용하는 것은 꽤나 도움이 됩니다. 특히 최고만 고집하는 것이 아니라, 적격으로 타협하는 것, 그럼으로써 시간과 자원을 절약하는 방법이 있다는 것은 여러가지를 시사합니다. 더 나아가야할 때와 멈춰야 할 때를 구분짓는 것은 시간이라는 한정된 자원을 가진 우리에게는 그야말로 최적의 전략을 제공해주는 것이 아닐까 합니다.