선형 계획법이나 동적 계획법을 적용해본 프로젝트 경험에 대해 이야기해 주세요.

알고리즘 수업에서 DP(동적 계획법)를 적용한 물류 배차 최적화 과제를 진행했습니다. 여러 노드에서 요청이 들어올 때 제한된 차량으로 최소 비용 경로를 찾는 문제였는데, 처음에는 완전 탐색으로 접근했다가 노드 수가 늘어나자 시간 복잡도가 폭발했습니다. DP로 재설계할 때 핵심은 부분 문제를 어떻게 정의하느냐였습니다. 방문한 노드 집합과 현재 위치를 상태로 정의하고, 메모이제이션으로 중복 계산을 제거했습니다. 비트마스크 DP로 구현하니 노드 15개 기준으로 실행 시간이 수 초에서 수십 밀리초로 줄었습니다. 어려웠던 건 상태 공간 설계였습니다. 처음에 상태 정의가 잘못되어 일부 경우의 수를 빠뜨리는 오류가 있었고, 점화식을 다시 세우는 데 시간이 걸렸습니다. 그 경험으로 DP는 '무엇을 저장하고 어떻게 전이하는가'를 명확히 정리하는 것이 출발점이라는 걸 배웠습니다.