database.sarang.net
UserID
Passwd
Database
DBMS
MySQL
PostgreSQL
Firebird
ㆍOracle
Informix
Sybase
MS-SQL
DB2
Cache
CUBRID
LDAP
ALTIBASE
Tibero
DB 문서들
스터디
Community
공지사항
자유게시판
구인|구직
DSN 갤러리
도움주신분들
Admin
운영게시판
최근게시물
Oracle Q&A 40761 게시물 읽기
No. 40761
쿼리 퀴즈입니다(울타리 자르기)
작성자
김흥수(protokhs)
작성일
2015-04-01 09:58
조회수
11,296

울타리 잘라내기

문제 정보

문제

 

너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체하기로 했습니다. 이 때 버리는 울타리의 일부를 직사각형으로 잘라내 재활용하고 싶습니다. 그림 (b)는 (a)의 울타리에서 잘라낼 수 있는 많은 직사각형 중 가장 넓은 직사각형을 보여줍니다. 울타리를 구성하는 각 판자의 높이가 주어질 때, 잘라낼 수 있는 직사각형의 최대 크기를 계산하는 프로그램을 작성하세요. 단 (c)처럼 직사각형을 비스듬히 잘라낼 수는 없습니다.

판자의 너비는 모두 1이라고 가정합니다.

 

입력

 

