레퍼런스/분석 검색 결과

해당 글 54건
왜 java에서는 equals 메서드를 오버라이드 하면 hashCode 도 같이 해야 할까요?

이 포스트를 이해하기 위해서는, Hash 자료구조에 대한 이해가 선행되어야 합니다. 만약에 이에 대한 이해가 없다면, 이 포스팅을 보고 오시는 것을 강력하게 권해드립니다. 흔히 많은 책에서 equals를 오버라이딩 하면, hashCode를 같이 오버라이딩을 하라고 합니다. 왜 그런지 천천히 알아보도록 하겠습니다. Dog 클래스입니다. 오늘은 이 클래스만 보고 이야기를 해 보도록 하겠습니다. 먼저 hashSet에 item을 하나 넣었다고 가정해 봅시다. 그러면 HashSet의 add 메서드가 hashMap의 put 메서드를 호출합니다. put은 putVal 메서드를 호출하는데요. 이 때, 1번째 인자로 hash(key)를 넣습니다. 이 함수의 내부를 봅시다. hashSet에 add한 key 객체가 hash..
레퍼런스/분석 2019. 12. 15. 16:41
인트로 정렬 : c++의 sort는 왜 최악의 경우에도 빠르게 동작하는가?

C++의 sort는 어떻게 O(nlogn)의 복잡도가 보장될 수 있을까요? 저번에 compare 함수가 항상 True를 리턴할 때에 어떤 일이 일어나는가? 편에서 이 함수를 뜯은 적이 있었습니다. 그 기억을 되살려서 보도록 하겠습니다. Quick sort는 pivot을 어떻게 선택하느냐가 중요하다고 했어요. 저번에 median 값을 가지고 pivot값을 생성한다는 것을 알 수 있는데요. 이 방법을 저격하는 데이터가 있다는 것이 알려져 있어요. 그러면 이 방법을 어떻게 해결할까요? nth_element에도 적용되는 기법 중 하나인데요. 호출 깊이의 제한을 둡니다. first와 last가 다른 경우, __introsort_loop를 호출합니다. 그런데, 이것은, 3번째 인자에 이상한 __lg(__last -..
레퍼런스/분석 2019. 12. 7. 21:25
c++ unique 함수 : 정렬을 먼저 해야 중복이 제거된다.

좌표 압축이라는 기술이 있다고 들었습니다. 물론, 저는 ps를 하지 않아서 잘 모르겠습니다. 좌표 압축을 위해서, 중복을 제거해야 하는데요. 그 때 많이 쓰는 함수가 sort + unique + erase 조합입니다. 아마도 그러리라 생각이 듭니다. 물론 set, map도 됩니다만. 이것은 제 전문이 아니니 논외로 하겠습니다. 이 중, unique가 어떻게 동작하는지 이해해 보도록 하겠습니다. cpp reference 코드에 나온 코드는 아래와 같습니다. 아. 보기만 해도 힘드네요. 일단, result, first, last 세 개가 있습니다. 이 셋을 기준으로 보도록 하겠습니다. 보통 unique를 쓰실 때, unique(v.begin(),v.end()) 이런 식으로 쓰실 거니, last는 자료구조의 ..
레퍼런스/분석 2019. 11. 28. 18:36
c++ sort 의 비교함수가 true만 리턴할 때 어떤 일이 일어날까요?

안녕하세요. chogahui05입니다. sort 함수의 비교 함수를 작성하실 때, strict weak ordering을 만족하게 작성하여야 한다는 말을 많이 들으셨을 거에요. 그렇게 작성하지 않으면 어떻게 될까요? 라는 질문은 사실 별로 의미가 없어 보입니다. 비교 함수가 무조건 true를 리턴하게 작성이 되었을 때 어떤 일이 일어날까요? 너무 멍청한 코딩인가요? 처음 비교함수를 작성하실 때, 이런 식으로 코딩하시지 않으셨나요? 위와 같이 작성이 되었을 때, 어떤 일이 일어날까요? 사실 배열에 들어간 데이터들을 보았을 때, 이 경우도 무조건 compare 함수가 true를 리턴하게 되어 있어요. 똑같은 상황인 셈입니다. se.cpp입니다. 이 프로그램의 내용을 봅시다. 이 경우에 프로그램이 어떻게 실행..
레퍼런스/분석 2019. 11. 12. 19:06
c++ string c_str 함수 : string을 char *로 바꿔봅시다.

string의 c_str 함수는 제가 string을 C style의 문자열로 바꿀 때 많이 썼던 함수입니다. 이 메서드는 const char *를 리턴합니다. 내용이 변경되면 안 되는 제약 조건을 가진, char형 포인터를 리턴합니다. 일단, string의 구조에 대해서 간략하게 설명을 하고, c_str()에 대한 설명을 하도록 하겠습니다. Stri uffer, StringBuilder, C++의 String 등이 있습니다. C++의 스트링 클래스에는 capacity와 size가 있는데요. 이는 동적 배열이 있는 Class는 보통 이 두 메서드를 구현을 많이 하는 편입니다. append 100만번 하면 시간이 오래 걸리는지 안 걸리는지 체크만 해도 되고요. 실제로 내부 구조를 보면, string 클래스 ..
레퍼런스/분석 2019. 11. 11. 01:25