비트연산 검색 결과

해당 글 3건
ip 주소의 netmask는 무엇일까요?

오늘 따라 덥군요. ifconfig 명령어를 치면, 여러 가지 정보들이 나옵니다. 이 중에서, netmask를 알아보도록 하겠습니다. ifconfig 명령어를 쳐 보겠습니다. 우분투에서는, 이 명령어를 치면, 추가적인 패키지를 깔아야 할 겁니다. inet, netmask, broadcast가 보이는데요. 이 중에서 netmask는 대체 어디에 쓰이는 것일까요? 일단, 255. 255. 255. 0을 3자리씩 끊어서 2진수로 바꿔 보도록 하겠습니다. 대충 이렇게 되겠군요. 다음에 192.168.213.128을 3자리씩 끊어서 2진수로 바꿔 보도록 하겠습니다. 이 친구는 hostname -I 명령어를 입력했을 때, 나온 값이기도 하였습니다. 그러면 11000000. 10101000. 11010101. 100..
네트워크 2020. 6. 21. 19:28
비트 배열 : 공간을 1/8, 1/32, 1/64로 압축한다.

제목이 꽤 도발적인 거 같네요. ps를 하시다 보면 종종 듣는 이야기 중 하나는, 상수 최적화, 혹은 O(n/32)나 O(n/64)입니다. 그것이 공간이 될 수도 있고, 시간이 될 수도 있는데요. 32와 64. 무언가와 연관이 있는 듯 싶습니다. 환경에 따라 다르겠지만, 보통 우리가 흔히 알고 있는 int형, long long형의 bit 수이기도 합니다. 공간을 n/32나, n/64로 compress 하는 문제를 생각해 봅시다. 사실, trie나 set, map을 쓰셔도 됩니다. 그런데 STL을 직접 구현해야 하는 경우, 2번째 것과 3번째 것은 구현하는 데, 상당히 어렵습니다. 1번은 시도해 볼 만 합니다. 그런데 메모리 제한이 128M로 꽤 넉넉하다면 어떨까요? 이 때는 이야기가 달라질 수도 있습니다..
자료알고/자료구조 2019. 12. 24. 05:39
외판원 문제 : 팩토리얼을 지수 복잡도로 낮춰보자

우리가 흔히 말하는 TSP, 외판원 문제는, 어떠한 도시에서 출발해서, 모든 도시를 방문하고 다시 출발점으로 돌아왔을 때, 최단 경로의 길이를 구하는 문제입니다. 이것을 단순하게, 모든 경우를 따져가면서 푼다면 n! 의 가짓수를 모두 따져야 할 겁니다. n이 12만 되어도 4억이 넘어갑니다. 이렇게 비효율적인, 팩토리얼급을 어떻게 지수급으로 낮추느냐가 핵심인데요. 중복된 상태를 memoi 하는 방법으로, O(n^2*2^n)으로 줄일 수 있습니다. dp를 다음과 같이 정의합시다. 시작점과 끝점은 0이라고 가정합시다. dp[state][s] : 현재 s에 있고, state 상태일 때 최단 거리. 그러면, 이 state가 무엇인지 궁금하실 텐데요. s에서 출발하였을 때, 방문한 도시들의 집합을 나타낸 겁니다...
자료알고/알고리즘 2019. 6. 27. 04:21