• 목록
  • 아래로
  • 위로



코딩 문제 중에서 소용돌이(?)라는게 있던데요.


위 그림처럼 n*n 사이즈의 2차원 리스트에 시계방향으로 1부터 n^2까지 자연수를 순서대로 배열하는 문제입니다.


며칠동안 고민을 했는데 잘 해결되지 않아서 COS 시험을 앞두고 질문 드립니다 ㅠㅠ


구글링해보면 이 문제 때문에 다들 고생했다는 내용이 있네요 ㅜㅜ



우선 COS Pro 홈페이지의 모범답안의 풀이입니다.


정수 n을 받아서 n*n 사이즈의 소용돌이를 반환하는 함수입니다.


def in_range(i, j, n):
    return 0 <= i and i < n and 0 <= j and j < n

def solution(n):
    pane = [[0 for j in range(n)] for i in range(n)]
    dy = [0, 1, 0, -1]
    dx = [1, 0, -1, 0]
    ci, cj = 0, 0
    num = 1
    while in_range(ci, cj, n) and pane[ci][cj] == 0:
        for k in range(4):
            if not in_range(ci, cj, n) or pane[ci][cj] != 0:
                break
            while True:
                pane[ci][cj] = num
                num += 1
                ni = ci + dy[k]
                nj = cj + dx[k]
                if not in_range(ni, nj, n) or pane[ni][nj] != 0:
                    ci += dy[(k + 1) % 4]
                    cj += dx[(k + 1) % 4]
                    break
                ci = ni
                cj = nj
    return pane



위 코드와 비슷한 방식으로 제가 작성하려고 했던 코드인데 제대로 작동하지 않네요.


예컨대 3을 넣으면

[1,9,8]

[1,9,8]

[1,9,8]을 출력하네요.


def check(a, b, s, n): # 0 <= a, b < n이고, 이미 지나간 경로가 아님을 확인합니다.
    if 0<=a<n and 0<=b<n and s[a][b] == 0:
        return True
    else:
        return False

def sol(n):
    s=[[0]*n]*n
    da=[0, 1, 0, -1] # a는 y축입니다.
    db=[1, 0, -1, 0] # b는 x축입니다.
    a=b=0 # 현재 좌표를 의미합니다.
    cnt=1 # 1부터 n^2까지 카운트합니다.
    d=0 # da, db의 인덱스를 가리키는 변수입니다.
    while cnt<=n**2:
        s[a][b]=cnt # 현재 카운트를 s에 대입합니다.
        ta=a+da[d]
        tb=b+db[d]
        if check(ta, tb, s, n): # 움직이는 방향이 문제없는지 체크합니다.
            a=ta
            b=tb
        else: # 문제가 있으면 방향을 변경합니다.
            d=(d+1)%4
            a+=da[d]
            b+=db[d]
        cnt+=1
    return s



(a, b) 좌표를 찍어보면 틀리긴 하던데 제가 어디에서 잘못했는지 잘 모르겠네요 ㅠㅠ 


어떻게 풀어야 간명하게 해결되는지 여쭤봅니다.


스포어 회원분들께 항상 감사드립니다! ^-^



+) 한 방향으로 4 -> 3 -> 3 -> 2 -> 2 -> 1 -> 1 씩 이동하는 패턴을 활용하는 방법은 없을까요??


작성자
이니스프리 119 Lv. (0%) 1876250/115200000EXP

당분간 일신상의 사정으로 쪽지나 댓글로 답변을 드리기 어렵습니다. 죄송합니다.

 

CSVpuymXAAAVVpd.jpg

댓글 6

title: 황금 서버 (30일)humit
profile image

파이썬의 앝은 복사로 인해 생기는 버그라고 생각하시면 됩니다.


a=[[0]]*5
# 생각과 다르게 해당 부분은 True를 반환합니다.
# 즉 a[0]와 a[2]는 서로 같은 곳을 가리킨다고 생각하시면 됩니다.
print(id(a[0]) == id(a[2]))

a[0][0] = 2
# 그래서 a[0][0]를 바꾸었지만 a[2][0]가 동시에 바뀌게 됩니다.
# 나머지 원소들도 동일하게 2로 바뀝니다.
print(a[2][0])



