Algorithm/Algorithm

유니온-파인드(Union-Find)? Union-Find는 여러 개의 노드가 존재할 때, 어떤 두 노드가 같은 그래프에 속하는지 판별하는 알고리즘이다. 방법 같은 그래프에 속하는지 어떻게 판별할까? 다음 그림을 보고 쉽게 이해하자 먼저 8개의 노드가 위와 같이 있다고 가정한다. 각 노드는 자기 자신을 가리키며 이는 자기 자신이 곧 루트 노드임을 의미한다. 여기서 5와 2가 연결되었다고 해보자. 그럼 다음과 같이 표현할 수 있다. 5번 노드에 2번 노드를 가리키는 값 2가 들어간다. 일반적으로 합칠 때는 더 작은쪽으로 합치며 이를 Union이라 한다. 그 다음 2와 1이 연결되었다고 해보자. 2번 노드는 1번 노드를 가리키며 이를 의미하는 값 1이 들어간다. 그럼 여기서 5번과 1번이 같은 그래프에 속하는..

백트래킹? 백트래킹은 해를 찾는 도중 해가 아니어서 막히면 되돌아가서 다시 해를 찾아가는 기법을 말한다. 최적화 문제와 결정 문제를 푸는 방법이 된다. 모든 경우의 수를 전부 고려하는 알고리즘 상태공간을 트리로 나타낼 수 있을 때 적합한 방식이다. 일종의 트리 탐색 알고리즘이라고 봐도 된다. 방식에 따라서 깊이우선탐색(DFS)과 너비우선탐색(BFS), 최선 우선 탐색(Best First Search/HeuristicSearch)이 있다. 모든 경우의 수를 고려해야 하는 문제라면, DFS가 낫다. BFS로도 구현이 물론 가능하지만, BFS는 큐의 크기가 매우 커질 수 있고 속도도 차이가 없기 때문에 경우의 수 구하기는 일반적으로 DFS가 편리하다. 출처: 나무위키 DFS & 백트래킹 백트래킹은 DFS를 사..

비트마스킹? 컴퓨터는 내부적으로 모든 자료를 이진수로 표현한다. 이와 같은 특성을 이용해 정수의 이진수 표현을 자료구조로 쓰는 기법을 비트 마스크라고 한다. 비트 마스크를 이용하면 더 빠른 수행시간, 간결한 코드, 적은 메모리 사용의 효과를 얻을 수 있다. 비트 연산자 a & b: AND 연산 a | b: OR 연산 a ^ b: XOR 연산 ~a: NOT 연산 a > b: a를 b비트 만큼 오른쪽으로 시프트 집합 표현 비트마스크를 이용하면 집합을 쉽게 표현할 수 있다. 원소 추가 현재 상태 cur이 있을 때, p번째에 원소를 추가한다고 하면 다음과 같다 cur = cur | (1