출처

ACM-ICPC Asia Regional - Daejeon (링크)

BAEKJOON Online Judge (링크)





문제이해


 1회에 1$짜리 버스 티켓과 2$짜리 기차 티켓이 있다.

그리고 1일, 7일, 30일 무제한 이용권이 있는데, 여기서는 버스티켓과, 버스와 기차를 모두 탈 수 있는 티켓으로 나뉜다.

 총 여행한 날짜와 각각의 날에 버스와 기차를 이용할 횟수가 입력으로 주어졌을 때 제시된 티켓들을 조합하여 티켓 값의 최소비용을 구하는 문제이다.





문제접근


 d[i]를 i일까지 여행했을 때 든 최소비용으로 정의한다. 그리고 하루 전까지 계산한 최소비용 d[i-1]에 오늘 탈 비용을 더하면 되는데, 7일권과 30일권 티켓도 있으므로 7일전과 30일전에서 각각 7일과 30일 티켓을 구입하여 올 경우도 생각해야 한다. 그러면 다음과 같이 7개의 선택지를 비교하여 min값을 구할 수 있다.


- d[i-1] + 버스 낱개 + 기차 낱개 구입비용

- d[i-1] + 버스 하루이용권 + 기차 낱개 구입비용

- d[i-1] + 하루이용권 구입비용

- d[i-7] + 버스 7일권 + 7일간 기차 최소비용

- d[i-7] + 7일권 구입비용

- d[i-30] + 버스 30일권 + 30일간 기차 최소비용

- d[i-30] + 30일권 구입비용


 주의할 점은 30일 버스티켓을 이용하고 있는 도중에도 7일짜리 버스+기차 티켓을 추가로 사는 것이 이득일 때가 있다는 것이다.


이제 위에서 진하게 표시한 '7일간 기차 최소비용'과 '30일간 기차 최소비용'을 구하는 것이 문제인데,

전자를 보면 7일권과 1일권의 가격 차이 때문에 버스 7일이용권을 구매한 상태에서, 버스+기차 하루이용권을 구매하는 것은, 7일간의 모든 날짜를 하루이용권만 가지고 계산하는 것보다 비용이 같거나 더 든다. 따라서 7일간 기차이용권을 낱개구매하는 것만 고려하면 된다.


30일간 기차 최소비용은 슬라이딩 윈도우를 사용하여, 하루이용권을 구매해야 이득인 연속된 날짜가 7일 이상 있는지 확인하여 할인차액(6$)를 뺀다.





구현


 최대 날짜 수가 10000일인데, 길이가 30인 슬라이딩 윈도우를 사용할 것이므로 조건을 간단히 하기 위해 배열 길이를 10060으로 선언하여 구현하였다.

 기차를 탄 횟수도 저장이 필요하여 역시 10060길이로 선언해서 배열 용량으로 총 20120*4 바이트를 사용하였다.





코드


https://github.com/tibyte/algorithm-problems/blob/master/baekjoon/10456.cpp

출처

Codeforces

