[알고리듬] 6주차: Backtracking

Divide-and-Conquer

문제(Computing problem)를 효율적으로 풀기 위한 일반적인(general) 방법론

 

점화식은 보통 이런 형태: $T(n) = rT(n/c) + O(f(n))$

 

 

Backtracking

탐색 알고리즘에서 많이 쓰는 기법(트리나 그래프 등)

미로에서는 일단 진행해보고 막다른 길에 다다르면 뒤로 돌아온다

그리고 아직 가보지 않은 길로 다시 진행한다. 이게 백트래킹

 

올바른(또는 최선의) 결정의 sequence를 통해 점진적으로 해를 구성한다 

여러 개의 갈림길 중 하나를 골라야 할 때는 모든 길을 다 가본다. 그리고 그 중 최상의 것을 선택한다.

어차피 그 갈림길들 중 하나는 답임.

 

N Queens problem

$n \;\times\; n$ 체스보드 위에 서로 공격받지 않도록 $n$개의 queen을 배치할 수 있는가?

queen은 가로, 세로, 대각선 상에 있는 말을 공격할 수 있다.

 

Gauss's recursive strategy

① 위에서부터 각 행에 queen을 하나씩 배치한다.

② $r$번째 queen을 $r$번째 행에 배치할 때 $n$개의 칸을 모두 시도한다.

② 어느 칸이 이번에 배치한 queen에 의해 공격받는 위치면 거기는 pass하고

② 그렇지 않으면 임시로 queen을 배치 후 다음 queen을 다음 row에 배치하는 과정을 반복한다.

② queen을 놓을 때마다 같은 문제의 더 작은 instance(subproblem)이 되므로 Recursion으로 풀 수 있다.

 

최초 호출: $PlaceQueens(Q,\; 1);$

$j$: 열 번호($1 \;\sim\; n$)

$legal$: 현재 위치에 queen을 놓을 수 있으면 $TRUE$, 아니면 $FALSE$

$i$: $i$번째 queen

$Q[1..n]$: queen이 놓인 위치

-> $Q[1],\; Q[2],\; \cdots,\; Q[r-1]$은 이미 queen이 놓여있는 위치를 의미함

 

$j = 1..n$에 대해 queen을 놓을 수 있는지 검사한다.

$r$번째 행의 $j$번째 칸이 공격받고 있으면 $legal$은 false가 된다.

$Q[i]=j$: 같은 열에 있는가?

$Q[i]=j+r-i$, $Q[i]=j-r+i$: 위의 대각선 포함 퀸들에 의해 공격받고 있는가?

$legal$은 공격받고 있는지를 나타내는 변수다.

 

* 왜 $Q[i]=j \;or\; Q[i]=j+r-i \;or\; Q[i]=j-r+i$인가?

$r$번째 퀸을 배치할 위치를 탐색하는 시점에서 $i = 1 \;to\; r-1$이다.

$i$번째 퀸이 대각선에 있는지 검사하려면 현재 위치($j$번째 열)를 기준으로 왼쪽으로 $r$, 위로 $r$ 옮긴 지점에서부터 탐색해야 한다. 이 위치는 $(r-r,\;j-r)$로 나타낼 수 있다(좌측 대각선 기준).

이 때 행 인덱스는 $i$로 표현되고, 행 인덱스가 커지면 열 인덱스도 똑같이 커져야 한다.

따라서 탐색할 위치는 $(r-r+i,\; j-r+i) \;=\; (i, j-r+i)$가 된다.

그런데 실제 검사는 2차원 배열에서 $A[i][j-r+i]$와 같이 이루어지는 게 아니라,

$i$번째 행에서의 퀸이 몇 번째 열에 있는지 나타내는 $Q[i]$로 검사한다.

따라서 $i = 1 \;to\; r-1$에 대해 $(i, j-r+i)$에 퀸이 있는지 검사하려면 $Q[i]=j-r+i$가 참인지 검사해야 한다.

오른쪽 대각선은 반대니까 $j-(-r+i) = j+r-i$로 하면 됨.

 

 

