전체 글 검색 결과

해당 글 904건
java에서 STL의 multimap 구조를 구현해 봅시다.

C++의 STL에서 multimap은 상당히 유용하게 쓰입니다. Java에서는 그렇게 쓸 수 없을까요? 저는 Key값이 중복되는 경우에도, Map 계열에 저장하고 싶습니다. 어떻게 하면 좋을까요? 그 전에 Java의 Map 계열이 어떻게 동작하는지 간단하게 정리하고 가겠습니다. map.find(K)를 호출했을 때 개략적인 흐름을 보겠습니다. 먼저, map 계열이 키가 K인 값을 찾는 구조입니다. 그러면, 자료구조에서 Key가 K인 것을 찾는데, 이 작업을 하기 위해 내부적으로 호출되는 메서드가 equals입니다. put(K,V')가 호출되었을 때, Key가 K인 것이 존재했다면, 데이터 를 가 같이 저장될 수 없습니다. 예를 들어, K가 가수이고, V가 발매한 앨범이라고 해 보겠습니다. Key dupli..
자료알고/자료구조 2020. 6. 24. 02:12
mysql inet_ntoa inet_aton 함수 : ipv4 주소를 어떻게 다룰까요?

ip 주소를 sql에서 다루어야 할 일이 있습니다. 오늘은, ip address를 unsigned integer로 바꾸는 함수와 unsigned integer를 다시 ip addr로 바꾸는 함수를 알아보도록 하겠습니다. 당연하게도, ipv4인 경우이고요. ipv6인 경우는 따로 있습니다. inet_aton과 inet_ntoa는 크게 어렵지 않습니다. 단순하게 해석해 봅시다. a는 Address의 약자일 겁니다. 그리고 n은 Number일 거고요. 중간에 to는 AtoB할 때 그 to가 맞습니다. 즉, A에서 N으로 변환하는 함수가 aton이고, N에서 A로 변환하는 함수가 ntoa인 셈입니다. ipv4 시스템에서, 255.255.255.255까지 나올 수 있습니다. 이 값을 numeric address로..
코딩/Sql 2020. 6. 22. 00:21
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
marking 배열과 sparse array

1달 2주 정도만에 자료구조 포스팅으로 돌아왔습니다. 와아아~. 생각난 김에, 안드로이드의 sparse Array에 대한 이야기를 해 보도록 하겠습니다. 당장 android의 스파스 어레이를 구글에 검색해 보시면 HashMap 하고 비교하는 글도 많아요. 거기서 빠질 수 없는 주제는 성능 비교일 텐데요. 퍼포먼스 이야기는 여기서 굳이 하지 않겠습니다. 이 포스팅을 보신 다음에, 추가적인 질문을 통해서 생각을 해 보도록 합시다. sparse는, 분포된 정도가 적은, 희박한이라는 뜻을 가집니다. 이것이 array의 수식어가 되면 어떨까요? 희소 배열. 즉, 전체에서, 정말 중요한 몇 % 정도만 저장하고 있는 구조 정도로 생각하시면 됩니다. 그런데, 사실 수식어가 걸리는 대상이 더 중요합니다. 여기서, 걸리는..
자료알고/자료구조 2020. 6. 19. 00:34
lis 알고리즘 : lower_bound 이용해서 그리디하게 해결해 봅시다.

lis 알고리즘은, 최장 증가 수열을 구하는 알고리즘입니다. 길이가 n인 수열이 있을 때, 이것을 O(nlogn)에 구할 수 있는 방법은 일종의 그리디를 이용한 것입니다. 물론, 조금 더 어려운 응용 문제를 풀기 위해서는 세그먼트 트리라는 자료구조를 알아야 하지만, 여기에서는 논외로 하도록 하겠습니다. 먼저 전체 소스 코드를 보겠습니다. res는 최장 증가 수열의 길이를 구하기 위한 벡터입니다. v는 문제에 주어진 수열입니다. 문제에 주어진 수열 전체를 돌면서, 먼저 lo 값을 구하고 있습니다. 이 lo 값은 res에서 v[i]보다 크거나 같은 최초의 위치를 찾습니다. 그 위치가 res의 크기와 같다면, res의 뒤에 추가합니다. 그렇지 않다면, res[lo]값에 v[i]를 갱신합니다. 일단 전체 시간 ..
자료알고/알고리즘 2020. 6. 17. 02:19