01.
샌드박스 카페에서 이야기 중에 달팽이 배열(나선형 이차원 배열)에 대한 주제가 나왔다.
이 달팽이 배열을 출력하기 위해서는 프로그래밍 언어에서 제공하는 형태의 이차원 배열에, 수의 순서를 따라가며 값을 쓰면 된다.
하지만 이 문제를 이차원배열을 사용하지 않고도 풀 수 있을 것 같다는 이야기가 있어 직접 구현해보게 되었다.





02.
우선 '달팽이 배열(spiral matrix)'이란, 수가 행렬을 나선형으로 따라가며 순서대로 배열되어있는 형태를 말한다.


아래 그림은 알아보기 쉽게 선을 그은 것이다.




이와 같은 결과를 이차원배열을 쓰지 않고 구현하려면, x좌표와 y좌표를 매개변수로 넣었을 때 해당 위치의 달팽이배열 값을 반환하는 함수 f(x, y)를 정의해야 한다.






03.

일단 작은 크기인 6x6 달팽이 배열을 보고 규칙성을 찾아보았다.

행렬을 아래 그림과 같이 3부분으로 나누어 보면, 3부분 모두 ㅁ자 모양 안에서 수가 순차적으로 증가하는 패턴을 갖고 있다.

그러므로 ㅁ자 모양으로 수가 이어지는 가장 바깥쪽 패턴만 구현한다면 전체 달팽이 배열도 쉽게 구현할 수 있을 것이다.


이차원배열을 사용하지 않는다는 조건이 있기 때문에 이 부분도 g(x,y)형태의 함수로 나와야 한다.

0부터 10까지의 부분을 보면 이 함수가 g(x,y) = x+y  (x>=y일 때)라는 것을 알 수 있다.


이제 11~19번까지가 문제인데, 우선 19라는 숫자는 nxn배열에서 둘레에 배치된 요소의 수를 구할 때 (n-1)*4로 구하므로, 6x6 배열의 둘레인 20에서 1을 뺀 것이다.

따라서 함수 g(x,y)를 여기까지의 정보로 구해 보면 아래와 같다.

g(x,y) = 

x+y                 (x>=y 일 때)

(n-1)*4 - (x+y)    (x<y 일 때)

 

그런데 이 함수는 안쪽의 ㅁ자 패턴을 구할 때는 좌표가 달라지기 때문에 바로 적용할 수 없다.

행렬위의 임의의 위치(x,y)에 있는 요소가 가장자리에서 떨어져 있는 정도를 먼저 알아야 한다.






04.

임의의 위치 (x,y)에 있는 요소의 가장자리에서 떨어진 정도를 반환하는 함수 h(x,y)를 작성하기 전에, 6x6인 경우와 9x9인 경우의 출력결과를 보면 각각 아래와 같다.




이 함수는 간단하게 만들 수 있는데,

h(x,y) = min(x, y, n-x-1, n-y-1)

을 구하면 끝이다.






05.

이제 04장에서 구한 h(x,y)함수로 03장의 g(x,y)함수를 완성한다.


p = h(x,y)

g(x,y) = 

x+y  - 2p                      (x>=y 일 때)

(n-1 - 2p)*4 - (x+y - 2p)    (x<y 일 때)


2p를 뺀 이유는 한 단계 안쪽 패턴은 한 변을 이루는 요소의 수가 2 만큼 작기 때문이다. 


드디어 이렇게 같은 패턴이 반복되는 결과를 얻을 수 있다!





06. 

달팽이 배열을 얻으려면 아직 한 단계가 남아 있다. 

05장에 있는 그림에서 첫 번째 패턴(껍질)은 0부터 시작해야 하고, 두 번째 패턴은 20부터 시작해야 한다. 그리고 가장 안쪽 패턴은 32부터 시작해야 한다.


일반화를 위해 nxn 행렬에서 p=k일 때 어떤 수부터 시작해야 하는지 유도한다.

안쪽 껍질(p값이 높음)로 갈수록 한 변을 이루는 요소의 개수는 2씩 줄어들고, 바깥쪽 껍질로부터 값이 누적된다.

p=0:    0

p=1:    4*((n-1))

p=2:    4*((n-1)+(n-3))

p=3:    4*((n-1)+(n-3)+(n-5))

p=k:    4*((n-1)+(n-3)+(n-5)+(n-7)+...+(n-(2k-1)))


p=k인 경우를 보면 n이 k개 더해지고,

1+3+5+7+... 과 같이 나아가는 급수의 k번째 일반항은 k*k이므로

원하는 식은,

4*(p*n - (p*p))

이 된다. 이 값을 마지막에 더하면 된다.






07.

아래는 python 3으로 구현한 코드이다.

github 주소 : https://github.com/tibyte/algorithms


1
2
3
4
5
6
7
8
9
10
11
12
n = int(input())
 
for y in range(0, n):
    for x in range(0, n):
        p = min(x,y,n-x-1,n-y-1)
        if x>=y:
            q = x+y - 2*p
        else:
            q = (n-1 - 2*p)*4 - (x+y - 2*p)
        q += 4 * (p*n - (p*p))
        print("{:3d}".format(q), end="")
    print()
cs




08.

n=6일 때와 n=9일 때의 실행결과이다.


n=6



n=9






09.


07장의 코드에서 반복문을 제외한다면, 임의의 위치 (x,y)의 달팽이배열 값을 바로 구할 수 있다.










상자 채우기 (2D bin packing) - (2) Maxrects 알고리즘①

에서 이어지는 포스트입니다.



지난 글에서의 순서를 다시 보면 아래와 같다.


1. 넣을 아이템을 불러온다

2. 남은 공간들 중에서 아이템을 넣을 수 있는 공간을 선택한다. (다양햔 휴리스틱 존재)

3. 해당 공간에 아이템을 넣는다.

4. 넣은 아이템과 겹치는 모든 공간들을 검사한다

5. 넣은 아이템과 겹치는 공간을 분할한다

6. 유효하지 않은 공간을 제거한다. (다른 공간 안에 포함된 공간이나, 높이나 너비 값이 음수인 공간.)

7. 넣을 아이템이 남아있으면 (1)로 돌아간다.


3,4,5,6 번 과정을 그림으로 그려봤을 때


아래 그림은

item1이 넣어져 있는 상태에서 남은 공간은 A와 B로 나누어져 있고,

item2를 넣는 상황이다.

[그림6]

위 그림과 같이 공간 A는 item2에 의해 3개의 새로운 공간으로 나위며

공간 B는 2개의 새로운 공간으로 나뉜다.



