완전탐색 톺아보기
완전탐색이란 무엇인가?
가능한 모든 경우의 수를 찾아보는 것을 완전 탐색이라고 한다
(주로, 재귀적으로 실행됨)
완전 탐색의 종류로는 다음과 같다
- Brute Force
- 순열
- 재귀 호출
- 비트마스크
- BFS, DFS
Brute Force
반복 / 조건문을 통해 가능한 ‘모든' 방법을 단순하게 찾는 경우를 의미한다
순열(permutation)
순열은 임의의 수열이 있을 때, 그것을 다른 순서로 연산하는 방법을 의미한다
=> [1,2,3] 과 [3,2,1]은 다른 순열임
재귀(Recursive)
비트마스크(Bitmask)
비트마스크란 비트 연산을 통해서 부분 집합을 표현하는 방법을 의미
- AND 연산(&) : 둘다 1이면 1
- OR 연산(|) : 둘 중 1개만 1이면 1
- NOT 연산(~) : 1이면 0 / 0 이면 1
- XOR 연산(^) : 둘의 관계가 다르면 1, 같으면 0
- Sihft 연산(<<,>>) : A << B이면 A를 좌측으로 B비트만큼 미는 것
| A | B | A & B | A | B | ~A | A ^ B |
| 0 | 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 | 0 |
우리는 보통 2진수가 아니라 10진수로 표현되기 때문에,
13과 72를 2진수로 표현한 뒤, 연산을 진행하면된다
13 = 1101(2)
72 = 1001000(2)
13의 경우 부족한 앞의 3자리를 0으로 채우면 비트연산이 가능하다
0001101
&1001000
0001000
=> AND 연산 실행
0001101
| 1001000
1001101
Shift 연산 수행하는 법
<<, >>로 표현되며 해당 방향으로 비트가 특정 값만큼 이동된다
1 << 3 연산을 보자
1을 2진수로 표현하면 다음과 같다
0001(2)
이를 3칸 좌측으로 이동시키므로, 1 << 3 연산이 수행되고 나면,
1000(2)로 바뀌게 된다
그럼, 5 << 3을 실행해보자
5를 2진수로 표현하면 다음과 같다
0101(2)
5<<3 연산이 수행되고나면
0101000(2)
이를 통해 알 수 있는 것이 있는데, A << B 연산이 있을 때, A * 2^B라는 사실을 알 수 있다
shift 연산을 통해 한칸씩 왼쪽으로 이동할 때마다, 2씩 곱해지기 때문에 A << B라면 A * 2^로 나타낼 수 있다
또한, A >> B라는 연산이 있을 떄에는 이진수를 우측으로 B만큼 밀기 때문에 2^B만큼 나눠진다
정리하자면, 다음과 같다
A << B = A * 2^B
A >> B = A/(2^B)
또한, 비트 연산을 집합으로 나타낼 수 있는데, A = {1,3,4,5,9}라고 가정하면 570이라는 하나의 숫자로 나타낼 수 있다
각각의 숫자가 있으면 1, 없는 경우 0으로 표시할 수 있게 된다
| 숫자 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 비트 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 |
전체 저장 공간 절약이 되며, index로도 활용이 가능하다는 장점이 있다
BFS / DFS
BFS는 너비 우선으로 현재 정점과 인접한 정점을 우선으로 탐색하는 방법이며
DFS는 깊이 우선 탐색으로 현재 인접한 정점을 탐색 후 그 다음 인접한 정점을 탐색하는 방식이다