[SW 정글 17일차] 오늘 배운 점들

오늘은 지난 날들처럼 어떠한 주제를 잡고 정리하는 것이 아닌 알고리즘 문제를 풀면서 마주했던 오류를 해결하거나 코드를 바꿔보면서 알았던 내용을 정리하려고 한다.

 

 

1. TypeError: unhashable type: 'list'

위 에러는 list를 set으로 바꿀 때 나온 것이다.

정확히 말하면 list 안의 요소는 또 다른 list로 이루어져 있는 상태이다.

 

나는 list에 들어있는 원소들의 중복 제거를 하고 싶었고 for문을 돌리면서 조건문을 써도 되지만 set이라는 배열의 특징을 이용했다.

set의 특징은 중복 원소를 허용하지 않는다는 것과 순서가 없다는 것(인덱스 접근 불가)이다.

그래서 중복 값이 들어있는 list를 set으로 형변환을 해준다면 자동으로 중복 값을 제거할 수 있다.

 

그래서 set을 써서 list 안의 원소를 중복 제거하려고 했고 TypeError: unhashable type: 'list' 라는 오류를 마주했다.

지금은 오류를 해석하면 왜 오류가 났는지 알 수 있지만 처음에 오류를 마주했을 때는 어떠한 이유로 오류가 났는지 몰라서 구글링을 했다.

 

원인은 아래의 블로그 글을 통해 바로 찾을 수 있었다.

https://daewonyoon.tistory.com/363

[Python] 리스트를 딕셔너리의 키로 사용하려 하는데 에러가 발생한다. TypeError: unhashable type

간단하게 한 줄로 설명하면 set(집합) 내부 원소는 다양한 값을 함께 가질 수 있지만, mutable한 값은 가질수 없다는 것이다.

여기서 mutable한 값은 변경 가능한 객체로 리스트와 딕셔너리가 있다.

mutable에 속한 객체들은 call by reference 속성을 가지고 있기 때문에 값의 변경이 일어날떄 객체의 값이 변경되지 않는다.

코드를 보면 다음과 같다.

# List

arr = [1,2]
print(id(arr))
# 결과 : 2482063976768
arr.append(3)      
# arr = [1,2,3]
print(id(arr))
# 결과 : 2482063976768

# Dict

dict = {1:'a'}
print(id(dict))
# 결과 : 2482096740224
dict[2] = 'b'
# a = {1:'a', 2:'b'}
print(id(dict))
# 결과 : 2482096740224

 

mutable한 객체에 대한 설명만 보면 잘 이해가 안갈 수 있으므로 immutable한 객체는 어떠한지 코드를 봐보자.

immutable한 객체에는 일반적인 자료형(int, float, string 등)과 튜플이 있다.

# Int
a = 1            
print(id(a))
# 결과 : 2482056489264
a += 1
print(id(a))
# 결과 : 2482056489296

# String
string = 'a'
print(id(string))
# 결과 : 2482057318128
string += 'b'
print(id(string))
# 결과 : 2482096084784

 immutable한 객체들은 call by value 속성을 띄고있어 값이 변경되면 객체가 변하는것을 확인 할 수 있다.

 

이러한 이유로 set에는 list로 된 원소가 들어갈 수 없는 것이고 TypeError: unhashable type: 'list' 오류가 뜨는 것이다.

이 오류를 잡는 방법은 그냥 list 원소를 tuple형태로 변경해주면 된다.

 

 

 

 

2. 재귀함수에서 전역 변수없이 결과값 받기

이번 주차에서 분할 정복 문제를 풀면서 재귀함수를 사용할 일이 많았고 이 전 주차에서는 재귀함수 문제로 N-Queen 문제를 풀기도했다.

그러면서 전역변수를 사용하는 것은 성능 상 안좋고 가급적이면 전역변수를 사용하지말라는 말을 들었다.

(전역변수의 문제점을 자세히 알고싶다면 아래의 블로그 글을 읽어보면 좋다.)

https://kwangyulseo.com/2015/06/25/%EC%99%9C-%EB%B3%80%EC%88%98%EA%B0%80-%EB%82%98%EC%81%9C%EA%B0%80/

왜 변수가 나쁜가?

 

이번 주차 때 푼 분할 정복 문제 중에서 색종이 만들기 문제를 전역 변수를 사용해서 결과값을 받아오는 형식으로 코드를 짰는데 고쳐보려고 했으나 아직은 전역변수없이 결과값을 받아오는 것으로 바꾸지 못했다.

 

그래서 전역변수없이 결과값을 받아오는 것으로 코드를 바꾼 N-Queen 문제 풀이를 올려보려고 한다.

 

<전역변수를 사용한 풀이 코드>

import sys

def set(i, N):
    for j in range(N):
        if(not flag_a[j] and not flag_b[i + j] and not flag_c[i - j + (N - 1)]):
            pos[i] = j
            if i == (N - 1):
                global cnt
                cnt += 1

            else:
                flag_a[j] = flag_b[i + j] = flag_c[i - j + (N - 1)] = True
                set(i + 1, N)
                flag_a[j] = flag_b[i + j] = flag_c[i - j + (N - 1)] = False


N = int(sys.stdin.readline())
cnt = 0
pos = [0] * N
flag_a = [False] * N
flag_b = [False] * (N * 2 - 1)
flag_c = [False] * (N * 2 - 1)

set(0, N)
print(cnt)

 

<전역변수를 사용하지 않은 풀이 코드>

import sys

def set(i, N):
    cnt = 0
    for j in range(N):
        if(not flag_a[j] and not flag_b[i + j] and not flag_c[i - j + (N - 1)]):
            pos[i] = j
            if i == (N - 1):
                return 1

            else:
                flag_a[j] = flag_b[i + j] = flag_c[i - j + (N - 1)] = True
                cnt += set(i + 1, N)
                flag_a[j] = flag_b[i + j] = flag_c[i - j + (N - 1)] = False
    
    return cnt


N = int(sys.stdin.readline())
pos = [0] * N
flag_a = [False] * N
flag_b = [False] * (N * 2 - 1)
flag_c = [False] * (N * 2 - 1)

print(set(0, N))

 

 

---

[오늘의 나는 어땠을까?]

오늘로 정글 2주차 마지막 날이다.

1주차보다 난이도 높은 알고리즘 문제들을 마주했고 혼자서는 해결하기 힘든 문제들이 있었지만 동료들에게 설명을 들으며 최종적으로는 모든 문제 풀이를 이해할 수 있었다.

하지만 지금 본 문제들의 풀이를 이해한 것으로 끝나는 것이 아니라 나중에 이분탐색, 분할 정복로 풀어야할 문제들을 보았을 때 직접 구현할 실력이 됐으면 좋겠다.

 

내일은 오전 10시부터 오후 11시30분에 모의 알고리즘 테스트가 진행될 것이고 이분탐색, 분할 정복를 사용하여 푸는 문제가 나오면 반드시 맞추고 싶다.

그래야 내가 이번 주차 때 무언가를 얻었다는 것을 증명할 수 있고 성장했다고 느낄 수 있기 때문이다.

하지만 못풀었다고 해서 너무 좌절하거나 실망하지않고 더 내 것으로 만들기 위해 노력을 할 것이다.

 

---

<참고 자료>

https://wikidocs.net/16044

https://wikidocs.net/1015

https://dpdpwl.tistory.com/82