그러면 기존 A, B 공간은 사라지고 새로운 5개의 공간이 생기게 된다.

[그림7]




마지막으로, 공간들 사이에 포함관계가 있는 것을 찾아 제거하여 최적화를 한다.

[그림8]




 코드로 작성할 때는 넣을 아이템들의 정보와 분할될 공간들의 정보를 선형적으로 탐색하도록 코드를 작성할 것이기 때문에 링크드 리스트(linked list)구조를 사용하였다. 


 5번 단계를 보면, 아이템과 겹치는 부분이 있는 공간 하나당 0~3개의 새로운 나눠진 공간이 생길 수 있다. 새로 생긴 공간들을 임시 리스트에 넣어두고, 기존에 겹쳤던 공간은 제거한다. 의사코드로 쓰면 아래와 같다.

width>0, height>0 부분은 크기가 음수로 되어 있어 유효하지 않은 공간이 생기는 것을 방지하는 것이다.


for s in spaceList

    if isIntersect(item, s) {

        s_top, s_right, s_bottom, s_left 생성

        if(s_top.width>0 && s_top.height>0) newList.push(s_top)

        if(s_right.width>0 && s_right.height>0) newList.push(s_right)

        if(s_bottom.width>0 && s_bottom.height>0) newList.push(s_bottom)

        if(s_left.width>0 && s_left.height>0) newList.push(s_left)

        spaceList.erase(s)

    }

}


이제 새로운 공간 리스트 (newList)를 기존 리스트(spaceList)와 병합해야 하는데

그 전에 [그림8]처럼 최적화를 해야 한다.

다음과 같은 4가지 조건을 생각해 볼 수 있다.


1. 기존 공간들 간의 포함관계

2. 기존 공간이 새로운 공간을 포함하는 경우

3. 새로운 공간이 기존 공간을 포함하는 경우

4. 새로운 공간 간의 포함관계


여기서 1번은 이 최적화과정이 item을 하나 넣을 때 마다 일어나므로 발생하지 않고, 

3번 또한 발생하지 않아서 고려하지 않아도 된다


2번과 4번의 경우 공간을 제거하여 최적화한 뒤,

newList를 기존 리스트 뒤에 병합하면 된다.



다음은 적용예이다.


적용 예시

아이템들이 모두 같은 크기인 경우

*'잔여 면적'은 적재하지 못한 아이템들의 면적입니다.

[그림9]





작은 아이템부터 큰 아이템까지 고르게 있는 경우

아이템들이 비효율적으로 적재되며 모든 아이템을 넣는 것도 실패한다.

[그림10]

*'잔여 면적'은 적재하지 못한 아이템들의 면적입니다.





작은 아이템부터 큰 아이템까지 고르게 있는 경우

+ 큰 아이템부터 내림차순으로 정렬

아이템을 면적으로 내림차순 정렬하면 공간의 단편화가 적어져서 연산 횟수가 줄어들고, 공간을 효율적으로 차지하게 된다. (정렬은 O(nlogn)으로 할 수 있으므로..)

[그림11]

*'잔여 면적'은 적재하지 못한 아이템들의 면적입니다.






같은 크기의 아이템 집단이 있을 때

이 알고리즘을 알아보게 되었던 목적이 게임 그래픽 리소스 패킹을 위해서였는데,

그 때 가장 많이 볼 수 있을 경우로,

아이템들이 모두 같은 크기일 때처럼 공간을 빼곡히 차지할 수 있다.

[그림12]

*'잔여 면적'은 적재하지 못한 아이템들의 면적입니다.






무작위 + 정렬

이전 포스트에서의 shelf 알고리즘보다 더 좋은 공간효율을 보여준다.

하지만 전체공간의 크기가 고정되어 있어서 모든 아이템들을 넣을 수 없는데,

이 전체공간의 크기를 PO2로 늘려 주는 부분을 다음다음 글에서 작성할 것이다.

[그림13]

*'잔여 면적'은 적재하지 못한 아이템들의 면적입니다.






아이템의 수와 연산횟수의 관계

단위연산은 정렬 시 비교연산 수,

넣을 공간을 찾을 때의 검사 수,

분할할 공간을 찾을 때의 검사 수,

포함관계에 있는 공간을 찾을 때의 검사 수를 더한 것으로 정했다.



아래 그래프에서처럼 아이템이 적을 때는, 아이템의 수가 늘어날수록 연산횟수의 변화율이 커지지만, 일정 수 이상에서는 선형적인 모양이 나온다.

공간을 점점 채워갈수록 고려해야 할 공간의 수가 더이상 늘어나지 않기 때문이다.

따라서 아이템에 비해 상대적으로 충분히 큰 공간을 두고 공간에 아이템이 50%정도 채워질 때까지를 봐야 한다.



[그림14] 가로축은 아이템의 수, 세로축은 연산횟수이다





그렇게 하면 아이템의 수에 따른 연산횟수가 점근적으로 O(n^2)에 근사하는 것을 볼 수 있다.


[그림15] 가로축은 아이템의 수, 세로축은 연산횟수이다




소스코드


GitHub gist에서도 볼 수 있습니다.

https://gist.github.com/tibyte/c0ef27311005e0f2476d


 mxrc3_1.html




관련글

상자 채우기 (2D bin packing problem) - (1) Shelf 알고리즘

상자 채우기 (2D bin packing problem) - (2) Maxrects 알고리즘①




참고글 : http://clb.demon.fi/files/RectangleBinPack.pdf









이전 글

상자 채우기 (2D bin packing problem) - (1) Shelf 알고리즘

에서 이어지는 포스트입니다.



Maxrects(Maximal Rectangle)알고리즘

목차

1. 원리

2. First Fit

3. Best Fit

4. Maxrects-CP



이전 글에서의 문제점을 해결하기 위해서는 남은 공간의 정보를 저장해 두어야 한다.

처음 공간에 아이템이 하나 배치됐을 때 아래와 같은 3개의 영역이 생긴다.

그림1



그런데 위와 같이 세 부분으로 나누면 단편화(fragmentation)가 심해져서 크기가 큰 아이템을 추가로 넣을 수 없다.

따라서 두 부분으로 나누어야 하는데 아래 그림처럼 2가지 선택지가 있다. 이렇게 나누는 방법을 Guillotine Algorithm이라고 한다. 

그림2


하지만 여전히 단편화 현상이 나타나게 된다. 왼쪽 그림에서 B영역과, 오른쪽 그림에서 A영역을 보면 알 수 있다.




따라서 두 공간을 직사각형 모양을 유지하며 최대한으로 확장하여 사용한다.

