• 목록
  • 아래로
  • 위로



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


위 그림처럼 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%) 1875900/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 367
공지 [중요] 호스팅 만료와 관련하여 일부 수칙이 변경됩니다. 4 마스터 23.01.14.02:23 4056
공지 [필독] 질문하는 방법 17 마스터 18.02.23.03:09 4464
922 계속 사용중이던 네트워크 공유 폴더가 갑자기 액세스 불가라고 뜹니다. 6 image 장윤서 18.06.07.16:55 34331
921 팀뷰어 대체할 원격 제어 프로그램 추천 부탁드립니다 16 이니스프리 17.11.30.15:38 32325
920 엑셀 그래프의 축 간격 조절 문제입니다. 2 image 국내산라이츄 17.08.10.11:06 12483
919 아이폰/아이패드 충전기 발열 관련 질문 드립니다 9 image 이니스프리 19.05.02.22:52 11105
918 에러 523 해결법 4 입체그림 20.02.21.16:48 6688
917 PyQt 실행시 프리징 현상 관련하여 질문 드립니다! ㅠㅠ 3 이니스프리 19.07.06.03:37 6684
916 프린터가 지 맘대로 프린트를 하네요. 3 곰도리푸 18.04.04.18:20 6014
915 윈도우용 메일 클라이언트가 필요합니다. 9 네모 18.01.11.20:15 5867
914 크롬에서 특정 사이트 접속 문제 관련하여 질문 드립니다 9 이니스프리 17.03.27.18:03 5309
913 오라클 클라우드 프리티어 가입이 안 되네요 ㅠㅠ 20 이니스프리 20.06.26.21:31 4827
912 파이썬 에디터로 어떤 것이 좋나요? 14 NoYeah 20.01.08.21:08 4525
911 라떼판다와 라즈베리 파이 중 어느 쪽을 사는 게 나을까요? 9 제르엘 18.10.14.19:25 3827
910 나무 위키의 수익구조는 무엇일까요? 2 NoYeah 18.03.18.15:56 3808
909 파티션 복구 프로그램 TestDisk 잘 아시는 분 계시나요? 29 이니스프리 17.11.10.14:53 3745
908 IE11에서 이미지가 깨지는 현상을 해결할 수 있을까요? 2 이니스프리 19.08.02.00:01 3702
907 파일질라로 연결하니까 보안되지 않은 서버입니다. TLS를 통한 FTP를 지원하지 않습니다. 이렇게떠요 해결방안좀 1 마카오 16.09.11.00:57 3654
906 자바스크립트 FormData와 관련된 메서드의 IE 호환성과 관련하여 질문 드립니다 ^^ 6 image 이니스프리 19.08.05.14:22 3426
905 선택약정 안 되는 중고폰의 경우에는 어떤 단점이 있는 것인가요?? 6 이니스프리 20.01.21.14:30 3099
904 집에서 시놀로지 NAS로 워드프레스나 미디어위키 돌리면 느릴까요? 10 이니스프리 17.01.16.20:56 2979
903 [Requests] multipart/form-data의 전송에 대해 질문 드립니다 ^^ 4 이니스프리 19.12.18.22:00 2901