(http://codeforces.com/problemset/problem/711/B)



문제이해

빈 칸을 의미하는 0이 한 개만 포함되는 불완전한 마방진이 입력으로 주어진다.

가로, 세로, 대각선의 합이 같은 마방진을 성립하게 하려면 어떤 수를 0 자리에 채워 넣어야 하는지 구하는 문제이다.

채워 넣을 수는 양의 정수로 한정된다. 채워 넣을 양의 정수가 없다면 -1을 출력하고, 있다면 그 수를 출력해야 한다.



문제접근

각각의 행 합, 열 합, 대각선 합을 구해서 

합이 다른 것을 찾는데, 그 행이나 열에는 0이 들어있어야 한다.


코드포시스 라운드에 참가할 때 

7 0 5

2 4 6

3 8 1

이런식으로 빈 칸에 0을 채워야 될 경우 -1을 출력해야 하는데

0을 출력해서 계속 W/A가 떴었다..


먼저 0이 들어있는 위치를 구하고,

0이 들어있지 않은 각각의 모든 행과 열들의 합을 구해서 합이 모두 같은지 검사한다.

그리고 그 합들이 모두 같고, 0이 포함되어있는 행/열보다 크면 유효하다고 판단한다.

대각선 2개도 고려해야 한다.



구현 

printf() 함수로 64비트 정수를 출력할 때 서식문자로 %lld 대신 %I64d를 써서 제출.



코드

https://github.com/tibyte/algorithm-problems/blob/master/codeforces/711b.cpp




격자 위에 원을 그려야 하거나 원 모양의 범위를 적용할 때

다음과 같은 식을 사용할 수 있다.



d가 0보다 크면 원 외부, d가 0보다 작으면 원 내부로 판단하는 것이다.


그러나 원을 그릴 때는 범위 내의 모든 점에 대입해야 할 뿐만 아니라 

매번 곱셈 연산을 3번 사용하여야 한다.



midpoint algorithm을 사용하면 이를 효율적으로 해결할 수 있다.

(원의 반지름이 n일 때 O(n))



원리




[그림1]

이 알고리즘의 원리는 결정된 한 점이 있을 때

한 칸 옆인 에 대응되는 y 값이 인지 인지 판단하는 것이다.  (위 그림에서 까만색 점 2개)



[그림 1]과 같이 원에 포함되는 것으로 결정된 한 점

가 있을 때 가 원의 내부인지 외부인지 판별하는 식은 아래와 같이 나타낼 수 있다.



중간점이 원 내부에 포함될 경우(p<=0), [그림1]에서 p의 위쪽 점을 선택하고,

p점이 원 밖일 경우(p>0) p의 아래쪽 점을 선택하는 것이다.


같은 방법으로 을 다음과 같이 점화식으로 나타낼 수 있다.




이제 을 결정해야 하는데,

위에서 서술한 바와 같이 의 부호에 따라 선택되므로 다음과 같이 나타낸다.



이를 활용하여 의 식을 간단히 하면



코드를 좀더 간편하게 하기 위해 대신 를 활용하면

최종적으로 아래 식을 얻을 수 있다.




한편 p의 초기값 는 위에서 식에 x의 초기값 0과 y의 초기값 r을 대입하여

5/4 - r이라는 것을 알 수 있다.


그런데 p의 점화식을 보면 초기값 외에는 모두 정수의 덧셈/뺄셈 연산이므로 (2x는 x+x로 계산)

p0을 int형으로 하고 1-r로 두어도 무방하다.




위 과정을 x > y가 되기 전까지 반복한다.

[그림 2]




실제로 그려보면 아래 그림과 같은 8분원(octant)을 얻을 수 있다.


[그림 3]




그리고 아래와 같이 대칭인 8개 점을 동시에 그리면 전체 원이 그려진다.

(x, y)

(x, -y)

(-x, y)

(-x, -y)

(y, x)

(y, -x)

(-y, x)

(-y, -x)


[그림 4]




4방향으로 뚫려 있는 부분은 따로 채워준다. 


[그림 5]



8개 부분을 따로 표시해 보면 아래 그림과 같다.


[그림 6]







원 채우기



y값이 변할 때 해당 y좌표에 해당하는 부분을 모두 칠하면

가운데 정사각형 영역을 제외한 부분을 채울 수 있다.(하단 코드 참조)


[그림 7]



나머지 정사각형 부분은 쉽게 채울 수 있다.(하단 코드 참조)


[그림 8]


모두 단색으로 칠해보면 아래 그림과 같은 원이 나온다.


[그림 9]




콘솔창에서는 한계가 있어 Javascript를 사용하여 그린 큰 원.


[그림 10]






구현



[그림 9]를 그릴 때 작성한 C언어 코드이다.

gcc컴파일러로 컴파일 가능하다.


나머지 코드들은

https://github.com/tibyte/algorithms/tree/master/bresenham/midpoint_circle

에서 다운로드 가능.


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
#include <bits/stdc++.h>
 
const int SIZE = 28;
 
void drawCircle(int arr[SIZE][SIZE], int r, int x, int y);
void display(int arr[SIZE][SIZE]);
 
int main(void)
{    
    int arr[SIZE][SIZE] = {0,};
    
    drawCircle(arr, 11, 11, 13);
    display(arr);
    
    return 0; 
}
 
 
void drawCircle(int arr[SIZE][SIZE], int r, int cx, int cy)
{
    int x, y;
    int p;
    
    x = 0;
    y = r;
    p = 1 - r;
    
    arr[y+cy][x+cx] = 1;
    arr[-y+cy][x+cx] = 1;
    arr[x+cy][y+cx] = 1;
    arr[x+cy][-y+cx] = 1;
 
    x = 1;
    while(x < y) {
        
        if(p < 0) {
            p += x+x + 1;
        }
        else {
            p += x+x + 1 -y-y;
            --y;
            for(int i=0; i<x; i++) {
                arr[y+cy][i+cx] = 1;
                arr[-y+cy][i+cx] = 1;
                arr[y+cy][-i+cx] = 1;
                arr[-y+cy][-i+cx] = 1;
                arr[i+cy][y+cx] = 1;
                arr[-i+cy][y+cx] = 1;
                arr[i+cy][-y+cx] = 1;
                arr[-i+cy][-y+cx] = 1;
            }
        }
        arr[y+cy][x+cx] = 1;
        arr[-y+cy][x+cx] = 1;
        arr[y+cy][-x+cx] = 1;
        arr[-y+cy][-x+cx] = 1;
        arr[x+cy][y+cx] = 1;
        arr[-x+cy][y+cx] = 1;
        arr[x+cy][-y+cx] = 1;
        arr[-x+cy][-y+cx] = 1;
        
        ++x; 
    }
 
    for(int i=cy-y+1; i<cy+y; i++) {
        for(int j=cx-y+1; j<cx+y; j++) {
            arr[i][j] = 1;
        }
    }
}
 
 
void display(int arr[SIZE][SIZE])
{    
    for(int i=0; i<SIZE; i++) {
        for(int j=0; j<SIZE; j++) {
            if(arr[i][j])
                printf("■");
            else
                printf("　");
        }
        printf("\n");
    }
}
cs







이전글(2013년) : http://tibyte.kr/160



단항 연산자(unary operator) 중에서 전위 증가(pre-increment)연산자와 후위 증가(post-increment) 연산자를 같은 줄에 사용한 결과를 3개의 컴파일러로 컴파일해 보았다.

이는 undefined behavior로, 컴파일러마다 다른 결과가 나올 수 있다.


사용한 컴파일러는 gcc 4.8.4와 clang 3.4, 그리고 Visual Studio 2015에 포함된 C 컴파일러(이하 VC)이다.



a의 초기값을 5로 했을 때 결과는 아래와 같다.

(원본 코드는 https://github.com/tibyte/asm/blob/master/unary.c 에서 볼 수 있다.)


위 그림에서처럼 컴파일러에 따라 결과가 다르게 나오는 것을 볼 수 있다.


소스코드가 어떻게 번역됐는지 확인하기 위해 오브젝트 파일을 생성하고 디스어셈블한다.






1. 디스어셈블된 코드 생성




 

$gcc -g -c unary.c -o unary-gcc.o

$objdump -dS -M intel unary-gcc.o > unary-gcc.txt

$clang -g -c unary.c -o unary-clang.o

$objdump -dS -M intel unary-clang.o > unary-clang.txt


gcc와 clang에서 -c옵션은 오브젝트 파일을 생성하는 것이고 -g는 디버깅 옵션으로, 소스코드를 포함시킬 수 있다.


objdump에서 -d옵션은 디스어셈블,  -S옵션은 소스코드 포함 옵션이다.

-M옵션은 인스트럭션을 AT&T 문법으로 출력할 것인지, Intel문법으로 출력할 것인지를 결정하는 옵션인데, 기본값은 AT&T로, 아래와 같은 형태로 출력된다.  





-M intel 옵션을 붙여 주면 아래와 같이 인텔 형식으로 된 결과를 얻을 수 있다.






Microsoft Visual Studio 2015에서 디스어셈블된 코드를 확인하려면

코드에 중단점을 건 후 F5로 디버그를 시작하고  Debug - Windows - Disassembly를 클릭하면 된다.







2. b = (a++) + a 분석


a의 초기값은 5이다.


GCC

mov    eax,DWORD PTR [a]

lea    edx,[rax+0x1]

mov    DWORD PTR [a],edx

mov    edx,DWORD PTR [a]

add    eax,edx

mov    DWORD PTR [b],eax

(1행) eax 레지스터에 5를 넣는다.

(2행) edx 레지스터에 6을 넣는다.

(3행) a에 6을 넣는다.

(4행) edx 레지스터에 6을 넣는다.

(5~6행) b에 5+6의 결과인 11을 넣는다.

b는 11이 된다.


lea 명령에서 rax 레지스터는 eax레지스터의 64비트 버전이므로

저장된 4바이트 값을 읽었을 때 같은 값이 나온다.



Clang
mov    ecx,DWORD PTR [a]
mov    edx,ecx
add    edx,0x1
mov    DWORD PTR [a],edx
add    ecx,DWORD PTR [a]
mov    DWORD PTR [b],ecx

(1행) ecx 레지스터에 5를 넣는다.

(2~3행) edx 레지스터에 6을 넣는다.

(4행) a에 6을 넣는다.

(5~6행) b에 5+6의 결과인 11을 넣는다.

b는 11이 된다.


VC
mov         eax,dword ptr [a] 
add         eax,dword ptr [a] 
mov         dword ptr [b],eax 
mov         ecx,dword ptr [a] 
add         ecx,1  
mov         dword ptr [a],ecx 
(1~2행) eax 레지스터에 6을 넣는다.
(3행) b에 6을 넣는다.
(4~6행) a에 5+1의 결과인 6을 넣는다.

b는 10이 된다.






3. b = (++a) + (a++) 분석


a의 초기값은 5이다.


GCC

add    DWORD PTR [a],0x1

mov    eax,DWORD PTR [a]

lea    edx,[rax+0x1]

mov    DWORD PTR [a],edx

mov    edx,DWORD PTR [a]

add    eax,edx

mov    DWORD PTR [b],eax

b에는 eax값과 edx값의 합이 들어가는데, 맨 처음에 a에 1을 더하여 6이 되고
그 다음 복사해 온 eax값에 1을 또 더하여 edx 레지스터에 복사하므로
b는 6+7의 결과인 13이 된다.


Clang
mov    ecx,DWORD PTR [a]
add    ecx,0x1
mov    DWORD PTR [a],ecx
mov    edx,DWORD PTR [a]
mov    esi,edx
add    esi,0x1
mov    DWORD PTR [a],esi
add    ecx,edx
mov    DWORD PTR [b],ecx
gcc와는 다르게 esi 레지스터를 사용하여 더한 값은 ecx+edx의 연산결과에 포함되지 않으므로
b의 값은 6+6의 결과인 12가 된다.



VC
 mov         eax,dword ptr [a] 
 add         eax,1  
 mov         dword ptr [a],eax 
 mov         ecx,dword ptr [a] 
 add         ecx,dword ptr [a] 
 mov         dword ptr [b],ecx 
 mov         edx,dword ptr [a] 
 add         edx,1  
 mov         dword ptr [a],edx 
clang 결과와 비슷하게 a에 대한 증가 연산 중 하나가 b값이 결정된 후에 계산되므로
b는 6+6 = 12가 된다.




4. 결론



증감연산자를 한 줄 내에서 여러 개 사용하면 연산의 실행순서가 불분명하여

값이 어떻게 변할지 예측하기 어렵고 컴파일러마다 다른 결과가 나오기도 한다.

따라서 이러한 코드를 작성하지 말아야 할 것이다..


Clang 컴파일러에서는 이런 구문을 컴파일할 경우 'multiple unsequenced modifications' 라는 warning을 띄워 준다.





참고 : undefined behavior




2016년 8월 2일에 윈도우10 1주년 업데이트(Windows 10 anniversary update)를 해 보았다. 



'업데이트 및 복구' 메뉴에서 '1607의 기능 업데이트'가 떴다.







업데이트를 다운로드 받는다. 약 7분 정도가 걸렸다.








컴퓨터를 재시작하면 업데이트 구성이 시작된다. 약 4분 정도가 걸렸다.









계속 놔두면 업데이트 작업이 진행된다. 약 20분 정도가 걸렸다.











앱 화면 모드를 '밝게'와 '어둡게' 중에서 선택할 수 있는 기능이 생겼다.








이번에 추가된 bash shell을 사용해 보기 위해서는 개발자 모드를 활성화해야 한다.








개발자 모드를 활성화하고 Windows 기능 켜기/끄기에 들어가면

'Linux용 Windows 하위 시스템(WSL : Windows Subsystem for Linux)'이 있는 것을 확인할 수 있다.

이번 1주년 업데이트에서는 정식 버전일 줄 알았는데 Insider Preview때와 마찬가지로 베타 상태이다.







WSL설치를 끝내면 System32 밑에 bash.exe가 생기고 실행하면 우분투가 설치된다.







사용자 이름과 암호를 설정한다.








루트 디렉토리의 파일들을 확인할 수 있다.








VIM을 실행한 모습. 아직 베타 버전이라서 그런지 한글이 깨진다..








우분투 등의 데비안 계열 리눅스와 같이 패키지 관리자인 apt를 사용해서 프로그램을 설치할 수 있다.







uname 명령어를 사용해 정보를 확인해 보았다.







리눅스용으로 작성한 C언어 소켓 통신 프로그램을 컴파일하고 실행해 보았다.








업데이트 완료 후 Windows.old 폴더가 생기고 18.6GB나 잡아먹고 있는데 디스크 정리로 들어가 지우면 된다.






html5 canvas를 사용할 때 자바스크립트(javascript)로 여러 줄 텍스트(multiline text)를 표시할 방법이 없어서 함수를 만들어보았다.


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
var canvas = document.getElementById("canvas");
var ctx = canvas.getContext("2d");
 
ctx.font="15px Consolas";
drawTextBox(ctx, "다람쥐 헌 쳇바퀴에 타고파\n다람쥐 헌 쳇바퀴에 타고파", 100, 100, 170, 1.2)
 
function drawTextBox(ctx, text, x, y, fieldWidth, spacing) {
  var line = "";
  var fontSize = parseFloat(ctx.font);
  var currentY = y;
  ctx.textBaseline = "top";
  for(var i=0; i<text.length; i++) {
    var tempLine = line + text[i];
    var tempWidth = ctx.measureText(tempLine).width;
 
    if (tempWidth < fieldWidth && text[i] != '\n') {
      line = tempLine;
    }
    else {
      ctx.fillText(line, x, currentY);
      if(text[i] != '\n') line = text[i];
      else line = "";
      currentY += fontSize*spacing;
    }
  }
  ctx.fillText(line, x, currentY);
  ctx.rect(x, y, fieldWidth, currentY-y+fontSize*spacing);
  ctx.stroke();
}
cs





fillText()가 한 줄 짜리 텍스트만 출력할 수 있으므로 이를 여러 번 써서 멀티라인 텍스트필드처럼 보이도록 만드는 것이다.


코드의 동작 방식은 아래와 같다.

1) 임시변수(tempLine)에 쓸 문자열을 한개씩 더한다.

2) 더하면서 캔버스 컨텍스트의 measureText()를 이용하여 너비를 재고, 이것이 지정된 텍스트필드 너비를 넘었을 경우 한 줄을 fillText()로 화면에 그린다.