그림3




여기서 새 아이템을 넣을 때 아이템이 공간A와 공간 B 모두에 겹치는(intersect) 경우가 대부분이다.

겹치는지 아닌지를 판별하는 방법은 http://tibyte.kr/228 이 포스트의 return null 조건 참고.

그림4



다음 단계에서 공간A와 공간B 모두에 대해 새로운 공간을 다시 생성해야 하므로

상하좌우 4방향 모두 고려해야 한다.

그림5

그림에서 흰 부분이 아이템이고, 색이 칠해진 부분이 남은 공간이다.


속성으로 x, y ,w, h 값을 가지는 rectangle객체가 있다고 할 때

위 4개의 남은공간을 나타내는 rectangle객체는 쉽게 얻을 수 있다.


//r은 아이템, s는 아이템과 겹치는 공간.

    rt = {x:s.x     , y:s.y     , w:s.w               , h:r.y-s.y          }   //top

    rb = {x:s.x     , y:r.y+r.h , w:s.w               , h:s.y+s.h-(r.y+r.h)} //bottom

    rl = {x:s.x     , y:s.y     , w:r.x-s.x           , h:s.h              }  //left

    rr = {x:r.x+r.w , y:s.y     , w:s.x+s.w-(r.x+r.w) , h:s.h              }  //right


위 rt, rb, rl, rr 객체 중에서 w(width)나 h(height)속성값이 음수인 객체는 지우면 된다. 







▽ 자바스크립트와 canvas로 구현한 결과. 마우스로 조절점을 드래그해보세요.

(※인터넷 익스플로러 9이상 필요)





이제 Maxrects알고리즘으로 bin packing을 하는 단계를 보면 아래와 같다.

이번 포스트에서는 (4)번과 (5)번을 알아보았다.


(1) 넣을 아이템을 불러온다

(2) 남은 공간들 중에서 아이템을 넣을 수 있는 공간을 선택한다. (다양햔 휴리스틱 존재)

(3) 해당 공간에 아이템을 넣는다.

(4) 넣은 아이템과 겹치는 모든 공간들을 검사한다

(5) 넣은 아이템과 겹치는 공간을 분할한다

(6) 유효하지 않은 공간을 제거한다. (다른 공간 안에 포함된 공간이나, 높이나 너비 값이 음수인 공간.)

(7) 넣을 아이템이 남아있으면 (1)로 돌아간다.


참고로 실제 리소스 패킹 목적으로 구현할 때는 위 순서중 (2)번에서, 적당한 공간이 없으면 전체영역의 크기를 확장해야 한다. 



다음 포스트에서 이어집니다..



이전글

상자 채우기 (2D bin packing problem) - (1) Shelf 알고리즘


다음글

상자 채우기 (2D bin packing problem) - (3) Maxrects 알고리즘② 




참고글 : http://clb.demon.fi/files/RectangleBinPack.pdf


관련글

상자 채우기 (2D bin packing problem) - (1) Shelf 알고리즘

상자 채우기 (2D bin packing problem) - (2) Maxrects 알고리즘(1)  

