[SW Expert Academy] Advanced-2 완전 검색

문제 풀이의 시작은 완전 검색이다.
가장 단순한 풀이방식이므로, 문제가 어렵게 느껴질때는, 가장 먼저 대입해봐야 할 아이디어이다. 
특히, 순열, 조합의 수도코드(recursion 함수)는 잘 써먹을 수 있어야한다.
삼성 A형 문제의 경우 종종 순열을 구현해야할 때가 있다.

플로우 1. 완전 검색 2.순열 3.부분집합 4.조합 

1. 완전 검색
-속도는 매우 느려질 수 있으나, 대부분의 문제를 해결할 수 있는 단순하고 기본적인 방법이다.
-문제를 풀 때에는 먼저 완전 검색을 고민하고, 이보다 더 시간 효율적인 알고리즘을 고민해 봐야한다.

2. 순열
-nPr = n*(n-1)*....*(n-r+1)
-외판원 순회 문제
경우의 수: O(n!) <입력값이 커질수록 시간 복잡도가 폭발적 증가한다>
n=11 -> 수행시간이 초(second)단위로 걸림
n=17 -> 수행시간이 연(year)단위로 걸림

-순열 생성 코드 (n=3일때)
-2.1. 기본
for i1 in 1->3
 for i2 in 1->3
  if i1 != i2
   for i3 in 1->3
    if i3 != i1 && i3 != i2
     print (i1, i2, i3)

->순열의 갯수(n)만큼 n개의 루프를 구현해야하므로 비효율적이다.
->재귀함수를 이용하면, 하나의 재귀함수와 루프만으로도 내부에서 무한의 루프를 나타낼 수 있음.

-2.2. Johnson-Trotter Algorithm (**중요**)
-이전 순열에서 두개만 순서를 교환하여 새로운 순열을 만드는 방법
-높이가 n인 트리를 생각해보자
-level 0에서는 첫번째 인덱스와, 나머지 인덱스의 순서를 바꾼 순열들의 집합이 노드가 된다. 노드의 수는 n
-level 1에서는 첫번쨰 인덱스는 고정시키고, 두번째 인덱스와 나머지 인덱스의 순서를 바꾼 순열의 집합이 노드가 된다. 노드의 수는 n-1
-최종 leaf 노드의 집합이 곧 순열의 집합이다.

    level 0             level 1
{1 2 3 4}  ----> {1 2 3 4} ----> {1 2 3 4} ----> {1 2 3 4}
{2 1 3 4}           {1 3 2 4}         {1 2 4 3}         
{3 2 1 4}           {1 4 3 2}
{4 2 3 1}

caller: perm(n, 1)

perm(n, k): //k는 노드의 level, n은 순열의 갯수
 if k==n:
  print array //array은 전역 변수임
 else
  for i in k->n-1: //for문은 트리의 같은 레벨의 노드 순회
   swap(k, i)
   perm(n, k+1) //recursion은 자식 노드 순회
   swap (k, i)
   
->트리와 recursion 함수의 관계를 잘 이해해서 써먹어야함.

3.  부분 집합 -> 2^n
-Knapsack(배낭) 문제
Greedy/Dynamic programming으로 해결 가능ㅎ
-부분 집합을 생성할 때는 binary counting
비트 표현을 통해서 부분 집합을 나타낼 수 있다. 
원소 수(4) -> 비트: 0000 ~ 1111
-> 1<<4 미만의 숫자들로 표현 가능

4. 조합 nCr
nCr = n! / (n-r)!r! (if n>=r)
nC0=nCn=1
nCr = nCn-r
nCr = n-1Cr-1 + n-1Cr (재귀적 표현)

comb(n, r):
 if r==0: print array tr //tr는 조합의 임시 저장 배열(전역)
 elif n<r: return
 else:
  tr[r-1] <= an[n-1] //an은 input array(전역)
  comb(n-1, r-1)
  comb(n-1, r) //앞에서 넣은 것은 자식 순회 시 덮어씌워짐

level0     level 1
(5, 3)  ---> (4, 2) ---> ....
                 (4, 3)