현재 위치

홈 ›› Forums ›› 공부 ›› 프로그래밍 QnA

정해진 직사각형에 임의의 사각형들을 집어넣는 방법을 찾습니다.

hjh3105의 이미지
글쓴이: hjh3105 / 작성시간: 월, 2014/08/18 - 11:58오전

안녕하세요 c, java 등을 공부하는 평범한 학생입니다.

정해진 직사각형은 ex)3000 * 1500 (단위는 mm라고 가정하겟습니다.)
임의의 사각형 조각들은 ex) 300 * 600 , 1500 * 200 (정해진 직사각형을 초과하는 임의의 사각형은 없습니다.)등등 다양한 크기입니다.

정해진 직사각형 한개로는 다 못넣을 정도로 많은 조각들이 있을때 여러개의 직사각형을 이용해 남는공간이 가장 적은 방법을 찾고있습니다.
어떤식으로 소스를 짜야할지 모르겟습니다...

아무거나 하나 조각을 잡고 그걸 기준으로 해서 모든 조각들을 다 집어 넣고 남는공간을 산출해 기억해둿다가
다시 처음으로 돌아가서 임의의 조각으로 이전과 같은 방식으로 해서 비교 해서 남는공간이 적은 방식을 찾는 방식밖에 생각이 안나는데요.
조각이 100개만 넘어가도 이런 방식으로 하게되면 실행시간이 너무 오래걸릴꺼같습니다...

참고 해야할 알고리즘이나 조언 부탁드립니다.

Forums: 
프로그래밍 QnA
yukariko의 이미지

글쓴이: yukariko / 작성시간: 월, 2014/08/18 - 4:00오후

배낭 안에 물건을 어떻게 해야 가장 부피를 적게 차지하면서 넣을 수 있을까? 와 비슷한 문제로 여겨집니다.
이것은 대표적인 NP문제로 빠른 해결방법이 현재 존재하지 않으며,
해결하는대에 시간이 기하급수적으로 늘어나는 문제입니다.
현재 사용하시는 방식에 만족하시지 못한다면 그냥 다른 주제를 찾는것을 추천드립니다.
사실 모든 배낭문제가 NP 문제인것은 아니고, 물건을 쪼갤수 있는 경우와 없는 경우로 나뉘는데, 이 글의 경우는 후자로 보입니다.
후자가 NP문제로 널리 알려져 있구요. 전자는 DP로 해결이 가능하다고 합니다.
찾아보시려면 knapsack problem 으로 찾아보시면 될듯하네요.

댓글 달기

텍스트 포맷에 대한 자세한 정보

Filtered HTML

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

BBCode

  • 텍스트에 BBCode 태그를 사용할 수 있습니다. URL은 자동으로 링크 됩니다.
  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param>
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.

Textile

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • You can use Textile markup to format text.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Markdown

  • 다음 태그를 이용하여 소스 코드 구문 강조를 할 수 있습니다: <code>, <blockcode>, <apache>, <applescript>, <autoconf>, <awk>, <bash>, <c>, <cpp>, <css>, <diff>, <drupal5>, <drupal6>, <gdb>, <html>, <html5>, <java>, <javascript>, <ldif>, <lua>, <make>, <mysql>, <perl>, <perl6>, <php>, <pgsql>, <proftpd>, <python>, <reg>, <spec>, <ruby>. 지원하는 태그 형식: <foo>, [foo].
  • Quick Tips:
    • Two or more spaces at a line's end = Line break
    • Double returns = Paragraph
    • *Single asterisks* or _single underscores_ = Emphasis
    • **Double** or __double__ = Strong
    • This is [a link](http://the.link.example.com "The optional title text")
    For complete details on the Markdown syntax, see the Markdown documentation and Markdown Extra documentation for tables, footnotes, and more.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 사용할 수 있는 HTML 태그: <p><div><span><br><a><em><strong><del><ins><b><i><u><s><pre><code><cite><blockquote><ul><ol><li><dl><dt><dd><table><tr><td><th><thead><tbody><h1><h2><h3><h4><h5><h6><img><embed><object><param><hr>

Plain text

  • HTML 태그를 사용할 수 없습니다.
  • web 주소와/이메일 주소를 클릭할 수 있는 링크로 자동으로 바꿉니다.
  • 줄과 단락은 자동으로 분리됩니다.
댓글 첨부 파일
이 댓글에 이미지나 파일을 업로드 합니다.
파일 크기는 8 MB보다 작아야 합니다.
허용할 파일 형식: txt pdf doc xls gif jpg jpeg mp3 png rar zip.
CAPTCHA
이것은 자동으로 스팸을 올리는 것을 막기 위해서 제공됩니다.