3) 매개변수로 입력받은 행간격 비율(spacing)만큼 아래로 간격을 띄워서 1)부터 반복한다.


1)에서 개행문자('\n')을 만났을 경우에도 줄바꿈을 한다.




전체 소스코드는 아래 링크에 업로드하였다.

https://github.com/tibyte/algorithms/tree/master/html5canvas-textfield





실행결과는 아래와 같다.







프리프로세서인 #include에 대한 간단한 실험을 해 보았다.


코드 중간에서 소스코드가 있는 txt파일을 로드해도 전처리 과정에서 include가 처리되기 때문에 정상적으로 컴파일된다.


main.c


#include <stdio.h>

int main(void)
{
#include "source.txt"   //'hello world!'가 출력된다.
	return 0;
}

 



source.txt


printf("hello world!\n");

 



https://github.com/tibyte/practice/tree/master/C/include



01.

github 저장소에서 임의의 gh-pages브랜치로 페이지를 만들어서 도메인을 연결할 수 있다.

그런데 루트도메인이 다른 사이트를 가리키고 있는 상태에서 서브도메인만 github 저장소의 페이지에 연결하고 싶은데 검색이 잘 되지 않아서 이 포스트를 작성하게 되었다.






02.

1. 먼저 임의의 github 저장소의 브랜치를 만든다. 브랜치 이름은 gh-pages로 해야 한다.


