Algorithm - Exhausitive Search

완전 탐색 알고리즘

• 모든 경우의 수를 다 체크해서 정답을 찾는 방법
• 문제의 정확한 결과값을 얻을 수 있는 가장 확실하고 기초적인 방법

완전 탐색으로 문제를 푸는 방법

• 해결하고자 하는 문제의 가능한 경우의 수를 대략적으로 계산함
• 가능한 모든 방법을 계산함
  1. Brute Force
  2. Permutation(순열)
  3. Recursion(재귀)
  4. Bitmask
  5. DFS / BFS
• 실제 답을 구할 수 있는지 적용함

각 방법에 대한 설명

1. Brute Force 기법

• 반복 / 조건문을 통해 가능한 모든 방법을 단순히 찾는 기법

2. Permutation(순열)

• 순열 : 임의의 수열이 있을 때, 그 수열을 다른 순서로 연산하는 방법

• 같은 데이터가 입력된 수열이지만 순서에 따라 의미가 다름

• 순서를 통해 연결되는 이전 / 다음 수열을 찾아낼 수 있음

• 예를 들어 N개의 서로 다른 데이터들을 순열로 나타낼 경우,

  • 각 자리에 오는 경우의 수는 N, N-1, N-2, ..., 1개이므로, 전체 순열의 경우의 수는 N!임

• [1, 2, 3]을 사전 순으로 나열하는 순열이 있다고 가정했을 때, 아래와 같이 나열될 수 있음

{1 2 3} // 최초 순열 (오름차순)
{1 3 2}
{2 1 3}
{2 3 1}
{3 1 2}
{3 2 1} // 최종 순열 (내림차순)

• 사전 순 순열의 규칙
  • 최초 순열은 오름차순, 최종 분열은 내림차순임
  • N 개의 데이터가 있고 1 ~ i번째 데이터를 설정했을 때, i번째 데이터 기준 최종 순열은 i + 1부터 N까지가 모두 내림차순임
  • N 개의 데이터가 있고 1 ~ i번째 데이터를 설정했을 때, i번째 데이터 기준 최종 순열은 i + 1부터 N까지가 모두 오름차순임

3. Recursion(재귀)

• 재귀 함수 : 자기 자신을 호출하는 함수
• 재귀 함수를 사용할 때 중요한 점
  • 재귀를 탈출하기 위한 탈출 조건이 필요함
  • 현재 함수의 상태를 저장할 Paramter가 필요함
  • Return문을 통해 필요한 값을 반환하여 정답을 구하는 연산에 사용함

4. Bitmask

• Bitmask : 비트(bit)연산을 통해서 부분 집합으로 표현하는 방법
  • AND 연산(&) : 둘 다 1일 경우 1
  • OR 연산(|) : 둘 중 1개만 1이면 1
  • NOT 연산(~) : 1이면 0, 0이면 1
  • XOR 연산(^) : 둘의 관계가 다르면 1, 같으면 0
  • Shift 연산(<<,>>) : A<<B라고 한다면 A를 좌측으로 B비트만큼 밈

A	B	A&B	`A	B`	~A
0	0	0	0	1	0
0	1	0	1	1	1
1	0	0	1	0	1
1	1	1	1	0	0

• 비트 연산으로 집합을 나타내는 방법
  • 정수로 집합을 나타내는 것이 가능함
  • 예를 들어 0 ~ 9까지의 숫자로 이루어진 집합 중에서 부분집합 A가 {1, 3, 4, 5, 9}라고 가정할 경우, 이를 570이라는 숫자로 나타낼 수 있음
    • 각각의 숫자가 있는 경우 1, 없는 경우 0으로 표시함
    • 아래의 비트를 2진수로 보면 1000111010과 같으므로 10진수로는570이 됨

숫자	9	8	7	6	5	4	3	2	1	0
비트	1	0	0	0	0	1	1	1	0	1

• AND 연산을 사용한 집합 포함 여부 검사
  • 예를 들어 현재 집합이 {1, 3, 4, 5, 9}=570일 때, 0이 포함되어 있는지에 대한 여부를 검사하는 방법
    • 0번째 비트만 1로 만들고 나머지 비트들은 0으로 만든 수와 현재 집합을 비트로 표현한 수(570)를 AND(&) 연산하여 현재 집합에서 0의 포함 여부를 알 수 있음
    • AND 연산은 둘 다 1인 경우에만 1이므로, AND 연산의 결과가 1일 경우 해당 숫자는 집합에 포함되어 있다는 것을 의미함

// 0의 포함 여부를 확인하는 경우
  1 0 0 0 1 1 1 0 1 0
& 0 0 0 0 0 0 0 0 0 1
---------------------
  0 0 0 0 0 0 0 0 0 0

• OR 연산을 사용하여 특정 숫자 추가하기
  • 특정 숫자를 추가하기 위해 해당 위치의 비트를 1로 만든 수와 현재 집합을 비트로 표현한 수를 OR(|) 연산함
  • OR(|) 연산은 둘 중 하나만 1이어도 1이므로, 추가하고자 하는 위치의 비트가 1로 변경됨

// 2를 추가하는 경우
  1 0 0 0 1 1 1 0 1 0
| 0 0 0 0 0 0 0 1 0 0
---------------------
  1 0 0 0 1 1 1 1 1 0

• NOT과 AND 연산을 사용하여 특정 숫자 제거하기
  • NOT(~) 연산으로 제거하고자 하는 위치의 비트만 0으로 하고 나머지는 1로 만든 수와 현재 집합을 비트로 표현한 수를 AND(&) 연산함
  • 이렇게 연산할 경우, 제거하고자 하는 위치의 비트만 0으로 바뀌고 나머지 비트들은 그대로 있음

// 4를 제거하는 경우
  1 0 0 0 1 1 1 0 1 0
& 1 1 1 1 1 0 1 1 1 1
---------------------
  1 0 0 0 1 0 1 0 1 0

• XOR 연산을 사용하여 특정 숫자 토글하기
  • 특정 숫자가 있으면 없애고, 없으면 추가해주고 싶을 때 XOR(^) 연산을 수행함

// 3을 토글하는 경우
  1 0 0 0 1 1 1 0 1 0
^ 0 0 0 0 0 0 1 0 0 0
---------------------
  1 0 0 0 1 1 0 0 1 0

• Shift 연산을 사용하여 전체 집합 표현하기
  • 전체 집합은 모든 숫자가 1이므로, N개의 비트가 모두 1이라는 의미임
  • 0부터 시작하므로 좌측으로 N번 이동한 뒤 1을 빼주면 됨

전체 집합 : (1<<N) - 1
공집합 : 0

5. BFS / DFS

• BFS / DFS는 그래프 자료 구조에서 완전 탐색을하는 대표적인 방법임
  • DFS : 스택 또는 재귀를 이용하여 최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우 다른 정점을 탐색하는 방법
  • BFS : 큐를 이용하여 현재 정점과 인접한 정점들을 최대한 넓게 탐색한 다음, 더 이상 탐색할 정점이 없을 때 아래로 이동하며 탐색하는 방법

참고

• 알고리즘 - 완전탐색(Exhausitive Search)