알고리즘 - 완전 탐색 응용

1.무식하게 전체 반복 : for 문과 if문을 이용해 전체를 다 훑어보는 방법.

2. 비트마스크 : 이진수의 각 비트를 배열의 요소로 생각해 0은 없는 것, 1은 있는 것으로 판단. 비트연산을 이용해 각 자리를 조작.

OR연산을 이용해 켜고 싶은 비트를 켠다.

AND와 NOT연산을 이용해 끄고 싶은 비트를 끈다.

XOR 연산을 이용해 토글 하고싶은 비트를 토글한다.

최하위 비트부터 i개를 전부 켜기 위해서는 SHIFT와 - 연산을 이용. (mask = (1 << i) - 1)

OR연산과 SHIFT - 연산을 합치면 이미 선언된 비트 마스크에서 최하위 부터 i개 비트를 켠다. 

 

두 비트마스크 에 대해 합집합, 교집합, 차집합, 대칭 차집합을 구할수 있다.

res = (mask1 | mask2) //합집합.   Mask1 AND Mask2

res = (mask1 & mask2) //교집합.  Mask2 OR Mask2

res = (mask1 & (~mask2)) //mask1 - mask2 차집합. 

res = ((~mask1) & mask2) //mask2 - mask1 차집합.

res = (mask1 ^ mask2) //대칭 차집합. 배타적 논리합 XOR

 

3. 순열 - 숫자의 배열을 나타내보는 것. n*(n-1)*(n-2)* ``` *2*1개의 가짓수를 가짐. 재귀 함수나 중첩루프, C++ 내장함수인 next_permutation함수 이용. n!(팩토리얼)의 가짓수를 가지기 때문에 중첩루프는 개 무식한 방법. 최소한 재귀함수를 쓰자. 

 

4. 백트래킹(DFS특수) : 기본적으로 깊이 우선 탐색법이다. 조건에 맞지않는 쪽의 가지는 굳이 탐색하지 않고 넘어가는 방식을 이용해 탐색범위를 좁히는 알고리즘.

 

5. BFS : 너비 우선 탐색법

 

ex1) N명의 학생들중 각각의 키 평균이 M이 되는 조합을 찾아라.

조건에 맞는 부분집합을 구하는 문제. 비트 마스크를 응용해서 풂.

마스크에 N개의 비트를 켜놓고 마스크를 -1씩 하면서 결과를 내어보는 것.

 

ex2) Baby Gin -  6개의 순열이 주어지고, 3자리가 1씩 등차순열 이면 Run, 같은수 3개 중복이면 Triplet. Run과 Triplet 이 같이 있거나 2개의 Run, 2개의 Triplet이면 Baby Gin

순열을 이용해 조합을 구함.

 

ex3)로또번호 고르기 : 6개의 숫자를 골라야하는 로또에서 후보군 N개의 수를 고르고(집합 S) S에서 6개를 고른 부분집합 S`를 구하는 방법. 백트래킹 응용.

 

ex4) 암호 제작 : L자리 암호를 구성하는 방법을 찾는 것. C개의 서로다른 문자가 후보군임. 암호는 오름차순으로 구성되었음. abcd는 가능하지만  badc는 불가능.  백트래킹 응용. 

 

ex5) 가장 먼 두점 구하기. 가장 가까운 두점 구하기

N개의 점중 두 점의 거리를 비교해 가장 먼 점, 가장 가까운 점을 구하는것.

2개의 점을 구해야 하기 때문에 이중 for 문을 이용해 구하는 방법. 

 

ex6) N개의 수를 N자리에 나열한 조합중에 가장 큰 수를 찾는 문제.

N개의 수를 N자리에 전부 배치해야하는 문제. N자리의 순열을 구한뒤 해당 수를 합침.

1.순열함수로 N개의 수 배열을 하나 구한다.

2.구한 배열의 합을 구한다.

3.최대값과 비교

4.크면 최대값과 결과배열 변경.

5. 전부 돌때까지 반복~