하드디스크를 2개 쓰면서 하나는 윈도우, 다른 하나는 리눅스를 설치해 쓰고 있었다.
윈도우가 설치되어 있는 파티션을 포멧 푸 윈도우 재설치를 하고 나니 리눅스에서 다음과 같은 증상이 나타났다.
- 부팅 시 fsck가 실행됨
- $DISPLAY is not set or cannot connect to X server 라는 메시지가 출력되면서 X window가 실행되지 않음.
fsck의 대상 파티션을 보니 기존에 /etc/fstab에서 마운트하고 있던 윈도우쪽 파티션의 uuid가 바뀌어서 그런 것이었다.
$ blkid |
로 새로운 uuid를 확인하여 fstab파일을 고쳤더니 해결.
연관글 : http://tibyte.kr/242
상자 채우기 (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
테스트환경 : Debian linux(데비안), KDE
X window의 설정 메뉴에 없는 설정으로 화면 해상도를 변경하는 법.
설정에 1600x900 해상도가 없어서 직접 추가해보게 되었다.
1. cvt명령으로 원하는 해상도의 modeline을 계산한다.
$ cvt 1600 900
아래와 같은 결과가 출력된다.
이 출력 결과를 잠시 다른 곳에 복사해 둔다.
1600x900 59.95 Hz (CVT 1.44M9) hsync: 55.99 kHz; pclk: 118.25 MHz
Modeline "1600x900_60.00" 118.25 1600 1696 1856 2112 900 903 908 934 -hsync +vsync
modeline에서 각각의 수치는 video timing에 관련된 것이고 아래와 같다.
이름, pixelclock, hdisp, hsync-start, hsync-end, htotal, vdisp, vsync-start, vsync-end, vtotal
(관련 내용은 http://www.arachnoid.com/modelines/ 참고.)
(pixelclock는 초당 뿌려줄 수 있는 픽셀 수)
2. xrandr명령으로 현재 디스플레이 정보를 본다.
$ xrandr
아래 결과가 출력되는데, xxxx connected 라는 부분이 있다.
디스플레이 장치마다 다르게 나오므로 이 부분의 이름을 기억해 둔다.
Screen 0: minimum 320 x 200, current 1360 x 768, maximum 8192 x 8192
xxxx connected primary 1360x768+0+0 (normal left inverted right x axis y axis) 345mm x 194mm
1920x1080 59.93 +
1680x1050 59.95 59.88
1600x1024 60.17
1400x1050 59.98
1280x1024 60.02
1440x900 59.89
1280x960 60.00
1360x768 59.80* 59.96
1152x864 60.00
1024x768 60.00
800x600 60.32 56.25
640x480 59.94
3. xrandr의 newmode와 addmode로 추가한다.
newmode에서 1번에서 복사한 modeline수치들을 붙여넣는다.
(xxxx는 2번에서 확인한 이름)
$ xrandr --newmode "1600x900_60.00" 118.25 1600 1696 1856 2112 900 903 908 934 -hsync +vsync
$ xrandr --addmode xxxx 1600x900_60.00
다시 xrandr를 쳐서 확인해 보면 방금 설정한 해상도가 추가되어 있는 것을 볼 수 있다.
해상도를 적용하려면 xwindow의 디스플레이 설정 메뉴에서 설정해도 되고, 터미널에서도 할 수 있다.
$ xrandr --output xxxx --mode 1600x900_60.00
그러니 이 설정은 컴퓨터를 재부팅하면 초기화된다.
아래와 같이 쉘스크립트로 작성해 두고 xwindow시작 시 자동으로 실행되게 하면 편하다.
(x 시스템마다 다르므로 별도 설정)
#!/bin/sh
xrandr --newmode "1600x900_60.00" 118.25 1600 1696 1856 2112 900 903 908 934 -hsync +vsync
xrandr --addmode xxxx 1600x900_60.00
xrandr --output xxxx --mode 1600x900_60.00
노트북에 240GB짜리 디스크를 2개 장착하고, 논리 파티션을 총 3개로 하여
NTFS, NTFS, ext4로 쓰고 있다. NTFS 하나에는 windows를, ext4에는 리눅스 데비안을 설치한 상태.
리눅스로 부팅 시 윈도에서 포멧한 NTFS 디스크에 접근할 수 없다.
bash를 열고 다음과 같이 마운트해주어야 한다.
$ sudo mount -t [디스크 포맷] [마운트할 디바이스 이름] [마운트 위치]
예시)
$ sudo mount -t ntfs /dev/sda1 /media/drive1
이 때 /dev/sda1과 같은 디바이스 이름은
$ sudo fdisk -l
명령을 통해 알 수 있다.
그런데 컴퓨터를 종료 후 재부팅할 때는 다시 마운트가 풀려 있다.
그래서 부팅 시 자동으로 마운트하도록 설정해야 하는데
이것은 /etc/fstab 파일을 수정해서 할 수 있다.
fstab 파일을 수정하기 전에 먼저
$ sudo blkid
로 해당 드라이브의 UUID를 확인해 둔다.
그리고 슈퍼유저권한으로 fstab 파일을 편집기로 연다.
$ sudo vim /etc/fstab
기존에 드라이브가 하나 이상 추가되어 있을 것이므로 형식을 똑같이 맞춰 주면 된다.
여기서는 디스크식별자, 마운트위치, 포맷, 옵션, dump, 파일 시퀀스 체크 순.
이 항목들에 대한 자세한 내용은 여기(http://movenpick.tistory.com/34) 참고.
예시)
UUID=F4080E4463836387 /media/driveA ntfs default 0 0
※주의 : 잘못 추가시 부팅이 되지 않을 수도 있습니다.
※ UUID 대신 /deb/sda1 과 같은 형식도 가능.
저장하고 재부팅하면 마운트가 되어있는 것을 볼 수 있다!
+)
NTFS에서는 unix와 linux에서 사용하는 권한지정방식과 다른 방식으로 파일권한을 관리하기 때문에
모든 파일의 권한이 777로 나온다..
티스토리 초대장 10장 배포합니다.
아래 양식에 맞추어 알맞게 작성해주신 분께 순서대로 드립니다.
1. 블로그 개설 목적
2. 기존 블로그 주소(있을 경우)
3. 티스토리 아이디로 쓸 메일주소 (초대장 받을 메일)
전송 후 24시간 내 수령하지 않는 경우에는 취소될 수 있습니다.
마감되었습니다.
이전 글
상자 채우기 (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 |
OpenGL로 외부 이미지파일을 읽어와서 출력할 때
glDrawPixels()함수를 쓰는 방법과 텍스쳐(texture)를 사용하는 방법이 있는데,
glDrawPixels()는 그릴 때마다 메인 메모리에서 픽셀값들을 읽어들이는 반면
텍스쳐는 생성할 때 그래픽 처리 장치의 메모리에 저장되므로 속도가 더 빠르다.
또한 텍스쳐를 그릴 때 확대/축소와 위치 지정을 자유롭게 할 수 있다.
먼저 테스트용으로 쓸 이미지 배열을 만든다.
여기서는 텍스쳐 포멧으로 RGBA_8888를 사용할 것인데,
Red, Green, Blue, Alpha(불투명도)에 해당하는 정보들을 각각 8비트(1바이트)씩 사용하는 방법이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 | int w = 100; int h = 100; GLubyte map[100*100*4]; int i,j; for(i=0; i<h; i++) { for(j=0; j<w; j++) { map[w*i*4+j*4+0] = 0x99; //Red map[w*i*4+j*4+1] = 0x99; //Green map[w*i*4+j*4+2] = 0xCC; //Blue map[w*i*4+j*4+3] = 0xAA; //Alpha } } |
100x100 크기의 0x9999CCAA색 사각형을 나타내는 1차원 배열이 생성된다.
(그릴 때는 2차원으로 처리된다.)
알파 채널을 사용하기 위해 GL_BLEND를 활성화하고,
텍스쳐id로 텍스쳐를 생성한 뒤 glBindTexture()로 텍스쳐id와 텍스쳐라이징 대상을 연결한다.
그리고 glTexImage2D()로 텍스쳐로 쓸 GLubyte 배열을 쓴다.
glTexParameteri()로 확대/축소시 텍스쳐 필터를 설정하고
glTexEnvi()로 텍스쳐 환경 설정을 한다.(레퍼런스 참고)
glEnable(GL_BLEND); glTexImage2D( |
텍스쳐의 너비와 높이가 각각 2의 거듭제곱 꼴일 때 높은 성능을 얻을 수 있다.
(메모리에 2의 거듭제곱 단위로 할당되기 때문에..)
OpenGL ES에서는 아예 2의 거듭제곱꼴만 하용하고 있다.
예시) 64x128, 128x128, 256x64 등
이제 텍스쳐를 그리는 부분이다.
여기서는 평면상에 텍스쳐를 그릴 것인데, 먼저 OpenGL의 좌표계에 대해 알아야 한다.
별도의 설정을 하지 않을 시, 화면의 중앙이 원점이 되며 우측 상단으로 갈 수록 x와 y 값이 각각 증가한다.
우측 상단 꼭지점의 좌표는 (1, 1)이다.
텍스쳐 이미지 자체의 좌표는, 이미지의 좌측하단이 원점이며,
이미지의 우측상단이 (1, 1)이다.
glOrtho()함수를 쓰면 좌표계(클리핑 범위)를 재설정할 수 있다. 형식은 아래와 같다.
glOrtho(왼쪽, 오른쪽, 아래, 위, z축 근거리방향, z축 원거리방향)
2D만 고려할 때, glOrtho(0, 너비, 높이, 0 정도로 지정하면
MFC, JS 등에서처럼 좌측상단을 원점으로 쓸 수 있다.
glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT); |
glTexCoord2f()로 그릴 텍스쳐 영역을 지정할 때
텍스쳐가 뒤집혀 있는 상태이므로 아래와 같은 순서로 그린 것이다.
아래는 png 이미지를 로드하여 화면에 두 번 표시해본 화면이다.
이미지를 로드하기 위해 SDL2를 사용했는데, SDL2 대신 glut과 pnglib라이브러리를 써도 png 이미지파일을 읽어올 수 있다. (pnglib라이브러리 없이도 BMP파일은 로드 가능.)
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 | #pragma comment (lib,"SDL2") #pragma comment (lib,"SDL2main") #pragma comment (lib,"SDL2_image") #pragma comment (lib,"opengl32.lib") #include <cstdio> #include <SDL.h> #include <SDL_opengl.h> #include <SDL_image.h> using namespace std; SDL_Renderer *renderer; int main(int argc, char **argv){ int winWidth = 800; int winHeight = 600; SDL_Window *win = NULL; SDL_Renderer *renderer = NULL; SDL_Surface *image; SDL_RWops *rwop; rwop = SDL_RWFromFile("../res/img.png", "rb"); image = IMG_LoadPNG_RW(rwop); GLubyte *map = (GLubyte*)image->pixels; int w, h; w = image->w; h = image->h; if (SDL_Init(SDL_INIT_VIDEO) < 0) return 1; win = SDL_CreateWindow("gl", 100, 100, winWidth, winHeight, SDL_WINDOW_OPENGL); renderer = SDL_CreateRenderer(win, -1, SDL_RENDERER_ACCELERATED); SDL_GLContext context; context = SDL_GL_CreateContext(win); glBlendFunc(GL_SRC_ALPHA, GL_ONE_MINUS_SRC_ALPHA); glEnable(GL_BLEND); glEnable(GL_TEXTURE_2D); GLuint texId; glGenTextures(1, &texId); glBindTexture(GL_TEXTURE_2D, texId); glTexImage2D( GL_TEXTURE_2D, 0, GL_RGBA, w, h, 0, GL_RGBA, GL_UNSIGNED_BYTE, map ); glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR); glTexParameteri(GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_LINEAR); glTexEnvi(GL_TEXTURE_ENV, GL_TEXTURE_ENV_MODE, GL_REPLACE); while (1) { SDL_Event e; if (SDL_PollEvent(&e)) { if (e.type == SDL_QUIT) break; else if (e.type == SDL_KEYUP && e.key.keysym.sym == SDLK_ESCAPE) break; } glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT); glOrtho(0, winWidth, winHeight, 0, -1, 1); glMatrixMode(GL_PROJECTION); glLoadIdentity(); glBindTexture(GL_TEXTURE_2D, texId); glBegin(GL_QUADS); glTexCoord2f(0.0, 0.0); glVertex2f(0, 0); glTexCoord2f(1.0, 0.0); glVertex2f(w, 0); glTexCoord2f(1.0, 1.0); glVertex2f(w, h); glTexCoord2f(0.0, 1.0); glVertex2f(0, h); glEnd(); glBegin(GL_QUADS); glTexCoord2f(0.0, 0.0); glVertex2f(0+30, 0+30); glTexCoord2f(1.0, 0.0); glVertex2f(w+30, 0+30); glTexCoord2f(1.0, 1.0); glVertex2f(w+30, h+30); glTexCoord2f(0.0, 1.0); glVertex2f(0+30, h+30); glEnd(); SDL_GL_SwapWindow(win); SDL_Delay(21); } SDL_GL_DeleteContext(context); SDL_DestroyRenderer(renderer); SDL_DestroyWindow(win); return 0; } | cs |