그래서 해당 부분만 수정해주면 정상적으로 돌아갑니다.


def check(a, b, s, n): # 0 <= a, b < n이고, 이미 지나간 경로가 아님을 확인합니다.
    if 0<=a<n and 0<=b<n and s[a][b] == 0:
        return True
    else:
        return False
 
def sol(n):
    s=[[0]*n for _ in range(n)]
    da=[0, 1, 0, -1] # a는 y축입니다.
    db=[1, 0, -1, 0] # b는 x축입니다.
    a=b=0 # 현재 좌표를 의미합니다.
    cnt=1 # 1부터 n^2까지 카운트합니다.
    d=0 # da, db의 인덱스를 가리키는 변수입니다.
    while cnt<=n**2:
        s[a][b]=cnt # 현재 카운트를 s에 대입합니다.
        ta=a+da[d]
        tb=b+db[d]
        if check(ta, tb, s, n): # 움직이는 방향이 문제없는지 체크합니다.
            a=ta
            b=tb
        else: # 문제가 있으면 방향을 변경합니다.
            d=(d+1)%4
            a+=da[d]
            b+=db[d]
        cnt+=1
    return s



comment menu
2020.02.14. 23:48

신고

"humit님의 댓글"

이 댓글을 신고 하시겠습니까?

이니스프리 작성자 → humit
profile image

ㅎㄷㄷ 얕은 복사와 관련해서 이런 문제가 있었군요!

며칠동안 이 문제를 비롯하여 유사한 문제들이 안 풀려서 고민했는데 알려주셔서 감사합니다!!

그냥 리스트의 곱셈을 하는 것과 for문으로 돌리는게 다르다는 것을 humit 님 덕분에 처음으로 알았네요 ^^

 

구체적인 원리까지는 제가 아직 이해하지 못했지만

구글링해보니 대략 "2차원 이상 리스트부터는 내부는 깊은 복사가 안되고 얕은 복사만 된다"는 취지로 써있던데

그렇다면 1차원 리스트는 곱셈으로 해결해도 되고, 그 이상은 for문을 사용해야 된다고 일단 시험을 앞두고 이해하면 될까요?? ㅠㅠ

 

그럼 즐거운 주말 되시고, 일욜부터 추워진다는데 감기 조심하세요!! ^^

comment menu
2020.02.15. 00:03

신고

"이니스프리님의 댓글"

이 댓글을 신고 하시겠습니까?

title: 황금 서버 (30일)humit → 이니스프리
profile image

네 그런식으로 이해하시면 되겠습니다.

comment menu
2020.02.15. 00:09

신고

"humit님의 댓글"

이 댓글을 신고 하시겠습니까?

이니스프리 작성자 → humit
profile image

옙 감사합니다!

덕분에 시험 잘 준비할게요~

샘플 문제를 보니 COS Pro 1급은 저같은 아마추어가 도전할 시험은 아닌 것 같더군요 ㄷㄷ

그럼 굿밤 되세요! ^-^

comment menu
2020.02.15. 00:14

신고

"이니스프리님의 댓글"

이 댓글을 신고 하시겠습니까?

title: 황금 서버 (30일)humit
profile image

이니스프리님이 원하시는 방법과는 약간의 차이가 있긴 하지만 다음과 같이 한방향으로 연속적으로 할당하는 방법이 있습니다.



def sol(n):
    arr = [[None] * n for _ in range(n)]
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    x, y = 0, 0
    idx = 1
    side = n - 1
    while side > 0:
        for direction in range(4):
            for _ in range(side):
                arr[y][x] = idx
                x += dx[direction]
                y += dy[direction]
                idx += 1
        # 위의 for문을 시작한 위치 그대로 돌아오므로
        # x와 y 값을 1씩 증가시키면 다음 위치가 됩니다.
        x += 1
        y += 1
        side -= 2
    # 1칸만 남은 경우(변의 길이가 홀수인 경우) 바로 채워줍니다
    if side == 0:
        arr[y][x] = idx
    return arr


