bitmask3 [leetcode][260] Single Number III 문제 : https://leetcode.com/problems/single-number-iii/ 2개의 요소는 단 하나만 존재하고 이 외의 요소들은 두 개씩 있는 nums 배열이 주어진다. 하나만 존재하는 2개 요소를 찾아라. (요소의 순서는 상관없다. 선형 시간복잡도로 구현하라.) nums 배열을 탐색하면서 모든 요소들의 XOR 연산 결과를 sum 변수에 저장한다. XOR 연산은 홀수번 나온 비트는 1, 짝수번(0포함) 나온 비트는 0으로 세팅된다. 즉, XOR연산 결과는 1개만 존재하는 수의 XOR 결과와 같다. (나머지 수들은 2번 XOR 연산되므로 A XOR A = 0. 이 되므로 무시해도 된다.) 하나만 존재하는 요소를 각각 A, B라고 했을 때, A는 B와 같지 않으므로 A XOR B = 0 .. 2020. 7. 24. brian kernighan's algorithm 2진법 수에서 1의 수(cnt) 를 세는 알고리즘. N = 11010(2) 에서 1의 수를 세보자. 일단 N - 1을 구한다. N - 1 = 11001(2) N, (N - 1)을 AND 연산한다. N & (N - 1) = 11000(2) 연산 결과는 N에서 뒤에서부터 가장 처음나오는 1 비트를 삭제한 결과와 같다. 1비트가 하나 있어서 삭제되었으므로 cnt + 1을 해준다. 이를 N이 0보다 큰경우 반복한다. (N이 0보다 큰 경우 1이 반드시 한 개 있다는 의미이므로) #include using namespace std; int main() { int N; cin >> N; int cnt = 0; while (N > 0) { N &= (N - 1); cnt++; } cout 2020. 7. 24. 외판원 순회(TSP: Traveling Salesperson Problem) 외판원 순회(TSP: Traveling Salesperson Problem)란 도시들이 있고 특정 도시에서 도시로 이동할 때 드는 비용이 주어졌을 때 불특정한 도시에서 출발해서 모든 도시를 돌고 다시 출발 도시로 돌아왔을 때 드는 최소 비용을 구하는 문제입니다. 외판원 순회는 NP문제로 이번에 소개할 알고리즘은 N이 16개 이하일 때 DP와 비트마스크를 이용하여 구하는 방법입니다. DP는 특정 도시들을 방문한 상태일 때 최소 비용을 저장해 놓고 이를 사용합니다. 비트마스크는 특정 도시를 방문한 상태를 저장할 때 사용합니다. 예를 들어서 1~3번 도시가 있다고 했을 때, 110(2)는 2,3번 도시를 방문한 상태입니다. 110(2)를 십진수로 바꿔보면 6(1x22 + 1x21 + 0x20)이 됩니다. 즉,.. 2019. 8. 31. 이전 1 다음
