[백준 9184번] 깊은 복사,얕은 복사 개념

 

신나는 함수 실행(#9184)

• Problem

재귀 호출만 생각하면 신이 난다! 아닌가요? 다음과 같은 재귀함수 w(a, b, c)가 있다. if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns: 1 if a > 20 or b > 20 or c > 20, then w(a, b, c) returns: w(20, 20, 20) if a < b and b < c, then w(a, b, c) returns: w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c) otherwise it returns: w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1) 위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15) a, b, c가 주어졌을 때, w(a, b, c)를 출력하는 프로그램을 작성하시오.

 

• Hint

깊은 복사 얕은 복사에 대해서 알아보자

 

• Solution

하드카피를 이용한 풀이 [ 정답 ]

def w(a, b, c):
    if a <= 0 or b <= 0 or c <= 0:
        return 1
    elif a > 20 or b > 20 or c > 20:
        return w(20, 20, 20)

    elif stg[a][b][c] != 0:
        return stg[a][b][c]

    elif a < b and b < c:
        stg[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
        return stg[a][b][c]
    else:
        stg[a][b][c] = w(a-1, b, c) + w(a-1, b-1, c) + \
            w(a-1, b, c-1) - w(a-1, b-1, c-1)
        return stg[a][b][c]


result = []
stg = [[[0]*(21) for _ in range(21)] for _ in range(21)]
i = 0

while i == 0:
    a, b, c = map(int, input().split())
    if a == -1 and b == -1 and c == -1:
        i = 1
    else:
        result.append(f'w({a}, {b}, {c}) = {w(a,b,c)}')
print(*result, sep='\n')

 

---

 

하드 카피를 하지 못하였을때의 문제점

stg = [[[None]*21]*21]*21
i = 0
while i == 0:
    a, b, c = map(int, input().split())
    if a == -1 and b == -1 and c == -1:
        i = 1
    print(f'w({a}, {b}, {c}) = {w(a,b,c)}')

위에 있는 하드카피로 성공하기 전에 실패했던 방법

단순하게 nested list 형식으로 21을 곱해주었다. 얕은 복사와 깊은 복사의 개념을 알지 못했고 혹시나 해서 리스트를 프린트 했는데

위와같은 결과값이 나와서 제대로 리스트에 추가가 되지 않고 있구나라는 것을 확인 할 수있다.

 

이유가 뭘까?

 

깊은 복사와 얕은 복사

 

얕은 복사는 객체의 주소를 참조한다.

 

[]*n 얕은 복사의 방식을 통해 각 리스트를 곱하는 것을 통해서 만든 21*21*21 사이즈의 행렬은

 

메모리 내에 21*21*21의 9261 칸의 공간이 생긴 것이 아니라 처음 []*21의 경우에는 각 자리수는 어쩔수 없이 할당 되기 때문에 21개의 칸(편하게 칸으로 표현 실제로는 각각 21가지의 None이 메모리 공간에 할당 된 것)이 형성된다.

 

이후의 []*21을 또 다시 [[]*21]*21 하는 경우에는 기존의 만들어진 21개의 칸을 가르키는 21개의 얕은 복사로 이루어진 Nested list가 아닌 메모리 주소인 것이다.

 

뭐,, 표현에 따라 Fake Nested List 라고도 부를 수 있으려나

 

 

깊은 복사는 새로운 객체를 만들어낸다.

 

stg = [[[0]*(21) for _ in range(21)] for _ in range(21)] 의 깊은 복사 방식을 통해 []*21로 만든 각 메모리를 반복문을 통하여 만든 21*21*21 사이즈의 행렬은

 

반복문을 통해 21*21*21 공간에 하드 카피 된 9261 칸의 공간이 생긴 것이다. 이해가 좀 되는가? (사실 나도 이해안됐다가 이해되서 글 쓰는거임) 얕은 복사에서의 첫 21개의 칸을 가르키는 객체가 생성된 것이 아니라 반복문을 통하여 첫 21개의 칸에 할당된 None 값이 총 21번을 도장 찍듯이 땅땅 박혔다고 생각하자

 

그럼 얕은 복사와는 다르게 깊은 복사는 각각에 메모리가 따로 할당되어 있기 때문에 코드가 작동되면 설계했던 위치에 성공적으로 할당된다.