Hacker News 2026.05.26 57

정사각형 안에 정사각형 채우기 — 이 단순한 문제가 수학자들을 100년째 괴롭히는 이유

단순해 보이지만 절대 단순하지 않은 문제

자, 이런 상황을 한번 상상해봐요. 큰 정사각형 하나가 있어요. 그 안에 작은 정사각형들(예: 한 변이 1cm짜리)을 N개 집어넣어야 해요. 단, 작은 정사각형들이 서로 겹치면 안 돼요. 이때 큰 정사각형의 한 변 길이를 가장 짧게 만들려면 어떻게 배치해야 할까요?

언뜻 들으면 "이거 그냥 격자처럼 차곡차곡 쌓으면 되는 거 아니야?"라고 생각하기 쉬워요. N이 1, 4, 9, 16처럼 완전제곱수일 때는 실제로 그래요. 한 변에 √N개씩 줄 맞춰 넣으면 딱 떨어지죠. 그런데 N=11이라면? 17이라면? 갑자기 문제가 이상해져요. 격자 형태로는 못 넣고, 작은 정사각형들을 비스듬히 기울여서 끼워 넣어야 가장 효율적인 배치가 나와요. 이게 바로 "Squares in Squares" 문제예요.

왜 이게 어렵냐면

이 문제는 조합 최적화(combinatorial optimization)의 끝판왕 같은 거예요. N이 커지면 가능한 배치의 경우의 수가 폭발적으로 늘어나거든요. 게다가 정사각형을 기울여 넣는 각도까지 변수로 들어가면, 이건 더 이상 깔끔한 수학 공식으로 풀 수 있는 문제가 아니에요. 그래서 수학자들과 컴퓨터 과학자들이 "이 N일 때는 이렇게 넣는 게 지금까지 알려진 최적의 답이다"라고 하나씩 갱신해 나가는 식으로 연구를 해왔어요.

흥미로운 건 N=11 같은 경우예요. 직관적으로는 4×3 격자에서 하나만 빠지면 될 것 같지만, 실제로는 가운데에 정사각형 하나를 약 40도쯤 기울여서 끼워 넣는 게 더 효율적이라는 게 밝혀졌어요. 보고 있으면 "이게 진짜 최적이야?" 싶을 정도로 비대칭적이고 묘하게 어색한 모양이 나와요. 그런데 그게 현재까지 알려진 가장 작은 컨테이너예요. 더 작은 배치가 있을 수도 있지만, 아직 아무도 못 찾았어요.

컴퓨터로 어떻게 풀까요

이 문제를 푸는 데는 보통 두 가지 접근이 쓰여요. 첫째는 분기한정법(branch and bound) 같은 전통적인 최적화 알고리즘이에요. 가능한 배치를 트리 구조로 펼쳐 놓고, "이 가지로 가면 답이 더 나빠질 게 확실하다" 싶으면 가지치기를 해서 탐색 공간을 줄이는 거죠. 둘째는 시뮬레이티드 어닐링(simulated annealing)이나 유전 알고리즘 같은 휴리스틱 방법이에요. 처음엔 마구잡이로 배치하다가 점점 더 좋은 배치 쪽으로 "진화"시키는 방식인데요, 정확한 최적해를 보장하진 않지만 실용적으로 꽤 좋은 답을 빨리 찾아줘요.

Erich Friedman이라는 수학자가 이런 packing 문제들을 오래 정리해 왔고, 이번에 공유된 사이트도 그 연장선이에요. N별로 알려진 최적 배치를 그림과 함께 보여줘요. 보다 보면 "수학이 이렇게 시각적으로 아름다울 수 있구나" 하고 새삼 느끼게 돼요.

업계 맥락에서 보면

이런 packing 문제는 단순한 수학 퍼즐이 아니에요. 실제로 산업 현장에서 매일 풀고 있는 문제거든요. 물류 창고에서 상자 배치, 컨테이너 적재 최적화, 반도체 칩의 회로 배치(EDA, Electronic Design Automation), 의류 공장의 원단 재단까지 다 같은 계열의 문제예요. 1mm 차이로 원단 효율이 1% 올라가면, 회사 입장에서는 연간 수억 원이 왔다 갔다 하니까요.

게임 업계에서도 비슷한 알고리즘을 써요. 텍스처 아틀라스(texture atlas)라는 게 있어요. 여러 개의 작은 이미지를 큰 이미지 하나에 모아 담는 기법인데, 메모리를 아끼고 GPU 호출 횟수를 줄여줘요. 이때 어떻게 배치하느냐가 성능에 직결돼요. Unity나 Unreal Engine 내부에도 이런 packing 알고리즘이 들어가 있어요.

한국 개발자에게 시사점

당장 실무에 쓸 일은 없을 수 있어요. 하지만 이런 문제를 한 번이라도 직접 다뤄보면 "NP-hard라는 게 진짜 뭔지" 몸으로 느끼게 돼요. 코딩 테스트에서 백트래킹이나 그리디 알고리즘을 풀 때, "왜 완전탐색은 안 되고 가지치기가 필요한가"가 자연스럽게 이해되거든요.

또, 머신러닝 시대에 모두가 신경망만 보는 것 같지만, 사실 산업의 핵심 최적화 문제들은 여전히 고전적인 조합 최적화로 풀려요. 쿠팡, 마켓컬리 같은 물류 회사의 백엔드, 반도체 EDA 도구, 클라우드의 VM 배치 스케줄러 — 다 이런 알고리즘 위에 서 있어요. 한 번쯤 이 분야를 들여다보면 커리어의 폭이 확실히 넓어져요.