[TIL] 정글 8일차 - 22/04/04

알고리즘

브루트 포스(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시간은 들어야겠다.

인프런 알고리즘 강의(파이썬) - https://www.inflearn.com/course/%ED%8C%8C%EC%9D%B4%EC%8D%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8