2. gh-pahes 브랜치에 이름이 CNAME인 파일을 만들고 그 안에 연결할 서브도메인을 적는다. 현재 github은 저장소 당 한 개의 도메인 연결을 지원하고 있다. ex) sub.yourdomain.com


3. 보유하고 있는 도메인의 DNS레코드 설정으로 들어가서 A 레코드에 github에서 고지한 IP주소를 적는다. 이 글 작성시점에서는 192.30.252.153이지만 나중에 바뀔수도 있다. 서브도메인명은 중복되지 않게 아무거나 적는다. 여기서는 테스트를 위해 test로 적어보았다.


4. CNAME레코드의 서브도메인명은 2번에서 적은 서브도메인(sub)을, URL주소에는 3번에서 정한 이름(test.yourdomain.com)을 적는다.


5. 저장하고 DNS변경내역 전파시간만큼 기다리면 루트도메인에 관계없이 해당 서브도메인으로 저장소 페이지에 접근할 수 있다. 이 때, gh-pages 브랜치에 index.html파일이 있어야 한다.






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)의 달팽이배열 값을 바로 구할 수 있다.












이 글을 작성했을 때보다 더 나중에 나온

안드로이드 스튜디오 2.2.2로 빌드하는 방법을 새로 작성하였습니다.

