[python] 달팽이 배열 풀기
요즘 퇴근하고 그리고 주말에 파이썬 알고리즘 문제를 풀고 있어요.
12월부터 앱을 하나 만들어볼까 하는데 그전에 알고리즘 문제는 어떤 건지 알고싶어서 하고 있는데
재미가 있어서 계속 하다보니 11월 안에는 알고리즘 기초책 한권을 다 끝낼 것 같아요!ㅎㅎ
(실력이 상승했는지는 답 못함^^;)
알고리즘에도 여러 유형이 있지만 오늘은 복습할 겸 달팽이 배열에 대해 쓰도록 하겠습니다!
책 '코딩강화파이썬'(저자 이규호 (2019)) p.237,238 참고하여 풀었습니다.
1. 문제
사용자에게 n을 입력받아 다음과 같이 달팽이 모양으로 자연수를 출력하는 프로그램을 작성하라.
단, 재귀 호출은 사용하지 않는다.(힌트: 2차원 리스트 사용)
| n | 1 | 2 | 3 | 4 |
| 모양 | 1 | 1 2 4 3 |
1 2 3 8 9 4 7 6 5 |
1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7 |
2. 달팽이 배열?
위 문제에서처럼 n×n 배열에 부터 까지의 자연수를 달팽이 집 모양으로 채우는 배열을
달팽이 배열이라고 합니다. 아래 그림을 참고하시면 더 쉽게 이해하실 수 있을 거에요
3. 문제 풀이
1)
어떤 n을 입력하여도 달팽이배열이 될 수 있도록 하려면 공통된 규칙을 코드로 옮겨줘야 하는데요
처음에 규칙을 찾기가 쉽지가 않아요
저는 이 문제만 몇 시간 가량 혼자 끙끙대다가 풀었어요ㅋㅋㅋㅋ
머리 속으로 생각하시기 보다는 n=3, n=4, n=5 일때를 공책에 손으로 적어보시면서 찾는 걸 적극 추천합니다!
저는 아래 그림의 규칙을 이용해서 행렬좌표를 이용해 풀었습니다.
2) 행렬좌표를 이용한 규칙 찾기
n =4 일때를 예시로 각 회전마다
숫자가 적히는 행렬좌표 및 행렬의 변화, 적히는 숫자 수를 알아보겠습니다.
| n = 4 |
| 1 2 3 4 12 13 14 5 11 16 15 6 10 9 8 7 |
표1: snail[행][열] , s, k, value : 아래 코드에서 쓴 변수입니다.
아래 전체 코드에서도 쓰니까 유심히 봐주세요!!
| 회전 횟수 | 행렬좌표(snail[행][열]) | 행렬 변화 (s) | 적히는 숫자 수 (k) | 숫자(value) |
| 1회전 | (0,0) (0,1) (0,2) (0,3) | 열 +1 | 4개 | 1,2,3,4 |
| 2회전 | (1,3) (2,3) (3,3) | 행 +1 | 3개 | 5,6,7 |
| 3회전 | (3,2) (3,1) (3,2) | 열 -1 | 3개 | 8,9,10 |
| 4회전 | (2,0) (1,0) | 행 -1 | 2개 | 11,12 |
| 5회전 | (1,1) (1,2) | 열 +1 | 2개 | 13,14 |
| 6회전 | (2,2) | 행 +1 | 1개 | 15 |
| 7회전 | (2,1) | 열 -1 | 1개 | 16 |
2-1) 적히는 숫자 수
n 은 한번, 그 후로는 1씩 감소하여 2번씩 반복하다가 1이 2번 적힌 후 끝나는 걸 볼 수있습니다.
4 -> 3 -> 3-> 2-> 2-> 1-> 1
n -> n-1 -> n-1 -> n-2 -> n-2 -> n-3 -> n-3 ... ->1 -> 1
2-2) 행렬변화
행과 열이 교차하여 변하네요
1회전을 제외하면 행+1,열-1(2,3회전) / 행-1,열+1(4,5회전) / 행+1, 열-1(6,7회전) 이 반복됨을 볼 수 있습니다.
1회전을 추가하면 짝수가 아닌 홀수가 되므로 2회전부터 규칙으로 생각하였습니다.
그렇게 하면 2회전과 3회전을 쌍으로 묶어 규칙으로 볼 수 있으니까요!
3) 내가 푼 코드 전체!
def num_snail():
n = int(input("n: ")) # 사용자 입력으로 n 받음
snail = [[0 for j in range(n)] for i in range(n)] # j(열) 가 먼저 변함
value = 1 # 1 ~ n**2 까지 숫자
i,j = 0, n-1 # i 행, j 열
s = +1 # s : 행렬 변화 (+1/-1)
k = n-1 # 회전시 적히는 숫자 수(n,n-1,n-1,n-2,n-2...)
for f in range(n): # 1회전 숫자 채우기(좌->우 n번)
snail[0][f] = value
value += 1
while k > 0:
for _ in range(k):
i = i+s
snail[i][j] =value
value += 1
for _ in range(k):
j = j-s
snail[i][j] = value
value += 1
k -= 1
s = s*(-1)
print_snail(snail,n)
def print_snail(snail,n):
for i in range(n):
for j in range(n):
print("%4d" %snail[i][j], end ="")
print()
num_snail()
갑자기 코드가 등장해서 '아 갑자기 뭐야'이런 맘이 들면서 어려워 보이실 수도 있겠지만
전혀 어렵지 않으니 안심하세요!!
맨 처음부터 차근차근 자세히 뜯어볼 거니까 편하게 쭉 봐주세요:)
n = int(input("n: "))
snail = [[0 for j in range(n)] for i in range(n)] # 2차원 리스트 사용
만약 n =4라면?
n: 4
[[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]input()의 결과값은 str이므로 int()를 이용해 정수형으로 바꿔줍니다.
n =4일때를 생각해보면
snail = [ [0 for j in range(4)] for i in range(4)] 가 되겠죠
[0 for j in range(4)]
: range(4) 는 0,1,2,3이니 총 4번 반복을 하겠네요.
for문 앞에 0이 있으므로 0을 4번 채워달라가 되겠네요!
(다른 예: [ int(i) for i in lst_a ]는 lst_a의 모든 원소들을 int정수형으로 바꿔달라가 되겠죠?)
그럼 j가 4번 반복하여 [0,0,0,0] 이 만들어지면
[ [ j ] for i in range(4) ]
이 작동합니다. 이제 보니 i도 4번 반복을 하는데 앞에서 j로 만들어진 리스트([0,0,0,0])로 4번 반복을 시켜주는거네요
그래서 결과적으로
snail = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]] 이 됩니다.
이차원 리스트를 이용해 행렬을 만들었어요
이렇게 만들어진 행렬에 순서대로 숫자를 채워넣을 겁니다.
for f in range(n): # 1회전 숫자 채우기(좌->우 n번)
snail[0][f] = value
value += 1range(4) => 0,1,2,3 이렇게 반복이 되겠네요
처음에 value를 1로 지정해놓았던 것도 기억해주세요!
1~n**2까지 모든 수가 들어갈 수 있도록 value값은 반복 후 마다 +1을 해줍니다.
| f | 행렬좌표 | value |
| 0 | snail[0][0] | 1 |
| 1 | snail[0][1] | 2 |
| 2 | snail[0][2] | 3 |
| 3 | snail[0][3] | 4 |
앞에서 보신 것 같은 기분이 드시는가요?!
이 부분은 위에 표1 에서 정리해둔 1회전을 나타내는 코드였습니다ㅎㅎ
그래서 여기 아래부터는 2회전 후부터를 나타내줍니다.
while k > 0: # n=4일때 k=3,3,2,2,1,1 이므로 k가 0이상일때까지만 반복
for _ in range(k):
i = i+s # 행 + 행렬변화 변수(s)
snail[i][j] =value # 행렬좌표에 숫자 넣기
value += 1
for _ in range(k):
j = j-s # 열 + 행렬변화 변수(s)
snail[i][j] = value
value += 1
k -= 1
s = s*(-1)
while반복문에서 보시면 행렬변화변수(s)에 따라 행(i)이 변하는 반복문 1개, 열(j)이 변하는 반복문 1개가
세트로 되어있는걸 보실 수 있는데요
즉 2,3회전 / 4,5회전 / 6,7회전을 쌍으로 반복하여 문제를 풀 거에요
전체 코드를 들고오는 게 이해하기 좋을 것 같아 들고왔습니다.
def num_snail():
n = int(input("n: ")) # 사용자 입력으로 n 받음
snail = [[0 for j in range(n)] for i in range(n)] # j(열) 가 먼저 변함
value = 1 # 1 ~ n**2 까지 숫자
i,j = 0, n-1 # i 행, j 열
s = +1 # s : 행렬 변화 (+1/-1)
k = n-1 # 회전시 적히는 숫자 수(n,n-1,n-1,n-2,n-2...)
for f in range(n): # 1회전 숫자 채우기(좌->우 n번)
snail[0][f] = value
value += 1
while k > 0:
for _ in range(k):
i = i+s
snail[i][j] =value
value += 1
for _ in range(k):
j = j-s
snail[i][j] = value
value += 1
k -= 1
s = s*(-1)먼저 n = 4일때를 생각해봅시다.
|
value = 1 |
으로 변수가 초기 세팅됩니다.
그리고 for f in range(4)를 이용해 1회전을 채운 후에는 value = 5가 되어있을 겁니다.
while반복문은 k>0일때까지만 반복하므로
k =3 , k =2 , k =1 이렇게 3번 반복하게 되겠네요
1) while반복문 : k = 3 일때
1-1) 2회전: 첫번째 for문 ( i = i+s ) / for _ in range(k)
| 반복횟수 | s | i | j | value | 행렬좌표 |
| 1 | +1 | 1 | 3 | 5 | snail [1][3] |
| 2 | +1 | 2 | 3 | 6 | snail [2][3] |
| 3 | +1 | 3 | 3 | 7 | snail [3][3] |
1-2) 3회전: 두번째 for문 ( j= j-s ) / for _ in range(k)
| 반복횟수 | s | i | j | value | 행렬좌표 |
| 1 | +1 | 3 | 2 | 8 | snail [3][2] |
| 2 | +1 | 3 | 1 | 9 | snail [3][1] |
| 3 | +1 | 3 | 0 | 10 | snail [3][0] |
두 개의 for문을 다 돌고 나면
k -= 1
s = s*(-1)을 만나서 k = 2 , s = -1이 됩니다.
그 후 다시 while문으로 돌아가는데 k > 0 이므로 4,5회전(for문)을 하게 됩니다.
1) while반복문 : k = 2 일때
1-1) 4회전: 첫번째 for문 ( i = i+s ) / for _ in range(k)
| 반복횟수 | s | i | j | value | 행렬좌표 |
| 1 | -1 | 2 | 0 | 11 | snail [2][0] |
| 2 | -1 | 1 | 0 | 12 | snail [1][0] |
1-2) 5회전: 두번째 for문 ( j= j-s ) / for _ in range(k)
| 반복횟수 | s | i | j | value | 행렬좌표 |
| 1 | -1 | 1 | 1 | 13 | snail [1][1] |
| 2 | -1 | 1 | 2 | 14 | snail [1][2] |
1) while반복문 : k = 1 일때
1-1) 4회전: 첫번째 for문 ( i = i+s ) / for _ in range(k)
| 반복횟수 | s | i | j | value | 행렬좌표 |
| 1 | 1 | 2 | 2 | 15 | snail [2][0] |
1-2) 5회전: 두번째 for문 ( j= j-s ) / for _ in range(k)
| 반복횟수 | s | i | j | value | 행렬좌표 |
| 1 | 1 | 2 | 1 | 16 | snail [2][1] |
이렇게 달팽이 배열을 완성했습니다!
푸느라고 몇 시간을 썼는지 모르겠지만 스스로 풀어서 정말 정말 뿌듯했습니당
오랜만에 보니 제가 푼 코드임에도 '내가 이렇게 풀었나'생각했었지만 그래도 좋아요
담에 또 복습하면서 글 올리도록 할게요!
모두 화이팅하시길 바라요:)