1. 완전탐색 알고리즘이란?
완전탐색은 간단히 가능한 모든 경우의 수를 다 체크해서 정답을 찾는 방법이다. 즉, 무식하게 가능한 거 다 해보겠다는 방법을 의미한다.
이 방법은 무식하게 한다는 의미로 "Brute Force"라고도 부르며, 직관적이어서 이해하기 쉽고 문제의 정확한 결과값을 얻어낼 수 있는 가장 확실하며 기초적인 방법이다.
예를 들어, 4자리의 암호로 구성된 자물쇠를 풀려고 시도한다고 생각해보자. 이 자물쇠가 고장난 것이 아니라면, 반드시 해결할 수 있는 가장 확실한 방법은 0000 ~ 9999까지 모두 시도해보는 것이다.(최대 10,000번의 시도로 해결 가능)
하지만, Computer Science에서 문제 해결 알고리즘을 사용할 때는, 기본적으로 2가지 규칙을 적용한다.
1. 사용된 알고리즘이 적절한가? ( 문제를 해결할 수 있는가 )
2. 효율적으로 동작하는가?
위 2가지의 규칙에 대해서 생각할 때, 1번은 만족될 수 있는 가장 확실한 방법이겠으나 대부분의 경우 2번의 경우 때문에 이 방법이 사용되는데는 제한이 따른다.
예를 들어, 다이나믹 프로그래밍으로 해결할 수 있는 알고리즘 문제 중 백준 1912번을 알아보자(관련 포스팅은 여기)
해당 문제를 다이나믹 프로그래밍으로 해결한다면 약 O(N)으로 해결할 수 있지만 완전 탐색으로 진행한다면 각 위치 N에 대해 이전의 경우의 수를 모두 따져봐야 하니 2중 반복문에 의해 O(N^2)의 시간복잡도를 갖게 될 것이다.
그렇다면, N이 최대 100,000이므로 주어진 시간 이내에 풀어낼 수 없는 경우가 생길 수 있다. 따라서, 완전탐색 기법을 사용 시에는 그 문제에 대한 파악이 중요하다.
2. 완전탐색 기법을 활용하는 방법
우선 완전탐색 기법으로 문제를 풀기 위해서는 다음과 같이 고려해서 수행한다.
1) 해결하고자 하는 문제의 가능한 경우의 수를 대략적으로 계산한다.
2) 가능한 모든 방법을 다 고려한다.
3) 실제 답을 구할 수 있는지 적용한다.
여기서 2)의 모든 방법에는 다음과 같은 방법 등이 있다.
① Brute Force 기법 - 반복 / 조건문을 활용해 모두 테스트하는 방법
② 순열(Permutation) - n개의 원소 중 r개의 원소를 중복 허용 없이 나열하는 방법
③ 재귀 호출
④ 비트마스크 - 2진수 표현 기법을 활용하는 방법
⑤ BFS, DFS를 활용하는 방법
3. 각 방식에 대한 설명
① Brute Force 기법
이 방법은 반복 / 조건문을 통해 가능한 모든 방법을 단순히 찾는 경우를 의미한다. 예를 들어, 위의 자물쇠 암호를 찾는 경우와 같이 모든 경우를 다 참조하는 경우가 그러하다.
② 순열(Permutation)
우선 순열이 무엇인지 이해하자. 순열은 임의의 수열이 있을 때, 그것을 다른 순서로 연산하는 방법을 의미한다.
즉, 순서가 중요함! 만약, 수열에서 숫자 [1, 2, 3]이 있다면, 이것을 [1, 2, 3]으로 보는 순서와 [3, 2, 1]로 보는 순서가 차이가 있음이 중요한 경우를 의미한다.
같은 데이터가 입력된 수열이지만, 그 순서에 따라 의미가 있고 이 순서를 통해 연결되는 이전 / 다음 수열을 찾아낼 수 있는 경우를 계산할 수 있다.
그래서, 만약 N개의 서로 다른 데이터가 있고 이를 순열로 나타낸다면 전체 순열의 가지 수는 N!개가 된다. 최초에 N개 중 1개가 올 수 있고 그 이후에는 각각 N-1, N-2, ... , 1개가 올 수 있어 이를 모두 곱하면 N!이 되기 때문이다.
[1, 2, 3]을 사전 순으로 나열하는 순열이 있다고 가정해보자. 그러면 아래와 같이 나열될 수 있을 것이다.
위 내용과 같이 순열을 나열할 수 있는데, 최초 / 최종 순열을 보면 숫자가 오름 / 내림차순인 것을 알 수 있다. (중복된 숫자가 있다면 비내림 / 비오름차순으로 된다.)
여기서 사전 순 순열의 규칙을 알아낼 수 있는데 N개의 데이터가 있고 1~i번째 데이터를 설정했을 때, i번째 데이터 기준 최종 순열은 i+1부터 N까지가 모두 내림차순이라는 것이다.(반대로 최초 순열이면 i+1부터 N이 오름차순!)
예를 들어, 1 3 2를 보자. 이는 0번째 숫자가 1일 때의 최종 순열이다. 왜냐하면 3 2는 내림차순이기 때문이다. 그렇다면 이 다음 순열은 어떻게 구할 수 있을까?
i번째가 고정이었고 i+1부터 내림차순인 경우가 최종 순열이므로 다음은 i번째부터 모두 오름차순이 되는 최초 순열이 된다. 즉, i-1까지는 변동이 없고 i는 i+1 ~ N까지의 숫자 중 자신보다 크지만 가장 작은 숫자와 교환이 되고 그 i+1~N은 다시 오름차순이 되어야 한다.
그래서 1 3 2의 다음 순열은 2 1 3이다. 1 3 2에서 1은 2와 교체되었고 1 3은 오름차순으로 정렬되었다.
이러한 규칙을 통해 이전 / 다음 순열을 구하거나 모든 순열을 완전 탐색으로 구하는 로직을 구현할 수 있게 된다.
그 로직은 다음과 같다.
※ 순열을 구현하는 방법
현재 순열을 구성하는 배열을 A라고 하고 i,j는 그 배열의 index 값을 의미한다고 하자. 예를 들어 A={7, 2, 3, 6, 5, 4, 1}이고 i, j는 각각의 index 값이다.
아래에서는 현재의 다음 순열을 구하는 로직을 기반으로 설명한다.
1. A[i-1] <= A[i]를 만족하는 i 중 가장 큰 값을 찾는다.(혹은 뒤에서부터 찾는 경우 A[i-1] >= A[i] 중 가장 작은 i를 찾는다.)
→ 현재 i값을 기준으로 이후는 모두 내림차순으로 되는 경우를 찾는 다는 것이다. 현재 기준 최종 순열을 찾음
A배열을 보면 A[i-1] < A[i]가 되는 가장 큰 i는 6인 3번째(0부터 시작)이다. 즉, i=3이 된다.
2. j >= i 중, A[j] > A[i-1]을 만족하는 가장 큰 j의 값을 찾는다.
→ 현재가 최종 순열 상태이므로 i-1번째 숫자를 변경하여 최초 순열을 찾아야 한다.
A배열을 기준으로 i-1번째 숫자는 3으로 3보다 큰 경우는 6, 5, 4이나 그 중 j 값이 가장 큰 경우는 4이다.
3. A[i-1]과 A[j]를 Swap한다.
→ i-1인 2번째 숫자 3과 j인 5번째 숫자 4를 변경한다. A 배열은 다음과 같이 변경된다.
A={7, 2, 4, 6, 5, 3, 1}
4. i이후의 순열을 모두 뒤집는다.
→ 최초 순열 상태로 만들어야 하므로 i번째부터는 오름차순으로 만들어야 한다. A 배열은 다음과 같이 변경된다.
A={7, 2, 4, 1, 3, 5, 6}
위 로직의 시간복잡도는 어떨까? 전체 N개의 숫자에 대해 각각 순열을 구하는 문제가 된다. 제일 좌측에 숫자 N개가 올 수 있고 각 것마다 (N-1)!개의 순열이 있기 때문에 시간복잡도는 O(N x (N-1)!)이라서 O(N!)이 된다.
N!은 굉장히 높은 시간 복잡도를 갖는다. N=10이면 되어도 약 360만 번의 연산이 수행되며 N=11이 되면 4억 번의 연산이 필요하다. 따라서 이 방법은 항상 사용할 수는 없고, 문제에서 주어진 N의 크기를 고려해야 한다.
위와 같은 방법으로 이전 / 다음 순열을 구하는 문제를 해결할 수 있다. 관련 문제는 완전 탐색 / 순열을 Tag로 작성한다.
c++, Python은 순열 관련 라이브러리가 있는데, 자바는 없으니 직접 구현해야 한다.
다음 순열을 구하는 코드
import java.io.*;
public class Main{
static int[] perm;
static int n = 4;
public static void main(String[] args) throws IOException{
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
perm = new int[]{1, 2, 3, 4};
while(get_next_perm()){
for(int num : perm){
bw.write(String.valueOf(num) + " ");
}
bw.write("\n");
}
bw.flush();
}
private static boolean get_next_perm(){
int i = n-1;
// 뒤에서부터 체크하여 현재 위치가 뒤에서부터 오름차순이 아닌 경우를 찾음
// 뒤에서부터 오름차순이라는 것은 사전 순으로 최종 수열이라는 의미임
while(i > 0 && perm[i-1] >= perm[i]) i--;
// 이미 자체적으로 최종 순열이라면, false를 반환
if(i <= 0) return false;
// j는 현재 i-1위치에서 시작.
// i-1 이후의 모든 숫자 중 큰 것을 고르는데 그 중, j의 값이 가장 큰 경우로 선택
int j = i-1;
while(j < n-1 && perm[j+1] > perm[i-1]) j++;
// j와 i-1번째의 숫자를 swap
swap(i-1, j);
// i번째부터 이후의 모든 숫자를 뒤집음
// i~n-1 사이의 숫자를 상호 뒤집어야 하므로 j 값을 n-1로 초기화
j = n-1;
while(i < j){
swap(i, j);
i+=1; j-=1;
}
return true;
}
private static void swap(int i, int j){
int temp = perm[i];
perm[i] = perm[j];
perm[j] = temp;
}
}
③ 재귀(Recursive)
재귀는 말 그대로 자기 자신을 호출한다는 의미이다. 왜 자기 자신을 호출할 필요가 있을까?
예를 들어, 총 4개의 숫자 중에 2개를 선택하는 경우를 모두 출력한다고 가정해보자. 1~4까지 숫자가 있고 2개를 중복 없이 선택하는 모든 경우의 수를 출력하고자 한다고 가정하자.
이를 반복문으로 표현한다면 다음과 같을 것이다.
for i from 1 to 4..
chose i
for j from i+1 to 4..
chose j
print i j
손 쉽게 2중 반복문으로 해결하였다. 그런데.. 만약 숫자 N개의 숫자 중 M개를 고르는 경우라고 할 때, N과 M이 매우 큰 숫자라면 어떨까? 반복문을 수백, 수천 개를 써 내려갈 수는 없다!
이를 재귀 함수를 활용한다면 자기 자신을 호출함으로써 다음 숫자를 선택할 수 있도록 이동시켜 전체 코드를 매우 짧게 줄일 수 있다!
아래와 같이, 1~100의 숫자 중, 5개를 선택하는 경우를 코드로 작성해보자.
public class Main{
static int lim = 100; // 1~100까지의 제한
static int n = 5; // 5개만 고른다.
public static void main(String[] args){
int[] chosen = new int[n]; // 선택된 숫자가 저장되는 배열
// 시작은 0부터 시작하며 0개를 현재 선택했으니 아래와 같이 parameter 전달!
solve(chosen, 0, 0);
}
// chosen은 선택된 숫자가 저장된 배열
// curr은 현재 숫자를 선택하는 index
// cnt는 몇 개의 숫자가 선택되었는지 확인
private static void solve(int[] chosen, int curr, int cnt){
// n개의 숫자를 다 선택했다면 출력 후 더 이상 재귀를 돌지 않아야 한다!
// 탈출 조건의 정의!
if(cnt == n){
for(int i : chosen){
System.out.print(i + " ");
}
System.out.println();
return;
}
// 반복문을 통해 숫자를 계속 선택!
for(int i=curr+1; i <= lim; i++){
// 현재 선택된 숫자를 저장
chosen[cnt] = i;
// 다음 숫자를 선택하기 위해 재귀 호출
solve(chosen, curr, cnt+1);
}
}
}
여기서 중요한 점!
⑴ 재귀를 탈출하기 위한 탈출 조건이 필요!
▶ 이것이 없으면 n개를 모두 골랐음에도 더 숫자를 선택하고자 하여 선택된 숫자를 저장하는 배열에 범위 초과 오류가 나거나, 다른 자료구조를 쓴 경우 잘못된 출력이 나올 수 있고, 혹은 무한 루프가 발생할 수 있다!
⑵ 현재 함수의 상태를 저장하는 Parameter가 필요!
▶ 위에서 우리는 curr, cnt를 통해 어떤 숫자까지 선택했는지, 몇 개를 선택했는지 전달하였다. 이것이 없다면 현재 함수의 상태를 저장할 수 없어 재귀 탈출 조건을 만들 수 없게 되거나 잘못된 결과를 출력하게 된다!
⑶ Return문을 신경 쓸 것!
▶ 위의 함수는 단순 출력이기에 void로 함수를 작성했다. 그런데, 재귀를 통해 이후의 연산 결과를 반환 후 이전 결과에 추가 연산을 수행하는 경우도 있을 수 있다. 즉, 문제 해결을 위한 정확한 정의를 수행하여야 이것을 완벽히 풀 수 있다.
잘 생각해보면 Dynamic Programming과도 매우 흡사해 보인다. 그 또한 Top-Down을 사용 시 재귀를 통해 수행하는데, 기저 사례를 통해 탈출 조건을 만들고, 현재 함수의 상태를 전달하는 Parameter를 전달한다.
또한 Return을 통해 필요한 값을 반환하여 정답을 구하는 연산 시에 사용하게 된다.
완전 탐색의 재귀와 DP의 차이점은, DP는 작은 문제가 큰 문제와 동일한 구조를 가져 큰 문제의 답을 구할 시에 작은 문제의 결과를 기억한 뒤 그대로 사용하여 수행 속도를 빠르게 한다는 것이다.
그에 반해 완전 탐색은 크고 작은 문제의 구조가 다를 수 있고, 이전 결과를 반드시 기억하는 것이 아니라 해결 가능한 방법을 모두 탐색한다는 차이가 있다.
(즉, DP는 일반적인 재귀 중 조건을 만족하는 경우에 적용 가능!)
이에 대한 더 자세한 내용은 DP 관련 포스팅(여기)를 참조
④ 비트마스크(Bitmask)
비트마스크란 비트(bit) 연산을 통해서 부분 집합을 표현하는 방법을 의미한다.
비트 연산이란 다음과 같은 것들이 있다.
And 연산(&) : 둘 다 1이면 1
OR 연산(|) : 둘 중 1개만 1이면 1
NOT 연산(~) : 1이면 0, 0이면 1
XOR 연산(^) : 둘의 관계가 다르면 1, 같으면 0
Shift 연산(<<, >>) : A << B라고 한다면 A를 좌측으로 B 비트만큼 미는 것이다.
좀 더 쉽게 표로 알아보자. A, B라는 변수값이 있다고 할 때, 각각의 비트 연산결과를 표로 정리하였다.(Shift 연산은 아래에 별도로 정리함)
| 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 |
그런데 우리는 1, 0만을 사용할 것이 아니라 각 모든 숫자를 비트 연산할 수 있어야 한다. 모든 숫자는 2진수로 표현될 수 있기 때문에 2진수를 통해 비트연산을 수행할 수 있다.
만약, 13과 72를 2진수로 나타낸다면 어떨까? 다음과 같을 것이다.
$13 = 1101_{(2)}$
$72 = 1001000_{(2)}$
그러면 13의 경우에는 부족한 앞의 3자리를 0으로 채우고 비트연산을 수행할 수 있다. 그 결과는 다음과 같다.
비트 연산의 시간복잡도는 내부적으로 상수 시간 정도로 처리가 되어 O(1)이라고 보면 된다.(그렇다고 프로그래밍 시 산술 연산을 비트 연산으로 모두 바꾸는 것은 오히려 비효율적. 유지보수에도 좋지 않고 실제로 미미한 차이만 나기 때문이다..)
NOT 연산 사용 시 주의할 점)
코딩 시, 숫자들을 저장할 수 있는 자료형은 1가지가 아니다. Java의 경우 byte, short, int, long 형으로 정수 형태의 자료를 저장할 수 있다.
이 때, byte는 8비트, short는 16비트, int는 32비트, long은 64비트이기 때문에 전체 저장할 수 있는 비트의 수가 다르므로 어떤 자료형에서 NOT연산을 하느냐에 따라 숫자 자체의 결과는 같더라도 비트마스크 결과는 다를 수 있다.
예를 들어 40을 byte, short, int 형으로 저장한 뒤 각각을 NOT연산도 수행해보고, 비트 출력 또한 수행해보자.
public class Main{
public static void main(String[] args){
byte b = 40;
short s = 40;
int i = 40;
// byte, short는 toBinaryString이 없어 Integer클래스의 함수를 빌려와서 연산한다.
// 0xFF는 8비트로 11111111이므로 & 연산을 통해 결과를 나타낼 수 있다.
String bs = String.format("%8s", Integer.toBinaryString(~b & 0xFF));
System.out.println("Byte 형 40 NOT 연산 : " + ~b + ", 2진수 출력 : " + bs);
// 0xFFFF는 16비트로 1111111111111111이므로 & 연산을 통해 결과를 나타낼 수 있다.
String ss = String.format("%16s", Integer.toBinaryString(~s & 0xFFFF)).replace(' ', '0');
System.out.println("Short 형 40 NOT 연산 : " + ~s + ", 2진수 출력 : " + ss);
System.out.println("Integer 형 40 NOT 연산 : " + ~i + ", 2진수 출력 : " + Integer.toBinaryString(~i));
}
}
/* 결과
Byte 형 40 NOT 연산 : -41, 2진수 출력 : 11010111
Short 형 40 NOT 연산 : -41, 2진수 출력 : 1111111111010111
Integer 형 40 NOT 연산 : -41, 2진수 출력 : 11111111111111111111111111010111
*/
위와 같이 숫자 자체는 같더라도 전체 비트 결과는 다르므로 주의해서 사용해야 한다. 만약 C++를 사용한다면 signed, unsigned 형까지 고려해서 연산을 수행해야 한다.
Shift 연산)
그럼 Shift 연산에 대해서도 알아보자. <<, >> 로 표현하며 해당 방향으로 원 비트를 특정 값만큼 밀어버린다는 개념으로 이해하면 된다.
예를 들어서 1 << 3 이라고 한다면 어떨까? 1은 이진수로 $1_{(2)}$ 인데, 이를 3칸 좌측으로 밀어버리므로 $1000_{(2)}$가 된다.
그렇다면 7 << 3이라고 한다면 7000이 되나? 아니다. 7을 2진수로 변환한다음 3칸 밀어야 한다. 즉, 7은 이진수로 $111_{(2)}$ 이므로 3칸 좌측으로 밀면 $111000_{(2)}$가 된다.
반대로 >> 는 우측으로 밀어버리는 것인데, 우측으로 밀어버리면 버려지는 것들은 어떻게 할까? 그냥 삭제되는 것이다.
예를 들어서 10 >> 2라고 한다면 10은 이진수로 $1010_{(2)}$ 이므로 2칸 밀면 $10_{(2)}$가 되는 것이다.
여기서 이해할 수 있는 것은, A << B를 한다면 A라는 이진수를 B칸씩 밀게 되는데, 그러면 모든 1의 값이 저장된 비트가 $2^B$씩 곱해지는 것이다.
그리고 A >> B는 A라는 이진수를 우측으로 B만큼 밀게 되니까 $2^B$만큼 나누어지게 된다. 따라서 다음과 같다.
$A << B = A*2^B$
$A >> B = A/2^B$
이를 통해 곱셈 / 나눗셈 산술 연산을 비트연산으로도 표현이 가능하다. 예) $(A+B) / 2 = (A+B) >> 1$
참고로, 비트 연산은 +, -보다 연산 우선 순위가 낮다. 헷갈리지 않게 코딩할 때는 () 연산자를 잘 써서 헷갈리지 않게 해주자.
비트 연산으로 집합을 나타내는 법)
비트마스크는 정수로 집합을 나타내는 것이 가능하다. 예를 들어 0~9 까지의 숫자로만 이루어지는 정수 집합이 있다고 할 때, 그 중 하나의 부분 집합이 A라고 하자. 그럼
A = {1, 3, 4, 5, 9} 라고 가정하면, 이를 570이라는 하나의 숫자로 나타낼 수 있다. 즉, A=570!
왜냐면, 아래와 같은 표를 보면 각각의 숫자가 있는 경우 1, 없는 경우 0으로 표시할 수 있기 때문이다.
| 숫자 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
| 비트 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 1 | 0 |
그러면, 저 비트를 하나의 이진수라고 본다면 $1000111010_{(2)}$와 같으므로 10진수로 해보면 570이 되기 때문이다. 이 정수로 사용하게 되면 전체 저장 공간 또한 절약이 되고 정수이기 때문에 index로도 활용이 가능하므로 매우 큰 장점이 있다.
이 비트마스크로 집합을 나타낼 때는 0~N-1까지 정수로 이루어진 집합을 나타낼 때 사용된다. 1~N까지로 하면 1개의 비트가 더 필요하여 전체 공간이 2배가 된다.(시간도 2배가 됨) 그래서 0~N-1까지로 활용(또한, 0이 없으면 연산을 더 변형해야 함.)
그러면 아래에서 비트 연산을 어떻게 활용하는지 알아보자.
① 집합 포함 여부 검사
0~9까지의 숫자 중 해당 숫자가 현재 집합에 포함되어 있는지를 알아보는 방법이다.
{1, 3, 4, 5, 9} = 570이라고 할 때, 0이 포함된 여부를 검사하려면 0번째 비트만 1로 만들고 나머지를 0으로 한 것과 570을 2진수로 만든 것을 AND(&) 연산 하면 있는지를 알 수 있다.
왜냐하면, &연산은 둘 다 1인 경우만 1이므로 0이 포함된 경우는 1로 표시되기 때문에 그 결과로 나온 위치의 비트가 1이라면 해당 수가 집합에 포함 여부를 알 수 있기 때문이다.
아래의 그림을 보자.
위의 연산과 같이, 0이 포함되었는지 확인할 수 있는 비트만 1로 놓고 나머지를 0으로 둔 다음 확인을 하면 된다.
아래의 코드를 통해 사용 방법을 확인할 수 있다.
public class Main{
static int[] set = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
static int sub_set = 570;
public static void main(String[] args){
// 현재 부분 집합에 0이 포함되었는지 검사
// 570 & 2^0 이므로 570 & (1 << 0) = 1이라면 있는 것, 0이면 없는 것
System.out.println((570 & (1 << 0)) == 1 ? "0 있음" : "0 없음" );
// 현재 부분 집합에 1이 포함되었는지 검사
// 570 & 2^1 이므로 570 & (1 << 1) = 2이라면 있는 것, 0이면 없는 것
System.out.println((570 & (1 << 1)) == 2 ? "1 있음" : "1 없음" );
// 현재 부분 집합에 2가 포함되었는지 검사
// 570 & 2^2 이므로 570 & (1 << 2) = 4이라면 있는 것, 0이면 없는 것
System.out.println((570 & (1 << 2)) == 4 ? "2 있음" : "2 없음" );
// 현재 부분 집합에 3이 포함되었는지 검사
// 570 & 2^3 이므로 570 & (1 << 3) = 8이라면 있는 것, 0이면 없는 것
System.out.println((570 & (1 << 3)) == 8 ? "3 있음" : "3 없음" );
System.out.println(check(4) ? "4 있음" : "4 없음" );
System.out.println(check(5) ? "5 있음" : "5 없음" );
System.out.println(check(6) ? "6 있음" : "6 없음" );
}
// 함수로 만든 경우
private static boolean check(int n){
boolean isExist = (sub_set & (1 << n)) == Math.pow(2, n) ? true : false;
return isExist;
}
}
/*
0 없음
1 있음
2 없음
3 있음
4 있음
5 있음
6 없음
*/
② 숫자 추가하기
위의 ①의 경우와 같이, 비트 연산을 통해 숫자를 추가할 수 있다. 특정 숫자를 추가하기 위해서는 해당 위치의 비트를 1로 만들어야 한다.
1도 만들기 위해서는 OR(|) 연산을 사용하면 된다. 추가하고자 하는 위치의 비트만 1로 만들고 나머지는 0으로 된 비트와 570을 2진수로 만든 비트를 OR 연산 시, 추가하고자 하는 비트 위치가 1로 변경되기 때문이다.
그림으로 알아보자. 만약 2를 추가하고자 한다면 아래와 같을 것이다.
코드로 알아보자.
public class Main{
static int[] set = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
static int sub_set = 570;
public static void main(String[] args){
// 2를 추가
add(2);
System.out.println(sub_set);
// 7을 추가
add(7);
System.out.println(sub_set);
System.out.println(check(2) ? "2 있음" : "2 없음" );
System.out.println(check(7) ? "7 있음" : "7 없음" );
}
// 현재 특정 숫자를 추가하는 함수
private static void add(int n){
sub_set = sub_set | (1 << n);
}
// 현재 특정 숫자가 부분 집합에 있는지 체크하는 함수
private static boolean check(int n){
boolean isExist = (sub_set & (1 << n)) == Math.pow(2, n) ? true : false;
return isExist;
}
}
/*
결과
574
702
2 있음
7 있음
*/
③ 특정 숫자 제거하기
특정 숫자를 제거하기 위해서는 NOT(~) 연산과 AND(&) 연산을 같이 쓰면 된다.
NOT(~) 연산으로 제거하고자 하는 위치의 비트만 0으로 하고 나머지는 1로 만든 다음 AND(&) 연산을 하면 해당 위치만 0으로 바뀌고 나머지는 그대로가 되기 때문이다.
그림으로 알아보자. 4를 빼고자 한다면 다음과 같을 것이다.
코드로 알아보자.
public class Main{
static int[] set = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
static int sub_set = 570;
public static void main(String[] args){
System.out.println(check(4) ? "4 있음" : "4 없음" );
// 4를 제거
delete(4);
System.out.println(check(4) ? "4 있음" : "4 없음" );
}
// 현재 특정 숫자를 제거하는 함수
private static void delete(int n){
sub_set = sub_set & ~(1 << n);
}
// 현재 특정 숫자가 부분 집합에 있는지 체크하는 함수
private static boolean check(int n){
boolean isExist = (sub_set & (1 << n)) == Math.pow(2, n) ? true : false;
return isExist;
}
}
/*
결과
4있음
4없음
*/
④ 토글 연산하기
0, 1을 왔다갔다 할 수 있게 하는 연산을 해보자. 만약 현재 있으면 없애고, 없으면 있게 하고자 한다면 어떨까?
즉, 0이면 1로 바꾸고, 1이면 0으로 바꾸고자 한다. 그러면 XOR(^) 연산을 수행하면 된다. XOR(^) 연산은 값이 다르면 1로 되며, 같으면 0이 되기 때문이다.
그림으로 알아보자. 3이라는 숫자를 토글하자면 다음과 같다.
코드로 구현한다면 다음과 같을 것이다.
public class Main{
static int[] set = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
static int sub_set = 570;
public static void main(String[] args){
System.out.println(check(4) ? "4 있음" : "4 없음" );
// 4를 토글
toggle(4);
System.out.println(check(4) ? "4 있음" : "4 없음" );
}
// 현재 숫자 토글하기
private static void toggle(int n){
sub_set = sub_set ^ (1 << n);
}
// 현재 특정 숫자가 부분 집합에 있는지 체크하는 함수
private static boolean check(int n){
boolean isExist = (sub_set & (1 << n)) == Math.pow(2, n) ? true : false;
return isExist;
}
}
/*
결과
4있음
4없음
*/
⑤ 전체 집합, 공집합 표현하기
전체 집합은 모든 숫자가 1이라는 것이므로, N개의 비트가 모두 1이라는 의미이다. 따라서 전체 집합을 표시하는 방법은 다음과 같다.
0부터 시작하므로 좌측으로 N번 이동한 뒤 1을 빼면 된다.
전체 집합 : (1 << N) - 1
공집합은 그냥 0으로 표시하면 된다.
이제 위 방법을 응용하여 비트마스크를 이용한 완전 탐색 문제를 해결해볼 수 있다. 비트마스크는 보통 처리할 전체 데이터가 정해져 있고 그 안에서 특정 개수를 가지고 연산을 수행할 때 사용한다.
보통 재귀로도 풀 수 있는데 비트마스크를 이용해서도 해결이 가능하다.
⑤ BFS, DFS 사용하기
이는 그래프 자료 구조에서 모든 정점을 탐색하기 위한 방법이다.
BFS는 너비 우선 탐색으로 현재 정점과 인접한 정점을 우선으로 탐색하고 DFS는 깊이 우선 탐색으로 현재 인접한 정점을 탐색 후 그 다음 인접한 정점을 탐색하여 끝까지 탐색하는 방식이다.
이 내용은 그래프 관련 포스팅(여기)과 BFS 포스팅(여기), DFS 포스팅(여기)를 참고
위의 방법들 중 상황에 따라 이용 가능한 방법을 활용하여 문제를 해결할 수 있는지 테스트하고 실제 답을 구해보는 훈련을 통해 문제 해결 역량을 기를 수 있다.
이후 해당 문제 관련 해결 내역은 완전탐색 태그를 추가하여 글을 포스팅 합니다.
'자바 프로그래밍 > 알고리즘(Algorithm)' 카테고리의 다른 글
| 알고리즘 - 그리디 알고리즘(Greedy Algorithm) (1) | 2021.04.07 |
|---|---|
| 알고리즘 - 백트래킹(Backtracking) (2) | 2021.02.03 |
| 알고리즘 - LIS(가장 긴 증가하는 부분 수열) (0) | 2021.01.10 |
| 알고리즘 - Dynamic Programming(동적 계획법) (34) | 2021.01.05 |
| 알고리즘 - 진법 변환하기(10진수 - N진수) (2) | 2020.12.29 |