http://tibyte.kr/272








개발환경

Windows 10 64bit

Android Studio 1.5.1

jdk 1.8.0_71


target sdk version : 23

min sdk version : 15


기본 설정


- JDK 설치

- JDK 환경변수 (PATH)설정

- 안드로이드 스튜디오 설치

- NDK 다운로드


안드로이드 스튜디오에서 새 프로젝트를 만든다. 

이 포스트에서는 프로젝트 이름을 ndktest로 정한다.


프로젝트 창에서는 Project Files를 선택해야 디렉터리 경로를 보기 쉽다.





File - Project Structure - Android NDK location 에서 다운받은 NDK 경로를 지정한다.

안드로이드 스튜디오를 통해 설치했다면 자동지정된다.






java 어플리케이션 만들기


안드로이드에서 빈 액티비티로 프로젝트를 만들면 TextView하나가 나와있는데,

C/C++ 네이티브 코드에서 보낸 메시지를 여기에 띄워 본다.


프로젝트 디렉터리를 기준으로

app/src/main/res/layout/content_main.xml 

파일에 있는 TextView에게 id를 붙여준다.


    android:id="@+id/textView" 



MainActivity.java 파일에 네이티브 라이브러리를 로드하는 구분과 메서드 선언을 적는다.


  static {

       System.loadLibrary("ndktest");

   }

   public native String getStringFromNative();



