요즘 퇴근하고 그리고 주말에 파이썬 알고리즘 문제를 풀고 있어요.
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] |
이렇게 달팽이 배열을 완성했습니다!
푸느라고 몇 시간을 썼는지 모르겠지만 스스로 풀어서 정말 정말 뿌듯했습니당
오랜만에 보니 제가 푼 코드임에도 '내가 이렇게 풀었나'생각했었지만 그래도 좋아요
담에 또 복습하면서 글 올리도록 할게요!
모두 화이팅하시길 바라요:)
'Python' 카테고리의 다른 글
| [python] 간단한 예제로 알아보는 재귀함수 (0) | 2020.12.07 |
|---|---|
| [python] enumerate함수 (0) | 2020.12.04 |
| [python] 람다함수, filter() (0) | 2020.11.08 |
| [python] list comprehension(리스트 내포) (0) | 2020.11.07 |
| [python] for _ in range (0) | 2020.10.31 |
