'비서 문제(Secretary Problem)'라고 들어보셨나요? 알고리즘이나 확률 수업에서 한 번쯤 나오는 유명한 문제인데요. 최근 한 개발자가 자기 회사의 채용 과정을 돌아보다가, 이 문제를 풀려고 한 적도 없는데 어쩌다 보니 문제 자체를 피해가고 있었다는 걸 깨닫고 그 이야기를 글로 정리했어요. 채용이라는 주제도 흥미롭지만, 저는 이 글이 '알고리즘 문제의 가정을 의심하는 법'에 대한 좋은 예시라서 소개하고 싶었어요.
비서 문제가 뭐냐면
이게 뭐냐면, 이런 상황이에요. 비서를 한 명 뽑아야 하는데 지원자가 100명 있어요. 한 명씩 순서대로 면접을 보는데, 면접이 끝나면 그 자리에서 뽑을지 말지 결정해야 해요. 한 번 보낸 사람은 다시 부를 수 없고, 뽑는 순간 면접은 끝나요. 이 조건에서 가장 좋은 사람을 뽑을 확률을 최대로 하려면 어떻게 해야 할까요?
수학적으로 증명된 최적 전략은 이래요. 처음 37%(정확히는 전체의 1/e)는 무조건 보내요. 대신 그동안 본 사람 중 최고가 누구인지 기억해둬요. 그다음부터는 지금까지 본 최고보다 나은 사람이 나타나면 바로 뽑아요. 이렇게 하면 진짜 최고를 뽑을 확률이 약 37%예요. 100명 중 1명을 찍는 것보다는 훨씬 낫지만, 세 번 중 두 번은 최고를 놓친다는 뜻이기도 해요.
이건 '최적 정지(optimal stopping)' 문제의 대표 사례예요. 언제 탐색을 멈추고 결정을 내릴지 정하는 문제인데, 집 구하기, 주차 자리 찾기, 심지어 연애 상대 고르기에도 비유되곤 해요.
그런데 실제 채용은 그 문제가 아니에요
글쓴이의 이야기를 제 나름대로 풀어보면 이래요. 비서 문제의 최적 전략이 37%밖에 안 되는 이유는 문제의 '조건'이 지독하게 불리하기 때문이에요. 그런데 실제 채용에서 그 조건들은 대부분 우리가 스스로 만든 거예요. 조건을 바꾸면 문제가 훨씬 쉬워지거나 아예 사라져요.
첫째, 즉시 결정할 필요가 없어요. 비서 문제는 면접 직후에 뽑든지 보내든지 하라고 해요. 하지만 실제로는 '일주일 안에 연락드릴게요'가 가능하잖아요. 여러 명을 본 다음에 비교해서 고를 수 있으면, 순차적으로 하나씩 결정하는 문제가 아니라 그냥 '후보군 중에서 고르기' 문제가 돼요.
둘째, 보낸 사람을 다시 부를 수 있어요. 비서 문제에서 거절은 되돌릴 수 없지만, 실제로는 '지난번에 지원하셨던 분인데 지금 자리가 났어요'가 되거든요. 물론 그 사이에 다른 회사에 갔을 수도 있지만, 확률이 0은 아니에요.
셋째, 상대 순위가 아니라 절대 기준으로 봐요. 비서 문제는 '지금까지 본 사람 중 최고인가'라는 상대 비교만 해요. 그래서 처음 37%를 기준 잡는 데 써야 해요. 하지만 채용에서는 '이 사람이 이 일을 할 수 있는가'라는 절대 기준이 있어요. 기준이 미리 있으면 첫 번째 지원자가 기준을 넘을 때 바로 뽑아도 되고, 탐색 기간이 필요 없어요.
넷째, 꼭 최고를 뽑을 필요가 없어요. 비서 문제는 '최고가 아니면 실패'로 정의돼요. 두 번째로 좋은 사람을 뽑아도 0점이에요. 하지만 실제로는 충분히 좋은 사람을 뽑으면 성공이죠. 목표를 '최고'에서 '충분히 좋음'으로 바꾸는 순간 성공 확률은 37%에서 훨씬 올라가요.
글 제목에 '나도 모르게(unwittingly)'라는 말이 붙은 이유가 여기 있어요. 글쓴이네 팀은 이걸 의도한 게 아니라, 그냥 '좋은 채용 관행'이라고 알려진 것들을 따르다 보니 자연스럽게 하고 있었던 거예요. 미리 정한 평가 기준, 여러 후보를 모아서 비교하기, 거절한 후보와 관계 유지하기 같은 것들이요.
알고리즘 문제와 현실 문제의 차이
이 글에서 제가 가장 중요하게 본 부분은 채용 팁이 아니라 사고방식이에요. 알고리즘 문제는 항상 가정 위에 서 있어요. 비서 문제의 37%는 '순차, 즉시 결정, 취소 불가, 상대 비교, 최고만 성공'이라는 다섯 가지 가정이 전부 성립할 때의 답이에요. 그 가정 중 하나라도 무너지면 답이 달라져요.
개발자들이 실무에서 자주 하는 실수가 여기 있어요. 어떤 상황이 유명한 문제와 비슷해 보이면 그 문제의 정답을 가져다 쓰려고 해요. 그런데 정작 '우리 상황이 그 문제의 가정을 만족하나?'는 안 물어봐요. 캐시 교체 정책, 분산 락, 재시도 전략 같은 것도 마찬가지예요. 교과서의 최적해가 우리 시스템에서는 전제부터 안 맞을 수 있거든요. 문제를 잘 푸는 것보다 문제를 잘 고르는 게 더 중요할 때가 많아요.
업계에서 채용은 어떻게 설계되어 있나요
이런 관점에서 보면 잘 알려진 채용 관행들이 왜 그렇게 만들어졌는지 보여요. 구조화 면접은 모든 후보에게 같은 질문을 같은 기준으로 물어서 '절대 기준'을 만드는 장치예요. 아마존의 바 레이저(Bar Raiser) 제도는 팀 외부 사람이 '이 사람이 회사 평균을 올리는가'라는 기준을 지키게 해서, 급하다고 기준을 낮추는 걸 막아요. 코딩 과제나 워크 샘플은 면접관의 인상이 아니라 실제 결과물로 기준을 확인하려는 거고요.
반대로 '이번 주 안에 뽑아야 해'라는 압박이 있으면 채용은 정확히 비서 문제로 돌아가요. 즉시 결정, 취소 불가, 지금까지 본 사람 중 최고. 그러면 성공 확률도 37%로 돌아가는 거예요.
한국 개발자에게는
한국 스타트업이나 소규모 팀에서 개발자를 뽑을 때 '이 사람 놓치면 안 될 것 같은데' 하는 조급함이 정말 자주 생겨요. 지원자가 많지 않고, 좋은 사람은 다른 회사에서도 오퍼를 받으니까요. 그런데 이 글대로라면 그 조급함이 바로 우리를 비서 문제 안으로 밀어넣는 조건이에요.
당장 할 수 있는 건 이런 거예요. 채용 공고를 내기 전에 '이 자리에서 반드시 할 수 있어야 하는 일 세 가지'를 먼저 적어두세요. 그게 절대 기준이에요. 그리고 첫 면접에서 뽑고 싶은 사람이 나와도, 최소 두세 명은 더 보고 나서 결정하는 규칙을 팀에 만들어두세요. 마지막으로, 거절한 후보에게 '다음 기회에 다시 연락드려도 될까요' 한 줄을 꼭 남기세요. 그게 '취소 불가'라는 가정을 깨는 방법이에요.
지원자 입장에서도 참고할 게 있어요. 회사가 '오늘 안에 답 주셔야 해요'라고 한다면 그 회사는 자기 채용을 비서 문제로 만들고 있는 거예요. 좋은 팀일수록 결정할 시간을 주고, 기준을 미리 말해줘요.
마무리
한 줄로 정리하면, 비서 문제의 37%는 문제의 가정이 만든 숫자이고 채용에서 그 가정은 대부분 우리가 바꿀 수 있으니, 정답을 외우기보다 가정을 바꾸는 게 훨씬 강력하다는 거예요.
여러분 팀의 채용은 어느 쪽에 가까운가요? 기준을 미리 정하고 여러 명을 비교하는 쪽인가요, 아니면 급해서 '지금까지 본 사람 중 최고'를 뽑는 쪽인가요?
🔗 출처: Hacker News