길로틴 절단

정의

각 절단이 현재 조각의 한 변에서 마주 보는 변까지 곧게 이어져야 한다는 제약 아래 직사각형을 자르거나 배치하는 직교 절단·적재 문제.

예시

패널 $4\times4$에서 먼저 한 변에서 마주 보는 변까지 가로로 곧게 자르면 $4\times1$과 $4\times3$으로 나뉘고, 이어 $4\times3$을 세로로 잘라 $2\times3$ 둘로 나눌 수 있다 — 매 절단이 조각의 변에서 변까지 이어지므로 길로틴 제약을 만족한다. 반대로 가운데에 한 조각이 둘러싸이도록 박힌 “바람개비(pinwheel)” 배치는 단 한 번의 직선 절단으로 분리되지 않아 길로틴 방식으로는 만들 수 없다.

왜 중요한가

길로틴 제약은 임의적이지 않다 — 패널 톱, 유리 절단기, 종이 재단기 같은 많은 절단 기계가 변에서 변까지의 직선 절단만 가능하다. 이 재귀적 구조는 동적 계획법과 잘 맞는다.

관련 노드

아래 깊이 1 그래프를 참고하라.