이 질문 뒤에 면접관이 확인하려는 것은 따로 있습니다.
알고리즘 수업에서 DP(동적 계획법)를 적용한 물류 배차 최적화 과제를 진행했습니다. 여러 노드에서 요청이 들어올 때 제한된 차량으로 최소 비용 경로를 찾는 문제였는데, 처음에는 완전 탐색으로 접근했다가 노드 수가 늘어나자 시간 복잡도가 폭발했습니다. DP로 재설계할 때 핵심은 부분 문제를 어떻게 정의하느냐였습니다. 방문한 노드 집합과 현재 위치를 상태로 정의하고, 메모이제이션으로 중복 계산을 제거했습니다. 비트마스크 DP로 구현하니 노드 15개 기준으로 실행 시간이 수 초에서 수십 밀리초로 줄었습니다. 어려웠던 건 상태 공간 설계였습니다. 처음에 상태 정의가 잘못되어 일부 경우의 수를 빠뜨리는 오류가 있었고, 점화식을 다시 세우는 데 시간이 걸렸습니다. 그 경험으로 DP는 '무엇을 저장하고 어떻게 전이하는가'를 명확히 정리하는 것이 출발점이라는 걸 배웠습니다.
수업 프로젝트에서 제한된 예산 안에서 여러 마케팅 채널에 예산을 배분해 ROI를 최대화하는 문제를 DP로 접근한 경험이 있습니다. 각 채널에 투입할 수 있는 예산 단위와 예상 ROI가 주어졌을 때, 예산 합이 제한 내에서 ROI 합을 최대화하는 조합을 찾는 것입니다. 전형적인 배낭 문제(0/1 Knapsack)의 변형이었는데, 처음에는 그리디 방식으로 ROI가 높은 것부터 넣다가 최적해가 아닌 경우가 생기는 것을 발견하고 DP로 재접근했습니다.
그리디가 부분 최적을 보장하지만 전역 최적을 보장하지 못한다는 것을 실제 케이스에서 확인한 것이 DP를 이해하는 전환점이었습니다. DP 테이블을 세우고 나서 경로를 추적해 어떤 채널 조합이 최적인지를 역추적하는 방식까지 구현했습니다. 이 경험이 알고리즘이 실제 의사결정 문제와 연결된다는 것을 이해하게 해줬습니다.
DP 프로젝트에서 기술적으로 고민했던 것 중 하나는 재귀 기반 메모이제이션과 반복 기반 타뷸레이션 중 어떤 방식을 쓸지였습니다. 배차 문제 초반에는 재귀로 구현했는데 파이썬의 재귀 깊이 제한에 걸려서 런타임 오류가 발생했습니다. 그래서 동일한 점화식을 반복문 기반 타뷸레이션으로 재구현했습니다. 두 방식의 결과는 같지만 스택 오버플로 위험이 없고 실행 시간이 더 안정적이었습니다. 공간 복잡도 최적화도 했는데, DP 테이블 전체를 저장하지 않고 이전 행과 현재 행만 유지하는 방식으로 메모리 사용량을 줄이는 구조로 바꿨습니다.
알고리즘은 정확성만으로 완성되는 것이 아니라 실제 제약(메모리·시간·환경) 안에서 동작하도록 설계해야 한다는 것을 그 경험에서 배웠습니다.
답변에서 흔히 빠지는 것들 — 빠져 있으면 꼬리질문이 깊어집니다.
이 질문에 이어 쿠팡 데이터 사이언티스트 면접관이 던질 가능성이 높은 후속 질문.
이 페이지의 질문·답변·꼬리질문은 유사 직군 채용 시장의 공개된 면접 후기·커뮤니티 게시물을 분석해 구성한 학습 자료입니다. 특정 회사가 실제로 이 질문을 출제했다는 것을 보장하지 않으며, 모든 예시는 우문현답이 직접 작성한 창작물입니다. 해당 회사의 공식 입장과는 무관합니다. 회사 측의 정정 요청이 있을 경우 24시간 이내에 응답·수정합니다.