[전남대]문제해결프로젝트 철판자르기 최종보고서

소개글

[전남대]문제해결프로젝트_철판자르기 최종보고서

목차

1. 문제해결 방법에 대한 설명
2. 각 테스트 케이스에 대한 좌표, 너비, 높이 길이
3. GUI 결과
4. 결과 확인 동영상
5. 코드 실행 결과
6. 시간 복잡도 분석

본문내용

1. 이 문제에 대한 정확한 답이 없다는 것을 이미 알고 있다. --> 큰 후판부터 넣는 탐욕법으로 문제를 해결할 수밖에 없다는 것을 정의.
2. 이진탐색으로 한 변의 길이를 가정하도록 한다.
3. 두변이 있는 공간에 최대한 많은 후판을 삽입하도록 한다. --> 결국 빈 패킹 문제가 된다.
4. 들어갈 수 있는 공간에 후판을 옆으로 세울지 가로로 눕일 지는 결과를 보고 알 수 있기 때문에 그 순간 회전을 랜덤으로 부여함 (optimize한 결과만 얻어냄)
5. 들어가고 남은 공간들을 새롭게 공간리스트에 삽입하도록 한다.(각 공간들이 겹치는 경우가 없어야 한다.)
6. 공간에 모든 후판이 들어갈 수 있다면 이진탐색으로 길이를 줄여 다시 위 방식을 반복한다.(들어갈 수 없다면 이진탐색으로 길이를 늘려 위 방법을 반복한다.)

문제를 푸는데 생기는 한계 :

랜덤으로 optimize한 결과를 얻어내기는 하지만 그 확률이 100%가 될 수 없다는 것이 아쉽다. 큐, 우선 순위큐, 스택, 덱, 트리 등 많은 방법을 생각해봤지만 다시 처음 상태로 되돌아가서 값을 돌려야 한다는 것에 시간 time over(1초 초과) 가 생길 수밖에 없다는 것을 알았다. 그렇다고 모든 경우의 수(ex : 80개 --> 시간 :80!(Factorial) )로 풀 수는 없는 것이다. 랜덤적으로 세울지 말지를 결정하는 것에 좋은 방법이 있는지 더욱 고민해야할 것이다.

참고 자료

없음