DP·탐색 문제를 푸는 사고 과정

동적 계획법과 그래프·백트래킹 탐색 문제에서 상태 정의, 점화식, 가지치기를 설명하는 인터뷰 준비 자료입니다.

첫 30초 답변

“작은 입력의 답을 적어 보면서 반복되는 부분 문제와 상태에 꼭 필요한 정보만 찾겠습니다.”라고 말한 뒤 상태를 문장으로 정의합니다.

미래의 결정을 위해 과거에서 기억해야 하는 최소 정보로 정합니다. 상태 의미를 한 문장으로 말할 수 없으면 과한 상태일 가능성이 큽니다.

의존 관계가 자연스럽고 상태 수가 작으면 메모이제이션이 빠릅니다. 스택 깊이와 순서를 통제해야 하면 바텀업 반복으로 바꿉니다.

현재 선택으로 최적해를 넘을 수 없거나 제약을 위반하면 즉시 가지치기합니다. 중복 상태는 방문 집합이나 정렬로 제거합니다.

질문 하나를 골라 2분 안에 말로 답한 뒤, 빠진 가정·트레이드오프·검증 방법을 메모하세요. 다음 날에는 예시를 바꿔 같은 구조로 다시 답해 보세요.