Python : Stack (2) [백트래킹, Backtracking]

이제부터 머리아플 구간이다. stack에서 심화된 알고리즘 기법인데, 시간 복잡도와 메모리를 크게 아낄 수 있는 방법이기 때문에 알고 있으면 많은 도움이 되는 기법이다. 음식을 할 줄 아는데, 맛있게 빠르게 만든다고 할까? 가보자

---

백트래킹 (Backtracking)

: 해를 찾는 도중에 '막히면' = '해가 아니라면' 탐색을 멈추고 되돌아가서 다시 해를 탐색하는 기법이다. 최적화(optimization) 문제와 결정 (decision) 문제를 해결하는데 도움이된다.

결정문제 : 문제의 조건을 만족하는 해가 존재하는지 여부를 확인하는 문제 (True / False)

• 미로찾기
• n-Queen
• Map coloring
• 부분 집합의 합 문제 등

어떤 노드의 유망성을 점검한 후에 유망(promising)하지 않다고 결정되면 그 노드의 부모로 되돌아가서(backtracking) 다음 자식 노드로 진행한다. 가지치기(pruning) : 유망하지 않는 노드가 포함되는 경로는 더 이상 고려하지 않는다.

 

백트래킹과 깊이 우선 탐색(DFS)의 차이

• 깊이 우선 탐색에 가지치기가 추가된 것이 백트래킹이라고 생각해도 좋다.
• 어떤 노드에서 출발하는 경로가 원하는 답과 이어질 것 같지 않다면 해당 경로를 따라가지 않음으로써 탐색 횟수를 줄임(가지치기)
• 깊이 우선 탐색은 '모든' 경로를 추적하는데 비해 백트래킹은 불필요한 경로는 조기 '차단'한다
• 깊이 우선 탐색에서 진행했던 부분집합 탐색을 생각해보자. N!가지 경우의 수를 가진다면 N이 커진다면 메모리 초과와 시간초과는 당연하다
• 하지만 백트래킹을 사용해 경우의 수를 줄일 수 있지만 최악의 경우(가장 마지막에 해답이 찾아진다면) 결국 지수함수 시간을 요하므로 처리 불가능이 될 수 있다.

 

근데 개인적인 경험으로는 여러 코드를 보면서 공부 했는데, 자신만의 코드 방식이 있는 것 같다. 친구들한테 물어봐도 인자로 넘기는 변수 개수도 다르고 변수명도 다르기 때문에 

---

부분집합

부분집합 : 어떤 집합의 공집합과 자기 자신을 포함한 모든 부분집합을 powerset이라고 하며 구하고자 하는 어떤 집합의 원소 개수가 n일 경우 전체 부분집합의 개수는 2**n개이다.

 

1. 앞서 일반적인 백트래킹 접근 방법을 이용한다
2. n개의 원소가 들어있는 집합의 2**n 개의 부분집합을 만들 때, True / False 값을 가지는 항목들로 구성된 n개의 배열을 만드는 법을 이용한다
3. 여기서 배열의 i번째 항목은 i번째의 원소가 부분집합의 값인지 아닌지를 나타내는 값이다.

간단하게 각 원소가 부분집합에 포함되는지를 확인하고 부분집합을 생성하는 방법을 알아보자.

아래는 모든 부분집합을 나타낸 예시이다.

bit = [0, 0, 0]

for i in range(2):

    bit[0] = i

    for j in range(2):

        bit[1] = j

        for k in range(2):

            bit[2] = k

            print(bit)

'''

[0, 0, 0]

[0, 0, 1]

[0, 1, 0]

[0, 1, 1]

[1, 0, 0]

[1, 0, 1]

[1, 1, 0]

[1, 1, 1]

'''

---

순열

순열 : 주어진 데이터들의 모든 가능한 순서를 나열한다. 순서가 다른 경우 모두 구별해서 나열하는데, 특별한 조건이 없다면 ABC는 "ABC", "ACB", "BAC", "BCA", "CAB", "CBA" 총 6개의 조합이 가능하다.

for i1 in range(1,4):

    for i2 in range(1,4):

        if i2 != i1:

            for i3 in range(1,4):

                if i3 != i1 and i3 != i2:

                    print(i1, i2, i3)

'''

1 2 3

1 3 2

2 1 3

2 3 1

3 1 2

3 2 1

'''

 

 

for문을 이용한 간단한 코드 작성으로는 위와 같다. 하지만 누가봐도 사용하면 안될 것 처럼 생겼다. 시간복잡도 보소!

총 2가지 방법이 있는데, 

교환을 사용한 예시

 

def permutation(nums, idx=0):

# 종료조건 : idx가 리스트의 마지막 인덱스에 도달했을 때

# 순열을 출력

    if idx == len(nums) - 1:

        print(nums)

        return

    for i in range(idx, len(nums)):

        # nums[idx]와 nums[i]의 위치를 바꾸어

        # 새로운 순열을 생성합니다. (결정)

        nums[idx], nums[i] = nums[i], nums[idx]

        # 다음 위치로 이동

        permutation(nums, idx + 1)

        # 원래의 순열로 복원합니다. (복구)

        nums[idx], nums[i] = nums[i], nums[idx]