상자 채우기 (2D bin packing problem) - (3) Maxrects 알고리즘(2) 




 상자 채우기 문제 (bin packing problem)는 최소한의 공간에 최대한의 아이템을 채워넣는 문제로 NP-hard분류에 속한다.

 이 문제를 적용할 수 있는 것은 1차원(linear)에서는 메모리(segmentation) 관리,  2차원에서는 그래픽 리소스 최적화, 3차원에서는 화물 적재 등 주변에서 쉽게 찾아볼 수 있다.

 게임 텍스쳐들을 모아 놓는 스프라이트 시트(sprite sheet)제작 툴에 활용하기 위해 이 알고리즘을 구현해보게 되었다. 참고글 : (http://clb.demon.fi/files/RectangleBinPack.pdf)

 이 글의 마지막에는 JS와 html5 canvas로 구현한 코드를 첨부했다.

 테스트할 사각형들은 미리 무작위로 생성해놓았다.




Shelf 알고리즘

 가장 간단한 해결방법은 Shelf(선반) 알고리즘을 사용하는 것이다. 평행한 선반 위에 물건(이하 아이템)을 올려놓듯이 순서대로 배치하는 것이다. 아이템의 배치 순서를 결정할 때  다양한 휴리스틱(heuristic)들을 적용할 수 있다.


목차

1. Next Fit

2. Smaller Height First

3. Lager Height First

4. Rotate - 회전하기

5. Shelf 알고리즘의 한계

6. Javascript 코드



1. Next Fit

 아이템들을 특별한 기준 없이 순서대로 배치한다. 좌측 상단부터 시작하여 오른쪽으로 아이템들을 배치해나가다가 오른쪽 변에 다다르면 그 층(row)의 최대 높이만큼 내려서 배치한다.

아래 그림과 같이 상당히 비효율적인 것을 확인할 수 있다. 

그림1


의사코드로 작성해 보면 아래와 같다.

nextPos = {x:0, y:0}

for i from 0 to items.length

    if(nextPos + items[i].width > spaceWidth)

        nextPos.x = 0

        nextPos.y += maxHeight

        maxHeight = 0; //reset

    end if

    if(nextPos.y + items[i].height > spaceHeight)

        break;

    end if

    /*allocating item*/

    /*finding a value of max height in this row*/

end for







2. Smaller height first


 넣을 아이템을 높이가 작은 순서대로 정렬한다.

시간복잡도가 O(nlogn)인 정렬 알고리즘으로 정렬한다면, 아이템 배치 부분은 O(n)이므로 총 시간복잡도는 O(nlogn)이다.

 이 테스트케이스에 크기가 더 큰 아이템들도 있지만 더 이상 넣을 공간이 없으므로 끝나게 되었다.

그림2







3. Lager height first


넣을 아이템을 높이가 큰 순서대로 정렬한다. 1.2에서 적재되지 못했던 아이템들을 볼 수 있다. 큰 순서대로 배치하였기 때문에 아래층에 넓은 공간이 남아버리게 된다.



따라서 높이가 맞지 않는 다음 아이템은 건너뛰고, 그 다음 아이템을 적재한다.

1번에 있는 의사코드를 다음과 같이 고칠 수 있다.

if(nextPos.y + items[i].height > spaceHeight)

    ++i;

end if

그림3

이제 아래쪽 빈 공간을 활용할 수 있게 되었다.




그러나 아직도 우측에 빈 공간이 남게 되는데, 아이템의 너비를 생각하지 않고

높이순으로만 정렬했기 때문이다. 

현재 층(row)에서 다음 아이템을 너비 때문에 넣지 못할 경우, 잠시 멈춰 두고 넣을 수 있는 아이템이 나올 때까지 순차탐색한다.  최악의 경우(아이템의 너비가 내림차순으로 정렬되어 있을 때 등)에는 이 때문에 시간복잡도가 O(n^2)가 된다.

다음 층로 넘어갔을 때는 공간이 많이 있으므로 멈췄던 인덱스부터 다시 배치를 시작한다.



배열을 탐색하면서 중간요소들을 지워야 하기 때문에 뒤에서부터 탐색하였다.

그래서 이번에는 items 배열을 높이가 작은 순서대로 정렬해두어야 한다. 

nextPos = {x:0, y:0}

i - items.length

while(i--)

    for j from i to 0

        if(nextPos + items[j].width >= spaceWidth)

            break

        end if

    end for

    if(j>0)

        j = i;

        nextPos.x = 0

        nextPos.y += maxHeight

        maxHeight = 0

    end if

    if(nextPos.y + items[j].height > spaceHeight)

        continue

    end if

    /*allocating item*/

    /*finding a value of max height in this row*/

    items.splice(j,1)

end while

그림4







4. rotate - 회전하기


3번에 있는 휴리스틱을 적용하면 채우기 효율이 매우 완벽해 보인다. 그러나 이런 경우도 있다.

그림5

이 포스트에서 구현한 선반 알고리즘은 높이에 관계없이 한 층 안에서 여러 개의 아이템을 쌓을 수 없기 때문에 위와 같이 두가지 아이템의 높이 차이가 많이 날 경우 빈 공간이 많이 남을 수 있다.


이 문제를 해결하기 위해 사각형을 회전할 수 있다.

현재 쓰고 있는 휴리스틱이 높이 순서 기반으로 되어 있기 때문에 너비가 높이보다 큰 사각형은

90도 돌려서 적재한다. 회전된 아이템은 파란색으로 표시하였다.

그림6

그림5에서 남았던 우측의 빈 공간들은 메워졌으나, 아이템이 수직으로 길게 되어버려서 이번에는 아래쪽 공간이 낭비된다.


 이 공간을 활용하려면 아래쪽 선반을 검사할 때, 회전한 아이템을 다시 원래대로 돌려야 한다.

위에 있는 의사코드에서 해당 부분을 수정했다.

if(nextPos.y + items[j].height > spaceHeight)

    if(items[j].w <= h-p.y)

        swap(items[j].w, items[j].h)

    end if

    else continue

end if

그림7


이제 두 가지 아이템의 크기가 다를 때 나타날 수 있는 문제도 해결된 것처럼 보인다!


한 가지 주의할 점은 회전을 쓸 수 없는 상황도 많다는 것이다. 이미지 리소스를 이 방식으로 저장해 두었다가 불러들일 때 적은 연산으로 다시 90도 복구할 수 없는 상황이라면 회전하지 않고 저장하는것이 더 나을 수도 있다.

그렇지만 OpenGL 등에서는 텍스쳐를 바인딩할 때 텍스쳐 좌표를 자유롭게 지정할 수 있으므로 문제가 되지 않는다. 저장할 이미지 리소스의 정보 파일에 x,y,w,h 및 회전 여부도 같이 저장해 두면 된다.





5. Shelf 알고리즘의 한계


4번까지의 결과를 보면 효율이 나쁠 수 있는 상황에서도 어느 정도 만족할 만한 해답을 이끌어낸 것 같다. 그러나 이 글에서 작성한 Shelf 알고리즘은 한 층 안에서 아이템을 수직으로 쌓을 수 없다는 결점이 있다.

가령 아래와 같이 사각형들의 크기차이가 심할 경우 그 차이만큼의 공간이 낭비될 수밖에 없다.

그림8


이 문제를 개선하려면 단순히 층을 나눠서 아이템을 적재하는 대신에

빈 공간에 대한 정보를 전체적으로 관리할 필요가 있다.

하지만 아이템의 크기가 다양하다면 빈 공간의 정보도 자잘하게 조각나서 매우 많아질 것이기 때문에 역시 문제가 된다.


다음 포스트에서 빈 공간의 정보를 최적화하는 Maxrects (Maximal rectangle) 알고리즘에 대해 알아본다! 



▽ Maxrects 알고리즘으로 그림8에서 사용했던 테스트케이스를 실행한 결과






6. Javascript code

이미지를 그리기 위해 작성한 자바스크립트 코드.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
<html>
    <meta charset="utf-8">
    <body>
    <canvas id="canvas1", width=256, height=256, style="border:1px solid #000000"></canvas>
    <script type = "text/javascript">
        var c = document.getElementById("canvas1");
        var ctx = c.getContext("2d");
 
        //var testCase = [11, 21, 43, 39, 13, 52, 35, 25, 28, 20, 66, 55, 54, 62, 50, 61, 49, 16, 60, 51, 39, 27, 54, 62, 65, 13, 34, 50, 48, 63, 19, 41, 18, 61, 23, 51, 39, 58, 35, 14, 35, 31, 67, 58, 25, 24, 58, 63, 59, 57, 69, 57, 34, 28, 61, 30, 18, 57, 10, 26, 42, 66, 31, 50, 63, 13, 42, 10, 57, 63, 61, 54, 50, 53, 20, 54, 66, 31, 48, 35, 28, 25, 37, 54, 32, 50, 42, 49, 62, 37, 31, 24, 63, 44, 66, 29, 25, 51, 52, 17, 67, 55, 27, 48, 23, 39, 38, 41, 46, 15, 46, 68, 24, 41, 38, 20, 33, 42, 12, 12, 51, 31, 53, 41, 25, 28, 39, 69, 61, 12, 55, 59, 35, 60, 13, 60, 22, 41, 60, 68, 28, 33, 31, 60, 27, 48, 38, 60, 19, 63, 28, 50, 24, 31, 42, 38, 11, 17, 50, 36, 27, 59, 42, 25, 16, 61, 35, 19, 32, 67, 40, 53, 33, 42, 15, 40, 62, 23, 42, 19, 57, 42, 43, 59, 12, 10, 45, 68, 16, 15, 15, 34, 67, 33, 27, 54, 53, 64, 18, 22];
        
        //var testCase = [20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,20, 40,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,40, 30,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,16, 16,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,36, 10,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,10, 36,6,15,6,15,6,15,6,15,6,15,6,15,6,15,6,15,6,15,15,6,15,6,15,6,15,6,15,6,15,6,15,6,15,6,15,6,15,6,15,6];
        
        //var testCase = [10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11, 10,20, 22,11];
 
        var testCase = [160,160,80,80,80,80,60,60,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,20,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10];
 
        //var testCase = [67,75,67,75,67,75,67,75,67,75,67,75,67,75,67,75,67,75,67,75,67,75,67,75,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11,50,11];
 
        var numCase = testCase.length/2;
 
 
        var w = c.width;
        var h = c.height;
 
        var r = new Array();
        var s = new Array();
        for(var i = 0; i<numCase; i++) {
            r[i] = {};
            r[i].w = testCase[i*2];
            r[i].h = testCase[i*2+1];
            r[i].r = false;
 
            //rotation
            if(r[i].w > r[i].h) {
                var temp = r[i].w;
                r[i].w = r[i].h;
                r[i].h = temp;
                r[i].r = true;
            }
        }
        s.push({x:0, y:0, w:w, h:h, v:true});
 
        //sorting
        for(var i=0; i<numCase-1; i++) {
            for(var j=0; j<numCase-1-i; j++) {
                if(r[j].h > r[j+1].h) {
                    var temp = r[j];
                    r[j] = r[j+1];
                    r[j+1] = temp;
                }
            }
        }
        var u = 0; //used space
        var p = {x:0, y:0}; //next point
        var m = 0; //max height
        var i = r.length;
        var j;
        while(i--) {
            //find item for next column
            for(j=i; j>=0; j--) {    
                if(r[j].w <= w-p.x) {
                    break;
                }
            }
            //go to the next row
            if(j<0) {
                j=i;
                p.x = 0;
                p.y += m;
                m=0;
            }
 
            //find item for bottom of space
            if(r[j].h > h-p.y) {
                if(r[j].w <= h-p.y) {
                    var temp = r[i].w;
                    r[i].w = r[i].h;
                    r[i].h = temp;
                    r[i].r = false;                    
                } 
                else continue;
            }
 
            //draw
            var fillStyle;
            if(r[j].r) fillStyle = "#6699CC";
            else fillStyle = "#CC6699";
            drawRect(ctx, {
                x:p.x,
                y:p.y,
                w:r[j].w,
                h:r[j].h}, fillStyle);
            p.x += r[j].w;
            u += r[j].w*r[j].h;
            if(r[j].h>m) m=r[j].h;
 
            //remove item from array
            r.splice(j,1);
        }
        //efficiency
        var e = Math.floor(u/(w*h)*10000)/100; 
        ctx.font="20px Consolas";
        ctx.fillStyle = "#000000";
        ctx.fillText(e+"%",w-70,h-18);


function drawRect(ctx, rect, fillStyle) { ctx.beginPath(); ctx.rect(rect.x, rect.y, rect.w, rect.h); ctx.fillStyle = fillStyle; ctx.fill(); ctx.stroke(); }
    </script>
    </body>
</html>
cs







관련글

상자 채우기 (2D bin packing problem) - (1) Shelf 알고리즘

상자 채우기 (2D bin packing problem) - (2) Maxrects 알고리즘(1) 

상자 채우기 (2D bin packing problem) - (3) Maxrects 알고리즘(2) 










스포츠 경기 등의 리그전에서 각 팀이 다른 모든 팀과 한 번씩 경기를 치르는 것을 라운드 로빈(round robin)이라 한다. 이 리그의 한 주기 스케쥴을 짜는 것은 여러 방법이 있지만, 아래와 같은 방법으로 단순하게 해결할 수 있다.


http://www.sciencedirect.com/science/article/pii/S0166218X04001350

위 사이트의 내용을 참고하여 GIF 애니메이션 이미지를 만들어 보았다.



1. 팀 수가 홀수일 때

각 팀이 다각형의 꼭지점에 배치되어 있다고 생각하고, 수평으로 마주보고 있는 팀과 대전한다.

한 팀은 쉰다.(쉴 수밖에 없다.)

(GIF 애니메이션입니다.)





2. 팀 수가 짝수일 때

1에서 한 팀이 쉬는 대신, 나머지 팀과 대전하면 된다.

짝수 다각형을 사용하면 된다고 생각할 수도 있지만,

그렇게 하면 꼭지점 하나를 사이에 두고 있는 팀과의 대결이 성사되지 못한다.


(GIF 애니메이션입니다.)






3.

2번은 아래와 같이 팀이 이동한다고 생각할 수도 있다.

(GIF 애니메이션입니다.)






소스코드

3번을 C++코드로 작성해 보았다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <string>
#include <stdlib.h>
 
using namespace std;
 
 
int main(void)
{
    
    int *team_id;
    string team[] = { "Heros", "Eagles", "Dinos", "Lions", "Wiz",
                    "Twins", "Wyverns" ,"Tigers","Bears","Giants"};
    int numTeam = (sizeof team)/(sizeof string);
    team_id = (int*)malloc(numTeam*sizeof(int));
 
    for (int i = 0; i < numTeam; i++) {
        team_id[i] = i;
    }
 
    for (int i = 0; i < numTeam - 1; i++) {
        cout << i + 1 << "일차" << endl;
        for (int j = 0; j < numTeam/2; j++) {
            cout << team[team_id[j]] << ":" << team[team_id[numTeam-j-1]] << endl;
        }
 
        for (int j = 0; j < numTeam - 1; j++) {
            team_id[j] = (team_id[j] + 1) % (numTeam - 1);
        }
 
        cout << endl;
    }
    
    return 0;
}
cs




출력결과


1일차
Heros:Giants
Eagles:Bears
Dinos:Tigers
Lions:Wyverns
Wiz:Twins

2일차
Eagles:Giants
Dinos:Heros
Lions:Bears
Wiz:Tigers
Twins:Wyverns

3일차
Dinos:Giants
Lions:Eagles
Wiz:Heros
Twins:Bears
Wyverns:Tigers

4일차
Lions:Giants
Wiz:Dinos
Twins:Eagles
Wyverns:Heros
Tigers:Bears

5일차
Wiz:Giants
Twins:Lions
Wyverns:Dinos
Tigers:Eagles
Bears:Heros

6일차
Twins:Giants
Wyverns:Wiz
Tigers:Lions
Bears:Dinos
Heros:Eagles

7일차
Wyverns:Giants
Tigers:Twins
Bears:Wiz
Heros:Lions
Eagles:Dinos

8일차
Tigers:Giants
Bears:Wyverns
Heros:Twins
Eagles:Wiz
Dinos:Lions

9일차
Bears:Giants
Heros:Tigers
Eagles:Wyverns
Dinos:Twins
Lions:Wiz




문제 링크 (알고스팟)
https://algospot.com/judge/problem/read/ASYMTILING

문제 이해

2 x n크기의 직사각형 공간을 2x1혹은 1x2 크기의 타일로 완전히 채우는 방법의 수를 구하는 문제이다.

타일의 배치가 좌우대칭인 것은 제외한다.


풀이

예를 하나 뽑아서 2 x 6 크기의 공간을 채우는 경우를 생각해 본다.

여기서 2 x 6 크기의 공간을 채우는 여러 경우들을 2가지로 나눌 수 있다.

A. 맨 마지막 타일이 세로로 되어 있음

B. 맨 마지막 타일이 가로로 2개 되어 있음


남은 부분의 크기를 보면,

A의 경우 나머지 공간의 너비는 5이고

B의 나머지 공간의 너비는 4이다.


즉, A에서 남은 부분을 채우는 방법의 수는, 이 문제에서 너비가 5인 공간을 채우는 경우의 답과 같다.

B의 나머지 부분을 채우는 방법의 수 역시 너비가 4인 공간을 채우는 경우의 답과 같다.

여기서 이 문제의 재귀적 속성을 발견할 수 있으며

이 문제를 Dynamic Programing (동적 계획법)으로 풀 수 있다는 것을 알 수 있다.


상향식(bottom-up)으로 어떻게 풀 지를 구체적으로 생각해 보면,

- n=1 일 때 (1 가지)

- n=2 일 때 (2 가지)
- n=3 일 때는  (n=2의 가지수) + (n=1의 가지수)

'n=2의 가지수'는 위 그림에서 A의 경우이고, 'n=1의 가지수'는 위 그림에서 B이다.


- n=4일 때는 (n=3)의 가지수 + (n=2의 가지수)

...

...

..


n = k일 때는 (n=k-1 의 가지수) + (n=k-2 의 가지수)


어디서 본 적이 있는 점화식이 나온다. 바로 피보나치 수열이다.




그런데 문제에서 좌우대칭인 경우는 제외하라는 조건이 있다.

이번에는 채워야 할 공간의 크기가 짝수인 것과 홀수인 것으로 나누어 생각해야 한다.


공간의 크기가 홀수일 때 좌우대칭이 되기 위한 조건은

가운데에 블록이 세로로 있어야 하며 분할된 한 쪽 너비는 (int)n/2이다.


공간의 크기가 짝수일 때는 분할된 한 쪽 너비가 n/2이다.




분할된 너비에 해당하는 경우의 수를 빼면 최종적인 답을 구할 수 있다.






구현

대칭인 경우를 제외시키기 위해 너비의 절반을 구해야 하는데,

피보나치 수열을 구하는 과정에서 같이 계산하도록 했다.


그리고 답을 리턴할 때, 이 문제에서 나머지연산한 결과를 요구하므로

계산 과정에서 그 수를 초과하지 않도록 주의하여야 한다.

A - B%mod + mod 와 같이 더해주면 값이 음수가 되는 것을 방지할 수 있다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <iostream>
 
using namespace std;
 
int main(void)
{
    int mod = 1000000007;
 
    int count;
    int input;
 
    int fibo2;
    int fibo1;
    int fibo;
 
    cin >> count;
 
    while (count--) {
        fibo2 = 0;
        fibo1 = 1;
        fibo = 0;
 
        cin >> input;
        if (input <= 2) {
            cout << 0 << endl;
            continue;
        }
 
        int p1=0, p2=0;
 
        for (int i = 1; i <= input; i++) {
            fibo = (fibo1 + fibo2) % mod;
            if (i == input / 2) {
                p1 = fibo1;
                p2 = fibo;
            }
 
            fibo2 = fibo1 % mod;
            fibo1 = fibo % mod;
 
        }
       
        if (input & 1) {  //input is odd
            p1 = 0;
        }
        cout << (fibo - (p1 + p2)%mod + mod)%mod <<endl;
    }
    //end while
    
    return 0;
}
cs










문제 주소 : https://algospot.com/judge/problem/read/BOARDCOVER

(알고스팟)


문제 이해

격자 모양의 게임판이 주어진다.

입력으로 주어지는 게임판에는 검은 칸과 흰 칸이 있으며

이 중에서 흰 칸을 아래 4가지 모양의 블록으로 채울 때

남은 칸을 모두 채울 수 있는 경우의 수를 구하는 문제이다.

가능한 답을 완전탐색(exhaustive search)해야 한다.



전략

흰 칸을 블록으로 모두 채운 경우에서

이 중 하나의 블록을 제외하여도 나머지 블록은 칸을 모두 채우고 있는 것을 볼 수 있다.

블록이 4가지 모양에 따라 가지를 뻗어 나가면서 탐색한다.



블록 하나를 배치한 뒤 남은 흰 칸을 재귀호출로 넘긴다.

다시 블록 하나를 배치하고 남은 흰 칸을 재귀호출로 넘긴다.


만약 칸을 더 이상 채울 수 없다면 재귀에서 탈출한다.

그리고 다음 단계에서 다른 모양으로(블록은 회전 때문에 4가지 모양이 있다)

흰 칸 채우기를 수행하기 위해 다시 재귀호출을 한다.


만약 칸을 모두 채웠다면 1을 반환한다.

재귀 구조에서 이 수를 누적하여 계산한다.


풀이


가능한 블록의 모양이 위 그림과 같으므로

함수의 구조는 대략 이렇게 될 것이다.

insert (map, free) {  //2차원배열, 남은 흰 칸 수

    int count = 0;

    if (남은 칸이 3의 배수가 아니면) {

        return 0;

    }

    if (남은 칸이 3이고, 채울 수 있는 형태이면) {

        return 1;

    }

    if (남은 칸이 3이고, 채울 수 없는 형태이면) {

        return 0;

    }

    if (1번 블록을 채울 수 있으면) {

        1번 블록을 채운다;

        count += insert(map, free-3);

        1번 블록을 해제한다:

    }

    if (2번 블록을 채울 수 있으면) {

        2번 블록을 채운다;

        count += insert(map, free-3);

        2번 블록을 해제한다:

    }

    if (3번 블록을 채울 수 있으면) {

        3번 블록을 채운다;

        count += insert(map, free-3);

        3번 블록을 해제한다:

    }

    if (4번 블록을 채울 수 있으면) {

        4번 블록을 채운다;

        count += insert(map, free-3);

        4번 블록을 해제한다:

    }

    return count;

}


이 때 생각해 볼 점은, 처음에 블록을 어디부터 채우고,

그 다음에는 또 어디부터 채울 것이냐다.

여기서는 상단, 좌측을 우선하여 블록을 채우기로 했다.

블록을 채우는 순서는 경우의 수에 영향을 미치지 않기 때문에 하단부터 채워도 결과는 같다.


상단,좌측을 우선하여 블록을 채울 때

기준이 되는 점(초록색)과 추가로 검사해야 하는 점(회색)은 아래그림과 같다.




소스코드(C++)


(설명의 블록 번호와 아래 소스코드의 블록 번호는 다릅니다)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
 
#include <iostream>
#include <string>
 
using namespace std;
 
int insert(int **map, int row, int col, int free)
{
 
    //맨윗줄 맨왼쪽 구함
    int tx; //targetX
    int ty; //targetY
    for (int i = 1; i < row-1; i++) {
        for (int j = 1; j < col-1; j++) {
            if (map[i][j] == 1) {
                tx = j;
                ty = i;
 
                //exit
                i = row - 1;
                j = col - 1;
            }
        }
    }
 
    bool p1 = false; //패턴1 : 남, 동
    bool p2 = false; //패턴2 : 남, 남동
    bool p3 = false; //패턴3 : 동, 남동
    bool p4 = false; //패턴4 : 남, 남서
 
    if (map[ty+1][tx] && map[ty][tx+1]) p1 = true;
    if (map[ty+1][tx] && map[ty+1][tx+1]) p2 = true;
    if (map[ty][tx+1] && map[ty+1][tx+1]) p3 = true;
    if (map[ty+1][tx] && map[ty+1][tx-1]) p4 = true;
 
 
    //만약 남은칸이 3이고, 채울 수 있는 형태이면, 1 반환
    if (free == 3) {
        if (p1||p2||p3||p4)
            return 1;
        else
            return 0;
    }
 
 
    int count = 0;
 
    if (p1) {
        //채움
        map[ty][tx] = 0;
        map[ty+1][tx] = 0;
        map[ty][tx+1] = 0;
        //재귀호출
        count += insert(map, row, col, free-3);
        //채운 것 취소
        map[ty][tx] = 1;
        map[ty+1][tx] = 1;
        map[ty][tx+1] = 1;
    }
 
    if (p2) {
        //채움
        map[ty][tx] = 0;
        map[ty+1][tx] = 0;
        map[ty+1][tx+1] = 0;
        //재귀호출
        count += insert(map, row, col, free - 3);
        //채운 것 취소
        map[ty][tx] = 1;
        map[ty+1][tx] = 1;
        map[ty+1][tx+1] = 1;
    }
    
    if (p3) {
        //채움
        map[ty][tx] = 0;
        map[ty][tx+1] = 0;
        map[ty+1][tx+1] = 0;
        //재귀호출
        count += insert(map, row, col, free - 3);
        //채운 것 취소
        map[ty][tx] = 1;
        map[ty][tx+1] = 1;
        map[ty+1][tx+1] = 1;
    }
    
    if (p4) {
        //채움
        map[ty][tx] = 0;
        map[ty+1][tx] = 0;
        map[ty+1][tx-1] = 0;
        //재귀호출
        count += insert(map, row, col, free - 3);
        //채운 것 취소
        map[ty][tx] = 1;
        map[ty+1][tx] = 1;
        map[ty+1][tx-1] = 1;
    }
 
    return count;
}
 
int main(void)
{
    int num;
    cin >> num;
    while (num--)
    {
        int row;
        int col;
 
        cin >> row >> col;
        row += 2;
        col += 2;
        //동적할당
        int **map = new int*[row];
        for (int i = 0; i < row; i++) {
            map[i] = new int[col];
            for (int j = 0; j < col; j++) {
                map[i][j] = 0;
            }
        }
 
        //입력받기
        for (int i = 0; i < row-2; i++) {
            string str;
            cin >> str;
            for (int j = 0; j < col-2; j++) {
                if (str[j] == '.') {
                    map[i+1][j+1] = 1;
                }
            }
        }
 
        
        //자유영역 계산
        //만약 자유영역이 3의 배수가 아니면 기각
        int free = 0;
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (map[i][j] == 1)
                    ++free;
            }
        }
 
        int count;
 
        if (free == 0) {
            count = 1;
        }
        else if (free % 3 != 0) {
            count = 0;
        }
        else {
            count = insert(map, row, col, free);
        }
        cout << count << endl;
 
        for (int i = 0; i < row; i++) {
            delete[] map[i];
        }
        delete[] map;
 
    }
    return 0;
}
 