onCreate 메서드 내에서는 위에서 선언한 함수를 호출하여 텍스트뷰에 쓴다.


 TextView view = (TextView)findViewById(R.id.textView);

 view.setText(getStringFromNative());



Build - Make Project로 빌드한다.




javah로 JNI용 C++ 헤더파일 제작


이 작업을 하기 전에 먼저 환경변수에 ANDROID_HOME이라는 값을 안드로이드 SDK 경로로 지정해 두면 편하다.



Windows 환경에서 안드로이드 스튜디오를 통해 안드로이드 SDK를 설치했을 때 기본 경로는 C:\Users\유저이름\AppData\Local\Android\sdk 이다.


프로젝트 디렉터리를 기준으로

app/src/main

으로 이동하여 커맨드창을 열고 다음과 같이 javah를 실행한다. (Windows 기준)

도메인 경로와 프로젝트 이름(여기서는 ndktest)는 프로젝트에 맞게 설정.


$ javah -d jni -classpath %ANDROID_HOME%/platforms/android-23/android.jar;%ANDROID_HOME%/extras/android/support/v7/appcompat/libs/android-support-v7-appcompat.jar;%ANDROID_HOME%/extras/android/support/v4/android-support-v4.jar;../../build/intermediates/classes/debug 도메인.경로.ndktest.MainActivity


만약 ANDROID_HOME 경로의 extras/android 디렉터리에 support가 없다면

Tools - Android - SDK Manager - Appearance - System Settings - Android SDK - SDK Tools 로 들어가

Android Support Library 를 설치한다.


성공적으로 실행되었다면

app/src/main/jni 에 헤더파일(.h)이 생성된다.




C++ 네이티브 코드 작성


간단한 C++ 코드를 작성한다.

여기서 주의할 점은 위에서 생성한 헤더파일을 로드해야하고, 함수 이름도

Java_도메인_경로_프로젝트이름_Java클래스명_Java메서드명 형식으로 되어야 한다는 것이다.


JNIEXPORT jstring JNICALL Java_kr_tibyte_ndktest_MainActivity_getStringFromNative(JNIEnv *env, jobject obj)


