본문 바로가기

전체 글85

백트래킹 목표를 찾아가는 도중에 어떤 노드에서 출발하는 경로가 해가 될 것 같지 않으면 그 경로를 따라가지 않고 되돌아감으로써 시도 횟수를 줄인다. 이를 가지치기(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.
SW 역량테스트 B형 준비 삼성 SW 역량테스트 B형은 Pro 등급이라고도 하며 A형보다 최적화에 더욱 초점을 둔 시험이라고 한다. SW Expert Academy 사이트에 가보면 A형은 라이브러리에 제한이 없는데 반해, B형은 라이브러리를 사용하지 못한다고 써있다. 모두 구현을 해야한다는 것인데 그런 만큼 기본을 더 충실히 다지고 가야겠다. 인터넷에서 찾아보니 자주 사용되는 자료구조를 확인할 수 있었다. 우선 LinkedList, Hash, Queue, Stack, Graph, MergeSort, DFS/BFS, Trie, KMP, Segment Tree, Indexed Tree, Heap Sort 비트 마스킹, 자료 압축 등등이 있는 것 같다. 이 모두를 남은 기간동안 충분히 활용할 수 있도록 공부하는 것이 당면의 목표인데.... 2023. 3. 23.

티스토리툴바