cs




문제 링크 : https://www.algospot.com/judge/problem/read/POTION

(알고스팟)


문제 이해

어떤 약을 한 단위 만드는 데 필요한 n개의 재료들의 양과

현재 넣은 재료의 양이 입력된다.

이 때 약을 만들기 위해 더 넣어야 하는 재료들의 양을 구하는 문제이다.

입력값은 모두 정수이고,

약을 최소한 1단위 이상은 만들어야 한다.



풀이

완성한 약의 양이 꼭 정수단위일 필요가 없다는 점에 주의해야 한다.

따라서 필요한 재료들의 양을 최대공약수로 나누어

들어가야 하는 재료들의 비를 구했다.


예를 들어 들어가야 하는 3가지 재료의 양이 각각 2 4 6 이라면

최대공약수 2로 나누어 1 2 3 라는 비율을 구한다.

이제 들어가야 하는 재료의 양은 1 2 3 의 정수배인

1 2 3

2 4 6

3 6 8

4 8 10

...

...

과 같이 된다.

(정수배인 이유는 입력되는 재료의 양이 정수이므로)


그런데 문제에서 완성 약을 한 단위 이상 만들어야 한다는 조건이 있으므로

2 4 6 다음부터 검사하면 되는것이다.


여기서 현재 넣은 재료가 3 6 7 이라면

