티바이트

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

이와 같은 결과를 이차원배열을 쓰지 않고 구현하려면, 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