[ABP: 정사각형 패킹의 전략]

상식과 비상식 사이 어딘가쯤

누구나 자신의 방안에 어떻게 가구를 배치해야 공간의 활용이 극대화될 것인지 고민해 본 적이 있을 것이다. 이러한 전략은 일반적으로 공간 패킹 (space packing) 전략이라고도 한다. 건축에서는 물론, 물류, 컴퓨터 칩의 배치, 에너지 활용 순서 등 다양한 산업 분야에서 꽤 중요한 기술적 영향을 발휘하는 엔지니어링 분야이기도 하다. 그렇지만 그 이면에는 수학이 자리잡고 있다.

*https://erich-friedman.github.io/packing/squinsqu/
*위에 링크한 자료는 이런 문제에 대한 해법 혹은 증명이다. 증명된 것도 있고, 증명이 안 된 (즉, 최선의 값만 찾아 놓은 것) 것도 있는데, 요는 이렇다. 한 변의 길이가 1인 정사각형을 N개 사용해서 채울 수 있는 최소한의 정사각형의 면적은 얼마인가? 예를 들어 N=1이면 당연히 면적은 1, N=2~4이면 면적은 4, N=5이면 면적은 7.3284 ((2 + (1/2^0.5))^2) 이고 이런 식이다.

N = 6, 7, 8, 9일 때의 면적은 9이다. 여기까지는 납득이 된다. 그런데 흥미로운 지점은 N = 10부터다. 위에 링크한 페이지에 나타난 패킹 예시 그림 중 N = 10 (P), 11 (F), 17 (F), 18 (F), 19 (F), 26 (F), 28 (F), 27 (F), 29 (F), 37 (F), 38 (F), 39 (F), 40 (F), 41 (F), 50 (F), 51 (F), 52 (F), 53 (F), 54 (F), 55 (F), 65 (F), 66 (F), 67 (F), 68 (F), 69 (F), 70 (F), 71 (F), 82 (F), 83 (F), 84 (F), 85 (F), 86 (F), 87 (F), 88 (F), 89 (F) 를 살펴 보자. 참고로 여기서 P라고 쓴 것은 수학적으로 증명된 것이고, F라고 쓴 것은 증명은 안 되었고, 아직까지 찾아진 설루션 중 최선의 값 (즉, 최소값)이다.**

**https://erich-friedman.github.io/packing/squinsqu/

비교적 규칙적인 모양인 N = 10인 케이스 정도가 증명된 사례의 최선이고, 보다 복잡해지기 시작하는 N = 11 케이스부터는 전혀 증명되어 있지 않다는 것을 알 수 있는데, 사실 N = 11 정도의 작은 숫자면 증명되었을 법도 한데, 아직 증명이 안 되었다는 사실도 신기한 부분이다. 인터넷 커뮤니티에는 N = 17인 케이스가 화제성이 있는지 자주 보이고 있는데, 위에 첨부한 그림처럼, 왼쪽의 규칙적인 (즉, 대칭적인) packing 보다 오른쪽의 불규칙한 packing이 아주 미세하게 더 작은 정사각형을 채울 수 있다라는 사실이 우리의 직관과 반하기 때문이 아닐까 한다. 대칭성에서 수학적 아름다움을 본능적으로 느끼는 대부분의 사람들 입장에서는, 실로 첨부한 그림의 우측에 표현된 것처럼, 이런 못 생긴 배치가 수학적으로 최선의 배치일 것이라는 사실에는 쉽사리 동의할 마음이 생기지 않을 것이다. 실제로 측정해보기 전에는 믿을 수 없을 정도일 것이다. 그렇지만 어쨌든 측정 결과는 불규칙적인 packing이 더 작은 정사각형을 채우는 것으로 나타난다. 즉, 대칭적 packing보다 이렇게 비대칭적인 packing이 현재로서는 최선에 가깝다. 물론 수학적 증명이 완료되기 전까지는 최선의 배치가 정말로 말도 안 되는 불규칙적 배치일지 여부는 알 수 없다.

이런 류의 연구가 흥미를 자아내는 것 외에, 도대체 무엇에 쓸모가 있느냐고 물어볼 수 있다. 그러나 사실 다면체 (폴리곤, polygon (2D), polytope (3D))로 이루어진 공간 혹은 그렇게 생긴 알갱이들로 그러한 공간을 빽빽하게 채우는 packing 문제는 물리학에서는 오래된 그렇지만 중요한 연구 주제다. 애초에 분자동역학 (molecular dynamics) 이나 몬테카를로 시뮬레이션 (Monte Carlo simulation)으로 연구하는 주제 중 하나가 identical particles의 assembly 현상인데, sphere에 대해서는 사실 어렵지 않지만, polygon이나 polytope이 주어진 3D 공간을 채우는 문제는 수치해석 관점에서도 굉장히 어려운 문제에 속한다. 인공지능이 붐을 일으키면서 최적화 기법으로 주목 받고 있는 강화학습 (reinforcement learning, RL)이 이러한 문제를 풀기에 적합한데, 계속 이전의 솔루션과 업데이트된 솔루션을 비교하는 것이 가능하기 때문이다. polygon 까지 갈 것도 없이 그냥 타원체를 2차원에서든 3차원에서든 채우는 문제도 수치해석적으로 많은 계산을 요한다. 이러한 packing 문제는 좁게는 자기조립 (self-assembly) 현상부터 넓게는 세포 내에서의 생체 분자들의 상호작용에 이르기까지 수많은 분야에 적용된다.

산업적으로는 어떨까? 당연히 좁은 주차장에 차를 어떻게 몇 대나 주차할 수 있는지의 공간활용 문제나, 비정형 floor plan을 가지고 있는 아파트, 혹은 복잡하게 생긴 반도체의 die에 어떤 가구나 어떤 component를 배치할 것인지와도 연결될 수 있는 문제가 된다. 공장에서 어떤 장비 들을 어떻게 연결할지에 대해서도 이러한 배치 문제, packing 문제는 생각보다 중요한 인사이트를 줄 수 있다. 공학적 응용 사례가 너무 많다 보니 일일이 열거하는 것이 어려울 정도이지만, 우리는 그 이면에 수학적 고민과 원리가 숨어 있다는 생각은 잘 하지 않는다.

우리가 쉽게 인지하는 이러한 현상과 문제들도 알고보면 과학적인 맥락은 물론, 산업적 응용 측면에서도 여전히 우리에게 줄 수 있는 통찰이 많다. 일부는 앞으로 AI를 활용한 연구로 대체될 수 있겠지만, P보다 F가 많은 이러한 문제들 같이, 전혀 엉뚱한 아이디어로 시작된 솔루션이 혁신을 만들어낼 수도 있지 않을까 생각한다. 즐겁고 재미있는 사례다.