[백준 10819번] 리스트 복사와 메모리에 대한 고민. 재귀 함수를 활용하여 문제를 풀어보자./22.11.01

이 문서는 전문적이지 않습니다.

 

입력 : 첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

출력 : 첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.

 

해당 문제는 배열에 들어있는 요소를 활용하여 수많은 경우의 수를 탐색해야한다.

 

 

#1

 

세상에 한번에 맞았습니다가 뜨는거구나..

사실 단번에 '맞았습니다!!' 라는 텍스트가 뜨니까 조금 어색했다. 앞으로는 자주 보자.

 

import sys

n = int(sys.stdin.readline())
listI =  list(map(int,sys.stdin.readline().rstrip().split(' ')))

#  차이를 절대값으로 리턴해주는 함수
def subT(a,b):
    return abs(a-b)

# 리스트를 넣었을 때 각각의 차이를 절대값으로 바꾼후 더한 수 리턴
def plusL(listA):
    ans = 0
    for i in range(len(listA)-1):
        ans += subT(listA[i],listA[i+1])
    return ans

def factorial(a):
    if a == 0:
        return 1
    return a * factorial(a-1)

listB = [0] * n
listAll = [0] * factorial(n)
listSum = [0] * factorial(n)
cnt=0

# 리스트를 섞는 함수
def shakeL(listA,listB, n):
    global cnt
    global listSum
    global listAll

    if n == 0 :
        listAll[cnt] = listB
        listSum[cnt] = plusL(listB)
        cnt += 1
        return
    else:
        listC = listA[:]
        for i in range(n):
            listC = listA[:]
            listB[n-1] = listC[i]
            del(listC[i])
            shakeL(listC,listB,n-1)
            listC.insert(i,listB[n-1])


shakeL(listI,listB, n)

print(max(listSum))

 

위 문제를 풀면서 습관화 하고자 한 방법론은 다음과 같다.

 

1. 문제를 해결하기 위한 함수을 간단하게 표현할 수 있으면 표현하자. subT(a,b), plusL(listA)

2. 함수를 다시 부르는 시점의 '전'과 '후'의 요소 값을 신경쓰자. listC[i] 값을 지운 후 함수를 호출한 뒤 다시 복구하자

 

 

사실 아직 재귀함수와 정렬에 대한 알고리즘이 머리속에서 쉽게 떠오르지 않는다.

그러나, 함수를 간단하게 표현하여 호출하니 조금씩 문제에 접근할 수 있었다.

물론 함수를 여러번 호출하게 되면 메모리를 많이 차지하게 될 수 있으니 조심하자.

 

 

위 문제를 풀면서 걱정했던 것은 메모리 초과였다. 이전 백준 메모리초과에 대한 영향이다.

리스트를 경우의 수 만큼 섞어주기 위해서 원본 데이터를 복사하여 독립적으로 '삭제', '변경', '복구' 를 해야한다.

이를 위해서 학습한 내용은 '얕은 복사'와 '깊은 복사'다.

 

 

단어만 보면 '얕은' 복사니까 데이터만 가져올 것 같고,

'깊은' 복사니까 주소 값과 연결될 것 같다고 느꼈다.

 

 

 

그러나 몇번의 print() 테스트로 알게된 것은 반대였다.

 

 

 

 

얕은 복사를 한 데이터를 수정할 경우 원본도 변경됐다.

반대로 깊은 복사를 한 데이터는 원본 데이터는 유지됐다.

 

왜 이런 현상이 발생했을까?

그 이유는 아래 표에서 확인할 수 있었다.

 

S.No.	Shallow Copy	Deep Copy
1.	In Shallow copy, a copy of the original object is stored and only the reference address is finally copied.	In Deep copy, the copy of the original object and the repetitive copies both are stored.
2.	Shallow copy is faster than Deep copy.	Deep copy is slower than Shallow copy.
3.	The changes made in the copied object also reflect the original object.	There is no reflection on the original object when the changes are made in the copied object.
4.	It stores references of the object in the main memory.	It stores copies of the object values.

출처 : https://byjus.com/gate/difference-between-shallow-and-deep-copy-of-a-class/

Difference between Shallow and Deep copy of a class

 

 

얕은 복사는 최종적으로 참조 주소만 복사한다.

 

깊은 복사는 최종적으로 원본 개체의 값을 새로운 메모리에 저장한다.

 

 

 

결국, 내가 원하는 행위는 깊은 복사에 더 가까우나, 새로운 메모리를 할당하는 것에 부담감을 느꼈다.

그래서 사용한 방법이 함수 내부에서 해당 리스트 값을 변경하여 변경된 리스트를 재귀 함수의 인자값으로 넣어준 뒤 다시 복구하는 알고리즘이었다.

 

listC = listA[:]

 

슬라이싱을 이용하여 얕은 복사를 했다. 하지만 지금 글을 정리하며 다시 리뷰해보니 다시 복구하기 때문에 listA 를 그대로 함수 내부에서 활용하면 됐을 것 같다는 아쉬움이 든다.

 

 

 

 

 

 

 

글을 마치며

 

 

지난 며칠 동안 코딩 테스트를 하며 만난 가장 큰 벽들은 '재귀 함수' 와 '정렬' 이었다.

이전의 나에게 재귀 함수에 대한 이해는 while 문과 같았고, 정렬에 대한 지식은 sort() 와 sorted() 가 전부였기 때문이다.

 

위 문제를 풀면서 재귀함수를 이렇게.. 쓰면 되지 않을까? 하며 고민한 것이 개인적으로 가장 뿌듯하다. 그러나, 리뷰하는 지금 시점에서 바로 보이는 내 코드의 문제점들은 앞으로 많이 고쳐나가야할 점이다.

 

TIL 을 적지않으면 정글의 하루는 끝나지 않는다.

 

아마 오늘 늦은 시간이지만, 적지않았다면 이러한 내 리뷰를 다시 볼 일 없었을 것이다.

내일은 더 일찍 적도록 노력하자.

 

 

 

긴 글 읽어주셔서 감사드립니다.

22.11.01