이 검사를 거치고 나면 $Q[r] \;\leftarrow\; j$로 임시로 배치함

 

 

 

Subset sum

Input: 집합 $X$, 목표 정수 $T$

Output: $X$의 부분집합 중에 합의 $T$와 일치하는 것이 있는가?

 

Ex) $X = \{8,\; 6,\; 7,\; 5,\; 4,\; 10,\; 9\},\;\; T=15$

-> $\{8,\; 7 \},\;\; \{5,\; 10 \},\;\; \{6,\; 9 \},\;\; \{7,\; 5,\; 3\}$

-> $\therefore\;\; TRUE$

 

Knabsack, Scheduling, Assignment 등의 문제(CPU나 메모리 관리)에서 사용됨

 

Trivial cases(Base cases)

$T \;=\; 0$

항상 $TRUE$: 공집합이 있으니까

*공집합은 모든 집합의 부분집합임

 

$T \;<\; 0$

항상 $FALSE$

$T > 0\; \& X \;is\; empty$

항상 $FALSE$

 

General cases

$X$의 임의의 원소 $x$에 대해, 총합이 $T$인 $X$의 부분집합이 있다면

ⓐ $x$를 포함하거나: 총합이 $T-x$인 부분집합 $X-\{x\}$가 존재한다

ⓑ $x$를 포함하지 않거나: 총합이$T$인 부분집합 $X-\{x\}$가 존재한다

= 이 원소를 선택해야 할까? -> Backtracking

 

따라서 $subsetSum(X, T)$는 $subsetSum(X-\{x\}, T-x)$와 $subsetSum(X-\{x\}, T)$로 reduce할 수 있음

둘 다 $subsetSum(X, T)$의 smaller instance이므로 recursion 가능

 

근데 $x$를 포함시켜야 하는지 아닌지 모르니까 일단 해보고 아니면 되돌아옴 = Backtracking

 

Q1. $x$는 어떻게 뽑아내지?

Q2. 집합은 코드 상에서 꽤 모호함

 

 

 

A1. $any\;\;element\;\;x$는 parameter에 $i$를 추가해 $X[i]$로 설정

A2. 집합 X는 배열로 표현

 

$i$: 현재 subset의 last index

$else\;\;if\;\;T<0\;\;or\;\;i=0$: 합은 0보다 작을 수 없고 $i$는 인덱스이므로 $1 \;\leq\; i \;\leq\; n$

 

Time complexity

$(n-1)$ 크기로 두 번의 재귀호출 + 상수번 연산

따라서 시간복잡도 함수를 $A(n)$이라 하면

$A(n) \;\leq\; 2A(n-1)+O(1)$

$\therefore\;\;\;A(n)=O(2^n)$ (대충 엄청 느리다는 뜻)

 

왜 $O(2^n)$이나 될까?

최악의 경우 $X$의 부분집합을 다 조사해봄

* $n(X)=n$일 때 $X$의 부분집합의 수는 각 원소에 대해 선택하거나/안 하거나의 두 경우가 있으므로 $2^n$개임

 

 

변형: 합이 $T$인 부분집합을 출력하기, 합이 $T$인 부분집합의 개수 리턴, etc.

 

 

 

Backtracking: General pattern

 

<Algorithms> page 79

Backtracking algorithms are commonly used to make a sequence of decisions, with
the goal of building a recursively defined structure satisfying certain constraints.
Often (but not always) this goal structure is itself a sequence.

 

Backtracking은 대부분의 경우 결정의 sequence를 만들어 낸다.

이 때 목표는 특정 제약조건을 만족하는, 재귀적으로 정의된 구조를 만드는 것이고,

이는 (항상은 아니지만) 그 자체로 goal structure가 된다.

 

N-queens

Goal: queen 위치의 sequence를 찾는 것

제약조건: 행 당 하나씩 있어야 하며 모든 퀸은 서로 공격할 수 없어야 함

알고리즘은 각 행에서 queen을 어디 놓을지 결정함

 

