알고리즘
브루트 포스(brute force)
brute: 무식한, force: 힘. 무식한 힘으로 해석할 수 있다. 완전탐색 알고리즘으로 가능한 모든 경우의 수를 탐색하고 요구조건에 충족되는 결과를 가져온다.
모든 경우의 수를 탐색하기 때문에 예외 없이 100%의 확률로 정답을 출력할 수 있다.
자료구조
배열 vs 리스트
https://velog.io/@metamong/%EB%B0%B0%EC%97%B4-vs-%EB%A6%AC%EC%8A%A4%ED%8A%B8
파이썬 문법
얕은 복사 .copy()
순열 생성에 참고한 동영상 - https://www.youtube.com/watch?v=qilJ2p_0BGg
순열을 직접 만들어보던 중, 임시로 생성한 list(여기서는 tmp)를 다른 list(여기서는 arr_list)에 append할 때 전역 변수로 선언된 tmp를 참조하기 때문에 2차원 list인 arr_list의 각 원소들(1차원 list)이 [0, 0, 0]으로 찍히고 있었다.
A = [1, 2, 12, 1]
N = len(A)
visited = [0] * N
tmp = [0] * N
arr_list = []
def permutation(level):
if level >= N:
arr_list.append(tmp)
return
for i in range(N):
if visited[i]:
continue
visited[i] = 1
tmp[level] = A[i]
permutation(level + 1)
tmp[level] = 0
visited[i] = 0
permutation(0)
print(arr_list)
arr_list에 tmp를 append하는 과정과 tmp[level]을 0으로 하는 곳이 원인이다. permutation 함수를 실행하면 함수 내에서 전역으로 선언된 tmp를 참조하게 된다. 이 tmp의 주소(혹은 id)가 345라고 한다면 arr_list에 tmp를 append했을 때 다음과 같은 형식이 된다.
arr_list = [tmp(id = 345), tmp(id = 345), tmp(id = 345), ...]이렇게 하면 tmp[level]도 전역으로 선언된 tmp, 즉 id가 345인 tmp를 참조하기 때문에 tmp[level] = 0을 하게 되면 arr_list안의 tmp들도 모두 [0, 0, 0]이 되어버린다. 따라서 arr_list에는 주소가 다른 tmp를 넣어줘야 한다.
python에서는 다행히 이를 .copy()를 써서 구현할 수 있다. 재귀의 종료조건인 if문으로 들어갔을 때 변경되어져 있는 tmp를 copy, 즉 얕은 복사를 해서 arr_list에 append 해주면 주소가 각기 다른 tmp가 들어가게 된다. .copy()는 주소는 다르지만 값은 같은 것을 복사해준다.
하나의 재귀가 끝날 때마다 if문으로 들어가 arr_list.append(tmp.copy())를 하게 되면 변경되어진 tmp를 copy해서 각기 다른 주소의 tmp를 arr_list에 append할 수 있다. arr_list는 다음과 같은 형식일 것이다.
arr_list = [tmp(id = 453), tmp(id = 192), tmp(id = 288), ...]따라서 tmp[level] = 0을 해도 arr_list안의 tmp들과는 주소가 다르기 때문에 arr_list안의 tmp라는 리스트 안의 원소값들은 변하지 않는다.
A = [1, 2, 12, 1]
N = len(A)
visited = [0] * N
tmp = [0] * N
arr_list = []
def permutation(level):
if level >= N:
arr_list.append(tmp.copy())
return
for i in range(N):
if visited[i]:
continue
visited[i] = 1
tmp[level] = A[i]
permutation(level + 1)
tmp[level] = 0
visited[i] = 0
permutation(0)
print(arr_list)
하루를 마치고
알고리즘을 주먹구구식으로 알아가고 있는 것은 아닐까 걱정된다. 기본적인 것부터 차근차근 알아가는 시간도 따로 필요할 듯 하다. 꼭 시간을 내서 매일 인프런 강의를 30분 ~ 1시간은 들어야겠다.