while문을 한 번 돌 때마다 바깥쪽에 있는 사각형에 숫자가 채워지는 방식으로 동작합니다. 그래서 side 값이 2씩 감소를 하는 것이고요.


뭔가 양파껍질을 벗겨 나가는 것과 유사한 방식으로 동작한다고 생각하시면 됩니다.

comment menu
2020.02.15. 00:17

신고

"humit님의 댓글"

이 댓글을 신고 하시겠습니까?

이니스프리 작성자 → humit
profile image

앗 이렇게 양파껍질 벗기듯이 순서대로 한 바퀴씩 처리하는 방법이 이동할 때 체크할 요소가 적어서 더욱 간단명료하네요! ^^

바쁘신데 정말 감사합니다!!

유사한 문제에서 이런 풀이방법을 적용해봐야겠네요~

그럼 안녕히 주무세요~ ^-^

comment menu
2020.02.15. 00:22

신고

"이니스프리님의 댓글"

이 댓글을 신고 하시겠습니까?

권한이 없습니다.
번호 제목 글쓴이 날짜 조회 수
공지 [작업 완료] 설 명절 맞이 서버 업데이트 안내 3 마스터 24.02.11.17:21 372
공지 [중요] 호스팅 만료와 관련하여 일부 수칙이 변경됩니다. 4 마스터 23.01.14.02:23 4058
공지 [필독] 질문하는 방법 17 마스터 18.02.23.03:09 4464
682 그누보드에서 과도한 POST 요청을 보내는 매크로를 이용한 DDoS에 대해 질문 드립니다. 6 image 이니스프리 20.02.20.13:17 656
681 윈도우 서버를 VPS에 구축하는 것에 대해 질문 드립니다. 23 이니스프리 20.02.17.21:06 632
680 다른 기기에서의 사이트 접속 불가 4 image 입체그림 20.02.17.19:03 597
[파이썬] 소용돌이(?) 코딩이 어렵네요 ㅠㅠ 6 image 이니스프리 20.02.14.22:06 2607
678 XE 상단바 내려가게 만들기 2 image 입체그림 20.02.14.10:17 202
677 스터디포어스에서 VisualEditor 사용이 가능하나요? 2 입체그림 20.02.12.10:42 244
676 컴퓨터 전문가님들 봐주세요~~원격프로그램에 대해서입니다 9 매매의신 20.02.12.09:05 386
675 인스타 프로필 사진 퍼오는거? 3 슬기 20.02.11.22:56 251
674 VPS에서 LEMP 스택을 제공하면 이걸 그대로 사용해도 괜찮을까요?? 4 이니스프리 20.02.07.14:29 221
673 이 파이썬 강좌를 수강하는 것은 어떨지 여쭤봅니다 ^^ 6 이니스프리 20.01.31.12:43 244
672 제대로 작동하는 GIF 무료 이미지 호스팅 사이트 추천 부탁드려요! 이니스프리 20.01.31.12:12 623
671 리눅스 오프라인 강좌의 수업 내용과 관련하여 질문 드립니다. 10 image 이니스프리 20.01.30.14:15 213
670 가개통을 구매하는데에 특별한 문제가 있나요? 3 Seia 20.01.26.18:59 213
669 ReactJS 도와주세요! 2 image Hanam09 20.01.25.22:01 176
668 선택약정 안 되는 중고폰의 경우에는 어떤 단점이 있는 것인가요?? 6 이니스프리 20.01.21.14:30 3099
667 맥북 프로 구매와 관련하여 여쭤봅니다 4 image 이니스프리 20.01.20.13:03 216
666 커뮤니티 사이트의 출첵 게시판의 활성화에 대한 좋은 아이디어가 있을까요?? 4 이니스프리 20.01.19.00:44 182
665 VPS에서의 Selenium 사용과 관련하여 질문 드립니다. 4 image 이니스프리 20.01.17.14:37 211
664 '링 피트 어드벤처'가 정말 운동이 되는가요?? 4 이니스프리 20.01.11.12:41 289
663 우분투만 사용하다가 페도라 13 / Centos 6.9 시험에 응시하려면 적응하기 어려울까요? ㅠㅠ 8 image 이니스프리 20.01.08.22:56 345