Subset sum

Goal: $X$의 원소의 sequence를 찾는 게 목적

Contstraints: 그 sequence에 속한 원소들의 합이 $T$여야 함

알고리즘은 각 원소를 포함할지 말지 결정

 

 

General pattern

각각의 재귀호출에서 정확히 하나의 결정을 내릴 필요가 있고, 그런 결정은 이전의 결정에 대해 일관성이 있어야 한다.

따라서 각 재귀호출은 이전의 호출로부터 어떤 정보, 즉 이전의 결정의 정보가 필요하다.

다만 효율을 위해 요약된 정보를 넘긴다.

 

N queens

빈 row의 정보

이미 배치된 queen의 정보

 

Subset sum

포함 여부를 고려하지 않은 나머지 element들의 정보

남은 Target의 값(기존 R에서 선택된 element의 값을 뺀 값)

 

 

알고리즘 설계 시 어떤 정보가 필요한 지 고려한다.

즉 알고리즘 수행 중간에, 이전 결정에서 뽑아올 정보가 무엇인지 결정해야 함

만약 이런 정보가 무엇인지 자명하지 않다면 더 general한 문제를 풀 필요가 있을 수 있다.

최종적으로 좀 더 일반적인 문제를 풀게 되고, 그 문제가 무엇인지 정해졌다면 다음 결정을 위해 recursive brute force로 문제를 해결한다. (대충 일단 다 때려넣어보라는 뜻)

 

 

Subsequence

Sequence

원소들이 순서를 갖고 나열된 것

수열, 문자열, 배열, etc.

 

Subsequence

어떤 sequence $S$에 대해

$S$의 원소 중 0개 이상 제거해 얻을 수 있는 sequence

 

 

Longest Increasing Subsequenece

원소가 증가하는 순서로 되어 있는 부분열

 

Input: $n$개의 정수로 구성된 Sequence $A[1..n]$

Output: LIS의 길이

 

어떤 결정의 연속(Sequence of decision)을 통해 LIS를 만들어 내기

결정: 임의의 subsequence는 주어진 Sequence A의 각 원소를 포함하는지/포함하지 않는지

-> $A[j]$가 subsequence에 포함되는지 안 되는지 결정함 - Step 1

 

3

1

4

1

5

9

2

6

5

3

5?

8

9

7

9

3

2

3

8

4

5는 추가할 수 없으니까 넘어가자

 

3

1

4

1

5

9

2

6

5

3

5

8?

9

7

9

3

2

3

8

4

8을 추가할 수는 있지만 꼭 그래야 할까..?

 

즉 $A[j]$가 subsequence에 포함되는지 안 되는지 결정하려면

ⓐ 임시로 8을 추가한 후 나머지 결정을 recursion(하나 줄었으니까 가능)

ⓑ 임시로 8을 제거한 후 나머지 결정을 recursion(하나 줄었으니까 가능)

후 더 긴 increasing subsequence가 나오는 것으로 결정 - Step 2

+ 당연히 $A[j]$는 이전에 선택한 원소들보다 커야 함(increasing subsequence니까)

 

이전 결정들에 의해 $A[1..j-1]$은 increasing subsequence고, A[j]는 그것들보다 커야함

-> A[j]는 이전 subsequence의 마지막 원소보다 크면 됨

-> Recursive call에 이전 subsequence의 마지막 원소를 넘겨줌-Step 3

 

 

Original problem

Input: $n$개의 정수로 구성된 Sequence $A[1..n]$

Output: LIS의 길이

 

실제로는 더 generalize된 문제를 풀게 됨

Input: $A[1..n]$, an integer $prev$(이전 subsequence의 마지막 원소)

Output: (모든 원소가 $prev$보다 큰) A의 LIS의 길이

 

조건이 더 많은데 왜 더 일반화된 문제?

두 번째 문제를 풀면 LIS 문제를 풀 수 있음 ($prev=-\infty$로 두면 풀어짐)