아래 코드에 있는 도메인 (kr_tibyte)는 프로젝트에 맞게 고친다.


#include "kr_tibyte_ndktest_MainActivity.h"

#include <string>

#include <sstream>


using namespace std;


JNIEXPORT jstring JNICALL Java_kr_tibyte_ndktest_MainActivity_getStringFromNative(JNIEnv *env, jobject obj) {


    stringstream ss;

    for(int i=1; i<=9; i++) {

        for (int j=1; j<=9; j++) {

            int n = i*j;

            ss << " ";

            if(n < 10) ss << "0";

            ss << n;

        }

        ss << endl;

    }


    string str = ss.str();

    return env->NewStringUTF(str.c_str());

}






makefile(*.mk) 설정


app/src/main/jni 안에 Android.mk를 만든다.

LOCAL_PATH := $(call my-dir)


include $(CLEAR_VARS)


LOCAL_MODULE    := ndktest

LOCAL_SRC_FILES := main.cpp

LOCAL_LDLIBS := -llog


include $(BUILD_SHARED_LIBRARY) 


LOCAL_MODULE은 생성될 네이티브 모듈의 이름,

LOCAL_SRC_FILES는 모듈을 만드는 데 사용될 소스파일들의 목록이다.



app/src/main/jni 안에 Application.mk를 만든다.


APP_ABI := armeabi

APP_STL := gnustl_static


여기서는 컴파일을 위한 옵션 플래그들을 지정할 수 있다.

APP_STL을 지정하여 C++에서 STL 요소들을 사용할 수 있다.


APP_ABI는 ABI(Application Binary Interface)를 지정할 수 있는데 armeabi, armeabi-v7a, mips, x86등이 있으니 필요에 따라 설정한다.






gradle 설정

app/build.gradle을 수정한다.


apply plugin: 'com.android.application'


android {

    compileSdkVersion 23

    buildToolsVersion "23.0.2"


    defaultConfig {

        applicationId "kr.tibyte.ndktest"

        minSdkVersion 15

        targetSdkVersion 23

        versionCode 1

        versionName "1.0"

    }

    buildTypes {

        release {

            minifyEnabled false

            proguardFiles getDefaultProguardFile('proguard-android.txt'), 'proguard-rules.pro'

        }

        debug {

            jniDebuggable true

        }

    }


    sourceSets.main {

        //네이티브 라이브러리 경로

        jniLibs.srcDir 'src/main/libs'

       //JNI소스 경로

        jni.srcDirs = []

    }


   //안드로이드 스튜디오에서 Java 소스를 빌드할 때 buildNative task를 실행시킴

    tasks.withType(JavaCompile) {

        compileTask -> compileTask.dependsOn buildNative

    }


   //네이티브 소스 빌드

    task buildNative(type: Exec, description: 'Compile JNI source via NDK') {

        def ndkDir = android.ndkDirectory

        commandLine "$ndkDir/ndk-build.cmd", 'NDK_DEBUG=1', '-C', file('src/main').absolutePath

    }


    //네이티브 라이브러리 삭제

    task cleanNative(type: Exec, description: 'Clean JNI object files') {

        def ndkDir = android.ndkDirectory

        commandLine "$ndkDir/ndk-build.cmd", '-C', file('src/main').absolutePath, 'clean'

    }

    

    clean.dependsOn 'cleanNative'


}

dependencies {

    compile 'com.android.support:appcompat-v7:23.1.1'

    compile 'com.android.support:design:23.1.1'

}





결과


이제 애플리케이션을 빌드하고 기기에서 실행시키면

C++ 코드에서 처리한 결과가 MainActivity의 TextView로 표시된다.





코드 모음


https://github.com/tibyte/practice/tree/master/android/ndktest





참조


https://stackoverflow.com/questions/21096819/jni-and-gradle-in-android-studio

http://stackoverflow.com/questions/21999829/how-do-i-read-properties-defined-in-local-properties-in-build-gradle

http://stackoverflow.com/questions/21096819/jni-and-gradle-in-android-studio

http://i5on9i.blogspot.kr/2015/02/android-studio-ndk-hello-world.html

https://www.davidlab.net/ko/tech/using-the-android-ndk-with-android-studio-part1/





+ Recent posts

티스토리툴바