STEAM R&E 연구결과보고서
(우리 집 좁은 공간에 짐정리 더 잘 해 볼 수 없을까?)
2016. 11. 30.
대구혜화여자고등학교
< 연구 결과요약 >
과 제 명 우리 집 좁은 공간에 짐정리 더 잘 해 볼 수 없을까?
연구목표
아파트와 같은 좁은 공간에서 집안 살림을 어떻게 정리하면 보관공간을 최소화할 수 있겠는가 하는 문제의 답을 구하는 방법을 제시한다. 이 방법을 찾기 위해 수학적 모델과 접근방식을 활용하여 배치문제를 정의하고 그 해답을 알고리즘 형태로 구현하여 제시한다.
연구내용
좁은 공간에서 살림을 어떻게 정리하면 보관공간을 최소화할 수 있겠는가 하는 문제를 다음과 같이 추상화하여 수학문제로 풀어보는 것이 이 연구의 내용이다. 즉, “이차원 공간에서 주어진 여러 개의 크기가 다른 정사각형을 직사각형 위에 그 면적과 둘레의 합이 최소가 되도록 배치하는 방법”을 찾아 알고리즘 형태로 제시하는 것이다.
이 연구의 단계별 연구내용은 다음과 같다.
○ 1단계 (문제정의): 수학적 추상화 과정을 통한 문제정의, 배치알고리즘 구현, 성능평가, 최적성 증명 기본 방향 탐색
○ 2단계 (문제해결): 1단계에서 정의한 문제를 해결할 수 있는 독창적인 배치알고 리즘 (“OOH 알고리즘”) 구현, 성능평가, 최적 조건을 찾아 제시하는 연구 수행
○ 3단계 (구현): 2단계에서 제시한 배치알고리즘을 컴퓨터 프로그램으로 구현, 다른 배치알고리즘과 성능 비교, 제안한 배치알고리즘의 성능을 더 개선할 수 있는 방법 연구
○ 4단계 (배치결과 시각화) 배치알고리즘을 수행하여 얻은 결과를 시각화 해서 보여줌으로써 배치결과를 눈으로 확인할 수 있도록 함
연구성과
이 연구에서 목표한 바와 같이 수학적 추상화 과정을 통해 생활환경의 문제를 수학 문제로 풀어보는 기회를 가질 수 있었다. 그 결과로, “이차원 공간에서 주어진 여러 개의 크기가 다른 정사각형을 직사각형 위에 그 면적과 둘레의 합이 최소가 되도록 배치하는 방법”을 알고리즘 형태로 제시하였고 컴퓨터 프로그램으로 작동 및 그 성능도 확인할 수 있었다. 이러한 기회를 통해 탐구에 대한 흥미와 대표적인 배치알 고리즘과 성능을 비교하는 과정을 통해 수행한 연구의 우수성을 확인하도록 하여 학생들이 자부심을 갖도록 하는 프로그램으로써 성과를 얻었다. 이 문제풀이 과정 에서 수리적이고 논리적인 사고와 문제해결 방법을 배우고 나은 성능의 방법을 찾아가는 과정에서 협업의 중요성도 경험할 수 있었다.
주요어 (Key words)
배치알고리즘, 최소면적 배치, 최적성, 시각화.
< 연구 결과보고서 >
1. 개요
□ 연구목적
○ 아파트를 중심으로 한 우리나라의 주거환경에서는 좁은 공간도 잘 활용해야 한다.
집안 살림을 잘 정리해서 보관하면 아파트와 같은 좁은 공간에서는 그만큼 주거공간을 넓고 안락하게 활용할 수 있게 되기 때문이다.
- 이 연구의 동기는 어떻게 짐을 배치하면 보관공간을 최소화할 수 있겠는가 하는 호기심 에서 시작되었고 보관공간을 최소화하도록 짐을 배치하는 방법을 찾아보려는 것이다. - 이 연구의 목적은 아파트와 같은 좁은 공간에서 집안 살림을 어떻게 정리하면 보관공간
을 최소화할 수 있겠는가 하는 문제의 답을 구하는 방법을 알고리즘으로 제시하는데 있다. 이를 통해 실생활에서도 쉽게 활용할 수 있도록 배치방법의 기본규칙을 실생활의 지혜로 정리하여 결과로 제시하는 것이다. 이러한 연구과정을 통해 문제해결을 위한 논리적이고 체계적인 방법을 배운다.
□ 연구범위
○ 좁은 공간에서 살림을 어떻게 정리하면 보관공간을 최소화할 수 있겠는가 하는 문제를 다음과 같이 추상화하여 수학문제로 풀어보는 것이 이 연구의 내용이다. 즉, “이차원 공간에서 주어진 여러 개의 크기가 다른 정사각형을 직사각형 위에 그 면적과 둘레의 합이 최소가 되도록 배치하는 알고리즘”을 찾아 제시하는 것이다. 분야로 구분하면 수학과 컴퓨터 소프트웨어가 관련 연구분야가 된다.
단계별 연구진행 내용은 다음과 같다.
○ 1단계 (문제정의): 수학적 추상화 과정을 통한 문제정의, 배치알고리즘 구현, 성능평가, 최적성 증명 기본 방향 탐색
○ 2단계 (문제해결): 1단계에서 정의한 문제를 해결할 수 있는 독창적인 배치알고 리즘 (“OOH 알고리즘”) 구현, 성능평가, 최적 조건을 찾아 제시하는 연구 수행
○ 3단계 (구현): 2단계에서 제시한 배치알고리즘을 컴퓨터 프로그램으로 구현,
다른 배치알고리즘과 성능 비교, 제안한 배치알고리즘의 성능을 더 개선할 수 있는 방법 연구
○ 4단계 (배치결과 시각화) 배치알고리즘을 수행하여 얻은 결과를 시각화 하여 보여줌으 로써 배치결과를 눈으로 확인할 수 있도록 함
2. 연구 수행 내용
□ 이론적 배경 및 선행 연구
○ 자료조사를 통해 1950년대 이미 관련된 연구가 시작되었고 현재도 관련 연구가 활발하 게 진행되고 있다는 것을 확인하게 되었다. 그러나 자료가 방대하고 수많은 방법이 제시되었고 또 이론 연구가 중심을 이룬다는 점에서 어려움이 있었으나 최근에 실용적 인 알고리즘이 제시된 바가 있어 이 개념을 발전시킬 수 있다고 보고 연구를 시작하였 다.
○ 선행연구 과정에서 다양하게 변형된 많은 배치문제가 있다는 것을 알게 되었다 [Lodi 2004, Hougardy 2011, Code project 2016]. 현재까지도 많은 배치방법이나 알고리즘이 제안되고 있고 그만큼 난해한 문제임을 확인 할 수 있었다.
□ 연구주제의 선정
○ 이 연구의 주제는 보관공간을 최소화하도록 짐을 배치하는 체계적 방법을 찾아보려는 학생들의 호기심에서 시작되어, 참여 학생들은 이 문제를 “이차원 공간에서 주어진 여러 개의 크기가 다른 정사각형을 직사각형 위에 그 면적과 둘레의 합이 최소가 되도록 배치하는 방법”을 찾는 비교적 쉬워 보이는 문제로 추상화하여 함께 풀어 모는 것으로 시작되었다. 본 책임 지도교사는 수학교육 전공으로 이 문제에 대해 연구한 경험은 없지만 수학적이고 논리적인 사고력을 키울 수 있는 좋은 문제로 파악 하고 이 연구를 시작하였다. 프로그램 개발과정과 시각화는 전문가의 도움으로 완성하 였다.
□ 연구 방법
○ 1단계 (문제정의): 수학적 추상화 과정을 통한 문제정의, 배치알고리즘 구현, 성능평가, 최적성 증명 기본 방향 탐색
- 책임교사와 학생 모두 같이 참여하여 함께 문제 방향 탐색 및 검토
○ 2단계 (문제해결): 1단계에서 정의한 문제를 해결할 수 있는 독창적인 배치알고 리즘 (“OOH 알고리즘”) 구현, 성능평가, 최적 조건을 찾아 제시하는 연구 수행 - 문제 해결과정의 경험을 활용하여 모든 참여 학생이 독립해서 해결할 수 있는 독창적인
배치알고리을 하나씩 제안하고 각 배치 알고리즘의 장점은 살리고 단점을 보완하여 최종 배치알고리즘을 제안
- 성능평가 및 교구의 활용에 대해 검토
- 제안한 배치알고리즘이 최적이 될 수 있는 특정한 예제 문제를 찾아 봄
○ 3단계 (배치알고리즘 구현)
- 1, 2단계에서 구한 배치알고리즘을 전문가의 도움을 받아 컴퓨터 프로그램으로 구현 - 현재 개발된 배치알고리즘의 개념을 배우고 참여 학생의 배치알고리즘과 성능비교 - 현재 개발된 배치알고리즘의 개념을 활용하여 제안한 배치알고리즘의 성 능을 더 개선할
수 있는 방법 연구
○ 4단계 (배치알고리즘 배치결과 시각화)
- 3단계에서 구현한 배치알고리즘을 전문가의 도움을 받아 컴퓨터에서 수행하고 결과를 시각화해서 보여줌으로써 배치결과를 눈으로 확인할 수 있도록 함
- 이 연구문제에서 다루었던 정사각형이 아닌 직사각형의 경우나 3차원 문제의 경우 더 생각해야 할 문제는 무엇인지 해결방법은 어떤 것이 있는지 토론
□ 연구 활동 및 과정
○ 정사각형 모양 배치가 면적과 둘레의 합이 최소가 되도록 하는 비교적 간단한 배치방법 이라는 가설로 배치알고리즘을 설계하고 구현하였다. 컴퓨터 실험을 통해 배치성능을 파악하여 이 가설을 확인하였다.
○ 이러한 과정에서 자석칠판과 다양한 크기의 정사각형 교구를 제작하여 이용하여 다양한 문제를 만들어 배치알고리즘의 성능을 파악하도록 계획하였으나, Microsoft Visio, Excel, Power Point 등을 이용하면 더 편하게 실험할 수 있음을 알 수 있었고 이를 실험에 활용하였다.
○ 배치성능이 배치하려는 정사각형의 개수와 크기에 영향을 받을 것으로 예상하여 이를 확인할 수 있도록 다음과 같은 표로 정리된 실험을 설계하였다. (괄호 안은 표본 수를 표시한다.)
○ 월별 연구 추진 실적
4 5 6 7 8 9 10 11
l 수학적 추상화 과정을 통한 문제정의
l 최적성 증명 기본 방향 탐색
l 배치알고리즘 (“OOH 알 고리즘”) 구현, 성능평가 l 최적 조건을 찾아 제시하
는 연구 수행
l 컴퓨터 프로그램으로 구 현, 다른 배치알고리즘과 성능 비교
l 배치결과 시각화
l 발표자료 및 최종 보고서 작성
3. 연구 결과 및 시사점
□ 연구 결과
○ 정사각형 모양 배치가 면적과 둘레의 합이 최소가 되도록 하는 비교적 간단한 배치방법 이라는 가설로 배치알고리즘을 설계하고 구현하였다. 이 배치알고리즘을 “OOH 알고리 즘”이라고 이름을 붙였다.
○ “OOH 알고리즘” 배치 결과 예
○ 실험 결과
배치성능이 배치하려는 정사각형의 개수와 크기에 영향을 받을 것으로 예상하여 이를 확인할 수 있도록 앞에서 설명한 대로 실험을 설계하여 수행하였다. (괄호 안은 표본 수를 표시한다.) 배치성능은 Sprites 알고리즘(Korf 2003)과 다음과 같은 기준을 이용하여
비교 하였다.
표 1. 배치성능
이 기준에 따른 배치성능은 채워 넣는 정사각형의 개수기 10에서 20으로 증가하면 1.077 에서 1.049로 좋아지고, 변 길이가 3배 증가하면 1.056에서 1.070으로 나빠지는 것을 알 수 있다. 이것은 예상한 바와 같이 정사각형의 개수가 많고 크기가 작을 때 배치성능이 나아지는 것을 알 수 있다. 총 180개 표본에 대해 이 성능지수가 평균 1.063으로 나타났다.
이 결과는 OOH 알고리즘이 Sprites 알고리즘 보다 훨씬 간단하지만 배치성능은 비슷한 정도로 우수한 성능을 갖는다는 것을 보여준다.
○ 결론
정사각형의 개수가 많고 크기가 작을 때 더 효율적으로 배치할 수 있다는 것을 알 수 있다. 제안한 배치알고리즘 OOH 알고리즘이 효율적이고 성능이 우수하다는 것을 확인 하였다.
□ 시사점
○ 살림정리의 요령
1. 큰 것부터 배치
2. 짐을 작게 만들어서 배치
○ 3차원 베치문제에 대한 연구가 더 진행되어야 한다.
4. 홍보 및 사후 활용
○ 이 연구결과는 수학 동아리 실험실에 전시하여 이 문제가 흥미로운 수학문제라는 것을 더 많은 학생들이 발견하고 더 나은 방법을 찾는데 도전할 수 있도록 한다. 이 연구과정에서 만든 컴퓨터 프로그램도 관심 있는 학생들이 실행해 볼 수 있도록 참여 학생의 동아리 홈페이지에 탑재하여 공유하도록 한다.
○ 본교의 학술제에 참여하여 연구 과정과 결과를 전시하고 본교 학생들에게 프레젠테이 션을 하여 함께 공유하도록 한다. 학술제에서 부스를 설치하고 포스터를 설치하여 본교 학생들이 본 연구과제에 대해 이야기해보는 시간을 가짐으로써 연구활동에 참여 한 학생들뿐만 아니라 본교의 학생들에게 STEAM교육에 대한 흥미를 유발하고자 한다.
5. 참고문헌
Code Project (2016) Fast optimizing rectangle packing algorithm for building CSS Sprites.
Hougardy, S. (2011) On packing squares into a rectangle, Computational Geometry, vol. 44, issue 6, pp.
456–463, 2011.
Korf R. E. (2003) Optimal rectangle packing: initial results, Proceedings of 13th International Conference on Automated Planning and Scheduling, pp. 287-295.
Lodi, A., Martello S. and Monaci, M. (2004) Two-dimensional packing problems: a survey, European Journal of Operational Research, 141, pp. 241-252.
부록: OOH 알고리즘 최적배치의 충분조건