반대로 첫 번째 문제를 풀어도 두 번째 문제를 풀 수는 없음

 

 

LISbigger problem

Input: $A[1..n]$, an integer $prev$(이전 subsequence의 마지막 원소)

Output: 모든 원소가 $prev$보다 큰, A의 LIS의 길이

 

Pseudocode of LISbigger problem

$n=0$: Base case

 

$A[1] \;\leq\; prev$면 당연히 $A[1]$은 버림($prev$보다 큰 subsequence를 구해야 하니까)

 

$skip$은 $A[1]$을 포함하지 않는 subsequence

$take$는 $A[1]$을 포함하는 subsequence

$+1$: 재귀호출의 결과는 $A[2..n]$의 subsequence = $A[1]$이 빠진 결과니까

 

 

근데 이거는 $A$를 잘라서 subarray를 parameter에 줄 수 있을 때 얘기고

$A$를 고정한 상태로 인덱스만으로도 제어가 가능하다.'

 

For fixed $A$

Input: indices $i$, $j$

Output: $A[i]$보다 큰, $A[j..n]$의 LIS의 길이

 

 

 

LIS Problem

Input: $n$개의 정수로 구성된 sequence $A[1..n]$

Output: $A$의 LIS의 길이

 

Time complexity: $O(2^n)$

마찬가지로 가능한 부분열의 수는 $2^n$개니까..

 

Recurrence of LIS problem

점화식이 한 줄로만 나오지는 않는다 ^^

 

Pseudocode of LIS problem

* 왜 $LISfirst(0)$으로 호출하는가?

현재 $A[i]$보다 큰 요소들을 LIS에 포함시키므로 처음 호출 시 $i$에는 $A$의 최솟값의 인덱스가 주어져야 한다.

그런데 $A[1]$이 $A$의 최솟값이라고 단정지을 수 없으므로 $A[1]$로 시작할 수 없다.

따라서 무조건 가장 작은 값($A[0]=-\infty$)을 하나 설정한 후 그 값과 비교하며 진행하는 것이 합리적이다.

 

LIS 2

앞의 알고리즘은 $A[j]$의 포함 여부에 초점이 맞춰져 있다.

반대로 생각하면 '뒤에 남은 원소들 중에 다음에 포함할 원소는 어느 것인가?'로 볼 수도 있다.

이 5개 중에 뭐가 최선인지 현재는 알 수 없음

-> 각 경우에 대해 (Recursion으로) 따져보고 그 중 최선인 것을 선택함

 

 

이 과정을 거쳐 하나를 고른 후에 남은 원소들에 대해 같은 작업을 반복함

 

어쨌든 이전 결정에서는 마지막 원소만 기억하면 됨

 

$LISfirst(i)$

$A[i..n]$의 LIS의 길이

$cf.\;\; max\;\; \varnothing \;=\; 0$

$j>i$: $A[j]$는 $A[i]$보다 뒤에 있어야 함

$A[j] > A[i]$: $A[j]$는 $A[i]$보다 커야 함

 

마지막 원소만 기억해도 뒤의 decision에는 지장이 없음

 

$A[i]=6$ -> 8, 9, 7, 9, 8

 

 

왜 $LISfirst(0) - 1$인가?

$A[0]=-\infty$고 반환값은 $A[0..n]$의 LIS의 길이니까

A[1..n]의 LIS 길이를 구하려면 1($A[0]$)을 빼야 함

 

 

 

Backtracking(General)

어떤 결정의 연속을 형성함으로써 문제의 답을 점진적으로 만들어 간다.

이 결정이 무엇에 대한 결정인지는 내가 정해야 됨

이전 선택에 대한 정보를 recursive call할 때 전달함으로써 결정의 sequence는 일관성을 띰

이 때 각 recursive call에서는 하나로 결정을 내려야 하며, 이런 결정은 이전의 결정들과 일관적이어야 한다.

-> 매 호출 시 이전 선택에서 필요한 정보를 뽑아서 전달

따라서 문제의 일반화(generalization)가 필요함