첫 줄에 테스트 케이스의 개수 C (C≤50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 판자의 수 N (1≤N≤20000)이 주어집니다. 그 다음 줄에는 N개의 정수로 왼쪽부터 각 판자의 높이가 순서대로 주어집니다. 높이는 모두 10,000 이하의 음이 아닌 정수입니다.

 

출력

 

각 테스트 케이스당 정수 하나를 한 줄에 출력합니다. 이 정수는 주어진 울타리에서 잘라낼 수 있는 최대 직사각형의 크기를 나타내야 합니다.

 

예제 입력

3
7
7 1 5 9 6 7 3
7
1 4 4 4 4 1 1
4
1 8 2 2

예제 출력

20
16
8

 

노트

 
 
 
이 문제를 sql로 푸는 것입니다.
단 이 문제는 그냥 푸셔도 되고
그냥 푸시는 것이 쉬우시면
성능에 도전하셔도 됩니다.
 
성능에 도전하실 경우는 
 
create table fence
 
 
as
select
    level no
    ,round(dbms_random.VALUE(10,10000),0) h
from    dual
connect by level <= 20000
/
 
로 테이블을 만드시고 이 테이블에 대하여 1분 내로 결과를 내시면 됩니다.

 

이 글에 대한 댓글이 총 1건 있습니다.

 위 문제를 단순히 곧이 곧대로 sql로 옮기면 대충 다음과 같다.

with base as (

            select   1 no , 7 h from    dual

union all   select   2 no , 1 h from    dual

union all   select   3 no , 5 h from    dual

union all   select   4 no , 9 h from    dual

union all   select   5 no , 6 h from    dual

union all   select   6 no , 7 h from    dual

union all   select   7 no , 3 h from    dual

)

select

    max(a.area) area

from

    (

        select

            a.no

            , b.h

            , b.no - a.no + 1 width

            , min(b.h) over ( partition by a.no order by b.no ) min_h

            , (b.no - a.no + 1) * min(b.h) over ( partition by a.no order by b.no ) area

        from    base a

                , base b

        where   a.no <= b.no

    ) a

/

 

 

 

SQL로 이 문제를 분할 정복법을 활용하여 해결하는 것은 다음과 같다.

 

with base as (

            select  1 no , 7 h from    dual

union all   select  2 no , 1 h from    dual

union all   select  3 no , 5 h from    dual

union all   select  4 no , 9 h from    dual

union all   select  5 no , 6 h from    dual

union all   select  6 no , 7 h from    dual

union all   select  7 no , 3 h from    dual

)

, base_recur ( min_no, max_no, center_no ,lvl ) as

(

    select

        min(no) min_no

        ,max(no) max_no

        ,trunc((max(no) + 1) / 2) center_no

        , 1

    from    base a

    union all

    select

        case when b.lvl = 1 then a.min_no else a.center_no + 1 end min_no

        ,case when b.lvl = 1 then a.center_no else a.max_no end max_no

        ,trunc(((case when b.lvl = 1 then a.min_no else a.center_no + 1 end) + (case when b.lvl = 1 then a.center_no else a.max_no end)) / 2 ) center_no

        ,a.lvl + 1

    from    base_recur a

            , (

                select

                    level lvl

                from    dual

                connect by level < 3

            ) b

    where   a.min_no < a.max_no

    and     a.lvl < 10

)

, calc_recur ( min_no, max_no, center_no, lvl, calc_min_no, calc_max_no,cur_h,area ,calc_seq) as

(

    select

        a.min_no

        ,a.max_no

        ,a.center_no

        ,a.lvl

        ,a.center_no calc_min_no

        ,a.center_no calc_max_no

        ,b.h

        ,b.h

        , 1

    from    base_recur a

            , base b

    where   b.no = a.center_no

    union all

    select

        a.min_no

        ,a.max_no

        ,a.center_no

        ,a.lvl

        ,case when (nvl(b1.h,0) >= nvl(b2.h,0) or a.calc_max_no >= a.max_no ) and a.calc_min_no > a.min_no then a.calc_min_no - 1 else a.calc_min_no end calc_min_no

        ,case when (nvl(b2.h,0) >= nvl(b1.h,0) or a.calc_min_no <= a.min_no ) and a.calc_max_no < a.max_no then a.calc_max_no + 1 else a.calc_max_no end calc_max_no

        ,least(greatest(nvl(b1.h,0),nvl(b2.h,0)) ,a.cur_h)

        ,least(greatest(nvl(b1.h,0),nvl(b2.h,0)) ,a.cur_h) *

            (

                case when (nvl(b2.h,0) >= nvl(b1.h,0) or a.calc_min_no <= a.min_no ) and a.calc_max_no < a.max_no then a.calc_max_no + 1 else a.calc_max_no end

                - case when (nvl(b1.h,0) >= nvl(b2.h,0) or a.calc_max_no >= a.max_no ) and a.calc_min_no > a.min_no then a.calc_min_no - 1 else a.calc_min_no end

            + 1)

        ,calc_seq + 1

    from    calc_recur a

            , base b1

            , base b2

    where   b1.no (+) = a.calc_min_no - 1

    and     b2.no (+) = a.calc_max_no + 1

    and     not (a.calc_min_no - 1 < a.min_no and a.calc_max_no + 1 > a.max_no )

    and     not (

                case when (nvl(b1.h,0) >= nvl(b2.h,0) or a.calc_max_no >= a.max_no ) and a.calc_min_no > a.min_no then a.calc_min_no - 1 else a.calc_min_no end = a.calc_min_no

            and case when (nvl(b2.h,0) >= nvl(b1.h,0) or a.calc_min_no <= a.min_no ) and a.calc_max_no < a.max_no then a.calc_max_no + 1 else a.calc_max_no end = a.calc_max_no

            )

    and     least(greatest(nvl(b1.h,0),nvl(b2.h,0)) ,a.cur_h) > 0

)

select

    max(a.area) area

    ,count(*) cnt

from    calc_recur a

/

 

 

sql이 엄청 복잡해진 것은 내가 실력이 부족해서이고

sql로 재귀호출을 할 수는 없으니(왜냐면 함수가 아니니까)

재귀호출에 의해서 문제가 분할 되는 것을 recursive-with 절을 사용하여 만들어 낸 다음

만들어진 분할된 부분 문제를 해결하고

이를 다시 병합하면 되는 것이다.

 

여기서 핵심 아이디어는 recursive-with 절을 사용한 문제의 재귀적 분할이며

위의 경우는 base_recur 부분이 되겠다.

base_recur 부분에서 원 문제를 연속적으로 두 부분의 부분문제로 만들어 낸다.

base_recur 부분만 select 해보면 그 결과는 다음과 같은데.

 

 

MIN_NO MAX_NO CENTER_NO LVL
1 7 4 1
1 4 2 2
5 7 6 2
1 2 1 3
3 4 3 3
5 6 5 3
7 7 7 3
1 1 1 4
2 2 2 4
3 3 3 4
4 4 4 4
5 5 5 4
6 6 6 4

 

이 목록은 재귀호출을 통해서 문제를 분할할 경우의 목록과 일치하게 된다.

 

그런 다음 부분문제를 해결하는 것은 

책 프로그래밍대회에서 배우는 알고리즘 문제해결전략 1권의 195 페이지를 참조하면 된다.

http://book.naver.com/bookdb/review.nhn?bid=7058764

 

뭐 어쨋든 이 문제를 SQL로 푸는 것의 의미는 SQL로 recursive-with를 사용하면 분할 정복 문제도 풀 수 있다는 것이다.(계층 구조를 직접 표현하는 것 뿐 아니라 계층적 작업이 가능한 것은 recursive-with로 가능하다는...)

 
김흥수(protokhs)님이 2015-04-10 09:13에 작성한 댓글입니다.
이 댓글은 2015-04-10 09:15에 마지막으로 수정되었습니다.
[Top]
No.
제목
작성자
작성일
조회
40764값의 수가 너무 많습니다.라고 에러가 뜨네요~ 알려주세요^^ [4]
짱초보
2015-04-06
7178
40763토,일을 제외한 날짜 카운트 질문 [1]
김영희
2015-04-02
7084
40762TREE 구조 SELECT 질문입니다. [2]
이용헌
2015-04-02
7353
40761쿼리 퀴즈입니다(울타리 자르기) [1]
김흥수
2015-04-01
11296
40760교차되는 값 데이타구하기 query 질문 [6]
강형석
2015-03-31
8182
40759ORA-00979 에러에 대한 문의 [1]
이성근
2015-03-31
6550
40756쿼리 퀴즈입니다.(퀵소트 따라하기) [1]
김흥수
2015-03-30
8631
Valid XHTML 1.0!
All about the DATABASE... Copyleft 1999-2024 DSN, All rights reserved.
작업시간: 0.017초, 이곳 서비스는
	PostgreSQL v16.2로 자료를 관리합니다