본문 바로가기

알고리즘26

백트래킹 목표를 찾아가는 도중에 어떤 노드에서 출발하는 경로가 해가 될 것 같지 않으면 그 경로를 따라가지 않고 되돌아감으로써 시도 횟수를 줄인다. 이를 가지치기(Pruning)이라고 하는데, 불필요한 부분의 연산을 줄이는 것이다. 깊이 우선 탐색과 비교했을 때, 깊이 우선 탐색은 모든 경로를 추적하는데 반해, 백트래킹은 불필요한 경로를 조기에 차단하기 때문에 경우의 수가 상대적으로 많이 줄어든다. 하지만 N!의 경우의 수를 가진 문제에서는 여전히 최악의 경우 지수함수 시간을 필요로 하기 때문에 처리가 불가능하다. 따라서 가지치기를 잘하는 것에 따라 효율이 결정된다. 쉽게 말하자면 특정한 조건을 만족하는 경우만 고려하고, 그렇지 않은 경우 과감하게 쳐낸다는 뜻이다. 이는 다양한 탐색에서 조건을 걸어 답이 도출되기.. 2023. 3. 24.
비트 마스크(Bit Mask) - 활용(순열) 저번에는 비트마스크로 부분집합을 도출하는 것을 알아보았다. 이번에는 순열이다. 순열은 같은 숫자들을 뽑아도 뽑는 순서에 따라 해당 집합이 가지는 가치가 다르다는 걸 전제로 한다. 즉 1 2 와 2 1은 같은 숫자를 뽑았지만 뽑은 순서가 다르기 때문에 서로 다르다고 본다. 이를 비트마스크를 통해 구현해보자. #include using namespace std; int *arr; int n; int *result; void cal(int idx, int v) { if (idx == n) { for (int i = 0; i < n; i++) { cout 2023. 3. 24.
비트 마스크(Bit Mask) - 활용(부분집합) 지난 번에 이어서 마저 작성하려고 한다. 비트 연산을 통해 다양한 연산을 빠르게 실행할 수 있는데, 부분집합을 찾는 것도 그 중 하나이다. 0에서 3까지 4개의 요소가 들어가 있는 집합에서 모든 부분 집합을 뽑아낼 수 있는 경우를 비트 마스킹을 통해 찾아보자. 우선 코드는 다음과 같다. #include using namespace std; int main() { int n = 4; char arr[4] = { 'a','b','c','d' }; for (int i = 0; i < (1 2023. 3. 24.
비트 마스크(Bit Mask) - 활용(집합 연산) 지난 번에는 비트 마스크의 기본인 비트 연산자를 간단하게 알아보았다. 그렇다면 이번에는 비트 마스크를 활용하는 예를 알아보는 게 좋지 않을까? 비트마스크의 가장 대표적인 활용은 바로 집합에서 이뤄진다. 비트 마스크 기법을 활용하면 집합의 공집합, 원소 추가, 삭제, 포함 여부, 합집합, 교집합 등등 다양한 연산을 간단하게 실행할 수 있다. 1. 공집합과 꽉 찬 집합 위와 같이 공집합인 경우 그냥 0인 상태이고, 풀집합일 경우 1을 시프트 연산으로 한 자리 수 더 크게 만든 다음 1을 빼면 해당 집합 크기에 모든 값이 1인 비트 값을 만들어 낼 수 있고, 이는 꽉 찬 집합과 같은 비트 값이다. 이렇게 간단히 비트 마스킹을 통해 공집합과 꽉 찬 집합을 확인할 수 있다. 2. 원소 추가, 삭제 추가의 경우 |.. 2023. 3. 22.

티스토리툴바