itertools의 combinations를 쓰면 편리하게 조합을 구할 수 있지만, 라이브러리를 쓰면 안되는 환경이라서 실제로 조합을 구현했다.
def dfs(comb, depth):
if len(comb) == m:
print(comb)
result.append(comb)
return
if depth == len(check):
return
comb.append(check[depth])
dfs(comb, depth + 1)
comb.pop()
dfs(comb, depth + 1)
result = []
dfs([], 0)
print(result, id(result))[ nCm 을 구현하려고 했음 ]
모든 조합의 경우의 수를 구하기 위해서 구한 배열의 길이가 m과 같으면 총 집합된 배열에 넣어주려고 다음과 같이 구현했다.
print(comb)를 하면 값이 잘 나오는데 result.append(comb)를 하고 마지막에 result를 출력하면 빈 배열만이 나왔다.
comb.pop()을 하는 부분에서 result에 담긴 값들도 pop() 되었는데 이해가 안갔다. comb와 result는 다른 것인데? result는 단순히 comb 의 값을 넣어줄 뿐인뎅???
위의 그림에서 comb가 바뀌면 result 또한 바뀌는데 위와 아래 그림 모두 주소값은 동일하다.
결국 result에 append 되는것은 값이 아니라 주소값이였던 것..!
def dfs(comb, depth):
if len(comb) == m:
# print(comb)
result.append([*comb])
return
if depth == len(check):
return
comb.append(check[depth])
dfs(comb, depth + 1)
comb.pop()
dfs(comb, depth + 1)
result = []
dfs([], 0)
print(result, id(result))그래서 result에 값을 넣어주도록 바꾸면 잘 들어가는 것을 확인할 수 있다!
후에 더 검색해보니 python은 passed by assignment라고 한다.
파이썬의 자료형엔 크게 immutable(불변) 과 mutable(가변) 이 있는데,
불변 타입의 객체를 넘기면 call by value 가 되고 가변 타입의 객체를 넘기면 call by reference 가 된다고 한다.
int, str 같은 타입이 불변이고 list, dictionary 같은 타입이 mutable 이다.
즉 할당 되는 것에 따라 전달 방식이 달라지는 것이다.
[*comb] 해줌으로써 가변타입을 불변타입으로 바꾸었기 때문에 값이 전달되는 것이다.
10.9 update
result.append(list(comb))로 해도 값이 나오는데 그 이유는 list는 안에 요소가 있으면 복사본이 생성되어 리턴되기 때문이다.
이로써 조합을 직접 구현할 수 있는 멋진 어른이 된 나 ,제법 멋져요
디버깅 신기하고 잼난당 끝!
