algorithm_완전 탐색

완전탐색

• 가능한 모든 경우의 수를 조사하여 답을 구하는 방법

문제를 완전탐색을 통해 풀어내고자 할 때
사용할 수 있는 완전탐색 기법의 종류가 몇개 있다

완전탐색 기법 종류

1. Brute Force

• 반복문과 조건문 활용으로 모든 경우 테스트

2. Bit Mask

• 각각 원소가 포함 된다 / 안된다 = 0 / 1
  -> 2진수 이용하는 컴퓨터 연산을 이용하는 방식
  
  -> 우측에는 S에 포함되는 값인지 체킹하고 싶은 집합(S의 부분집합)
  -> s에 속하는 값이 우측 집합에 있으면 1, 없으면 0
  -> 좌측의 0, 1, 2, 5, 14, 31 은 비트마스크된 2진 표현을 10진수로 표현했을 때의 값

3. 재귀 함수

• 재귀
  = 자기 자신을 호출한다
• 예시
  원소의 개수가 3인, S의 부분집합을 만드는 문제가 주어졌다면
  {1,3,4}, {1,3,7}, {1,3,10}....이 될것
  여기서 1은 고정시키고나머지 원소들을 넣는 것이기 때문에
  1이 넣어진 상태로 {1, , }
  -> 재귀적으로 함수를 호출하여 그 다음 원소가 불러진다
  -> 이때 두번째 원소인 3을 찾기위해 1, 2가 S에 포함되는지 아닌지 판별하는 과정이 필요하다
  -> 이후에 3이 S에 포함되는 값인 3을 찾아 1, 3이 넣어진 상태로 {1,3, }
  -> 재귀적으로 함수를 또 호출하여 그 다음 원소인 4가 넣어지는 것이다 {1,3,4}
• 이때 이렇게 원소를 하나씩 S에 속한다/속하지 않는다를 통해
  속하면 재귀함수가 호출되고
  속하지 않으면 거기서 재귀함수로 두번째 또는 세번째 원소가 호출되지 않고 있기 때문에
  비트마스크와 같이 2가지 선택을 가질 때 유용하게 쓰임

4. 순열

• 임의의 수열 -> 다른 순서로 나열하여 연산
• 순열을 가진다는 것의 의미는
  {1,2,3} 과 {3,2,1}이 다르다는 의미이다
• 다음 순열을 구하면서 모든 순열을 구하며
  완전 탐색이 진행된다

5. DFS/ BFS

• BFS = 너비 우선탐색
  : 현재 정점과 인접한 정점을 우선으로 탐색
  -> 인접한 정점들을 모두 탐색한 이후에
  -> 인접한 정접들의 인접한 정점들을 탐색하는 방법
• DFS = 깊이 우선탐색
  : 현재 정점과 인접한 정점을 탐색한 후
  -> 그 다음에 인접한 정잠을 탐색하여 끝까지 탐색하는 방식
• 예시 (택배) -> 완전 정확한 비유는 아님/ 감잡는 예시
  - 단독주택 마을에서
  골목길 끝에 길 부터 들어간뒤
  차례로 택배 전달
  - 아파트에서
  1층 의 101~109호 전달한뒤에
  2층 의 201~209호 전달하는 택배 방식
  

참고 링크

[알고리즘] 완전탐색 벨로그글
[Algorithm] 완전탐색 벨로그글 2
알고리즘 - 완전탐색(Exhaustive Search) 티스토리