재료추가로 만들 수 있는 값이 위 정수배들 중에서 3 6 8 이므로

약을 완성시키기 위해 0 0 1 만큼의 재료를 더 넣어야 하는 것이다.


최대공약수를 구하는 부분은 유클리드 알고리즘을 사용하였고,

n개 수의 GCD를 구하기 위해 해당 알고리즘을 n-1번 반복하였다.

(관련글 : http://www.tibyte.kr/224)



코드

 

#include <cstdio>

#include <cmath>


using namespace std;


//GCD계산 (유클리드)

int calcGcd(int n1, int n2)

{

int temp;

if (n1 < n2) {

temp = n1;

n1 = n2;

n2 = temp;

}

while (n2 != 0) {

temp = n1%n2;

n1 = n2;

n2 = temp;

}


return n1;

}



int main(void)

{


int numTry;

scanf("%d",&numTry);


while (numTry--)

{

int numElem;

scanf("%d",&numElem);


int *ideal = new int[numElem];

int *curr = new int[numElem];

int gcd;

double curMul = 0;

double maxMul = 0;

int mul;

//비율값 입력받음

for (int i = 0; i < numElem; i++) 

scanf("%d", &ideal[i]);



//비율값의 gcd계산

gcd = ideal[0];

for (int i = 1; i < numElem; i++) 

gcd = calcGcd(gcd, ideal[i]);



//ideal값 재계산

for (int i = 0; i < numElem; i++)

ideal[i] = ideal[i]/gcd;


//현재넣은값 입력받음

for (int i = 0; i < numElem; i++) {

scanf("%d", &curr[i]);

curMul = (double)curr[i] / ideal[i];

if (curMul >maxMul ) maxMul = curMul;

}

mul = ceil(maxMul);

for (int i = 0; i < numElem; i++) {

ideal[i] *= mul;

printf("%d ", ideal[i] - curr[i]); 

}

printf("\n");


}

return 0;

}













두 직사각형이 평면상에 놓여져 있을 때 아래와 같이 7가지로 나누어 생각해 볼 수 있다.





회색 사각형을 기준으로

1. 한쪽 귀퉁이를 덮음

2. 한 변을 덮음

3. 자신의 한 변이 모두 덮임

4. 교차

5. 자신이 포함됨

6. 다른 사각형을 모두 덮음

7. 겹치지 않음



각각의 경우를 나누어 처리할 수도 있으나

1~6의 겹치는 영역(직사각형)을 보면 모두 공통적인 특징이 있다.


겹치는 영역(Intersection)의

왼쪽 변은, 기존 두 사각형의 왼쪽 변 중에서 더 오른쪽에 있는 것

오른쪽 변은, 기존 두 사각형의 오른쪽 변 중에서 더 왼쪽에 있는 것

위쪽 변은, 기존 두 사각형의 위쪽 변 중에서 더 아래쪽에 있는 것

아래쪽 변은, 기존 두 사각형의 아래쪽 변 중에서 더 위쪽에 있는 것

이 된다는 것을 확인할 수 있다.


화면 좌측상단이 원점인 좌표계를 기준으로  코딩할 때 사각형 구조체를 x, y, width, height로 정의한다면, 겹치는영역의

(왼쪽 변) x는 기존 두 사각형의 x중에서 큰 것
(오른쪽 변) width는 기존 두 사각형의 x+width 중에서 작은 것 - x좌표

(위쪽 변) y는 기존 두 사각형의 y중에서 큰 것

(아래쪽 변) height는 기존 두 사각형의 y+height 중에서 작은 것 - y좌표

으로 하면 된다.


-x, -y 가 붙어있는 이유는 해당 속성이 각각 너비와 높이이기 때문.



아래는 Javascript 코드로 작성해 본 것이다.


function getIntersection(r1, r2)
{
    if(r1.x > r2.x+r2.w) return null;
    if(r1.x+r1.w < r2.x) return null;
    if(r1.y > r2.y+r2.h) return null;
    if(r1.y+r1.h < r2.y) return null;

    var rect = {};
    rect.x = Math.max(r1.x, r2.x);
    rect.y = Math.max(r1.y, r2.y);
    rect.w = Math.min(r1.x+r1.w, r2.x+r2.w)-rect.x;
    rect.h = Math.min(r1.y+r1.h, r2.y+r2.h)-rect.y;

    return rect;
}

코드를 보면 두 사각형이 겹치지 않은 경우를 걸러내는 부분이 추가되었다.








이 문제에 대해 조금 다르게 생각해 볼 수도 있는데,

너비가 w이고 높이가 h인 screen이 있을 때

임의의 점에 대하여

그 점이 screen 안에 있을 때는 그대로 표시하고,

screen 밖에 있을 때는 screen의 안쪽 변 끝에 두는 간단한 식이 있다.


x' = min(w, max(0, x))

y' = min(h, max(0, y))


이 식을 한 사각형의 4 꼭지점(초록색)에 각각 적용한다면,

두 사각형의 겹치는 부분이 만드는 새로운 사각형의 4 꼭지점(파란색)을 얻을 수 있다.







연관글 :

자바스크립트로 구현한 결과는 여기에 올림.















문제 링크 : http://judge.koreatech.ac.kr/problem.php?id=1007


32bit 크기의 정수 N개 (N은 1<=N<100001인 홀수)가 입력으로 주어진다.


하나를 제외한 나머지 수는 모두 짝이 있다. (짝수 번 중복된다.)


예시 

입력 : -1 2 0 -1 2

출력 : 0


입력 : 2 2 2 2 5

출력 : 5


입력 : 2 2 2 2 2

출력 : 2

(2와 2가 짝, 다시 2와 2가 짝이 되면 2 하나가 남는다.)



생각 1

integer범위 길이만큼의 배열을 만들어서 각각 몇 번 나왔는지 센다.

=> 메모리 용량 4GB가 필요하므로 비효율적


생각 2

입력이 들어올 때마다 리스트에 넣는다.

리스트에 넣을 때, 리스트를 선형탐색하여 자신과 같은 수가 있으면 그 수를 뺀다.

마지막에 남은 수를 출력한다.

시간복잡도 : O(n^2)

공간복잡도 : O(n)


생각 3

생각2에서 리스트 대신 트리를 사용한다.

시간복잡도 : O(nlogn)

공간복잡도 : O(n)


생각 4

임의의 정수 a, b, c에 대해 a xor b xor c xor b = a xor c 인 성질을 이용한다.

(어떤 정수에 임의의 정수를 짝수 번 xor 하면 원래대로 돌아온다.)

문제에서 한 수를 제외한 나머지 수들은 모두 짝수 번 반복되므로

들어오는 입력을 모두 xor연산하여 누적시키면 답이 나올 것이다.

시간복잡도 : O(n)

공간복잡도 : O(1)



소스코드 (C++)


#include <cstdio>


using namespace std;


int main(void)

{


int numTry;

scanf("%d",&numTry);

while (numTry--)

{

int leng;

scanf("%d",&leng);


int acc = 0;

int num;

for (int i = 0; i < leng; i++) {

scanf("%d",&num);

acc ^= num;

}

printf("%d\n", acc);

}

return 0;

}






 




+ Recent posts

티스토리툴바