# 예시로 [1, 2, 3]의 순열을 생성

permutation([1, 2, 3])

'''

[1, 2, 3]

[1, 3, 2]

[2, 1, 3]

[2, 3, 1]

[3, 2, 1]

[3, 1, 2]

'''

 

출력 값 전체는 동일하지만 자세히 살펴보면 순서는 다르다는 것을 확인 할 수 있다. 예시의 숫자가 작아서 차이가 거의 안나지만 경우의 수가 더 많아진다면 확연한 차이를 볼 수 있다. 그 이유는 함수식으로 표현한 것은 원본 데이터의 순서를 바꾸어 출력하기 때문이고, 위의 알고리즘은 for문을 통해 넣을 수 있는 수가 결정되기 때문이다. 

• 이 함수는 입력 리스트  nums 와 인덱스  idx 를 매개변수로 받는다 (미리 설정해도 된다)
• 먼저  idx 가 리스트의 마지막 인덱스에 도달 했는지 확인한다. 만약 도달했다면 현재 순열에서 원하는 행동을 하고 (출력)하고 함수를 종료한다
• 도달하지 않았다면,  idx 부터 리스트의 끝까지 반복한다. 반복에서  nums[idx] 와  num[i] 의 위치를 바꾸어 새로운 순열을 생성한다
• 이후 함수를 재 호출하여 다음 위치로 넘어간다
• 마지막으로 원래의 순열로 복원하기 위해  nums[idx] 와  num[i] 의 위치를 다시 바꾸어 돌아간다

방문체크(visited)를 사용하는 예시

def permutation(lst, visited, result, target):           # 매개변수로 데이터, visited 정보, 결과, 목표를 받아준다

    if len(result) == target:                                  # 타겟에 도달, 목표에 도달했을 떄의 기저조건

        print(result)                                               # 기저조건 달성시 필요한 행동 실행

        return                                                        # 실행 이후 return

    for i in range(len(lst)):                                   # 데이터의 길이만큼 깊어질 것이므로

        if visited[i] == False:                                 # 중복을 거르기 위해 False인지 확인하고

            visited[i] = True                                     # True로 바꿔주어 중복되지 않기위한 데이터를 저장한다다

            result.append(lst[i])                               # 해당 데이터를 일단 저장

            permutation(lst, visited, result, target)  # 깊어지기위한 함수 추가 실행

            visited[i] = False                                   # 빠져나온 후 복구

            result.pop()                                           # result에서도 제거

lst = [1, 2, 3]

visited = [False]*(len(lst))

result = []

target = 3

permutation(lst, visited, result, target)

'''

[1, 2, 3]

[1, 3, 2]

[2, 1, 3]

[2, 3, 1]

[3, 1, 2]

[3, 2, 1]

'''

 

좀더 직관적으로 확인할 수 있는 방법은 visited을 사용할 때가 더 도움이 많이 되었던 것 같다. target이라는 변수를 넣어서 내가 원하는 제한을 걸어 출력을 해줄 수 있다. 예를들어 순열의 길이가 2인 것을 원한다면 target에다가 2를 넣어주면 된다.

• 이 함수는 입력 리스트  lst , 방문 체크 리스트  visited , 결과를 저장할 리스트  result , 만족하는 조건  target 을 매개변수로 넣어준다
• 먼저  result 의 길이와  target 이 같은지 확인한다 만족한다면 현재의 순열을 출력하고 함수를 종료한다
• 그렇지 않다면  lst 의 길이만큼 반복하는데,  visited[i] 가 False인지 확인하고 False라면 True로 바꾸고  result 에   lst[i]  를 추가한다
• 다음으로 함수를 호출하여 다음 단계로 넘어간다
• 마지막으로  visited[i] 를 False 로 설정하고,  result 에서 마지막 데이터를 제거하여 이전 상태로 복원한다

---

결정과 복구 (commit and backtrack)

빨간 네모칸의 존재 이유

DFS에서 상태 공간 트리의 상태에 대한 결정과 복구를 하는 이유는 모든 가능한 경로를 탐색하고, 이전 상태로 복구하여 다른 가능한 경로를 탐색하기 위함이다. 각 진행 상태에서 결정을 통해 새로운 상태로 이동, 해가 유효하지 않거나 더이상 만족하는 해가 없다면 이전 상태로 복구하여 다른 가능한 경로를 탐색한다.

이를 결정과 복구 과정이라고 한다.

 s.append(i) 는 현재 상태를 새로운 상태로 이동하는 결정 단계.

 s.pop() 는 호출이 끝나고 난 후에 다른 경로의 탐색을 위해 한 단계 이전 상태로 복구하는 복구 단계.

---

사실 이론을 알고있어도 실제 문제에 적용하기에는 쉽진 않다. 경우가 모두 다르고 2차원 배열로 넘어가게되면 고려해줘야 할 것이 많아지기 때문이다.(백준의 N-Queen문제) 그래도 꼭 알아야하는 기법이고 알기만한다면 여러 알고리즘 문제를 손쉽게 풀 수 있을 것이다.