레퍼런스 사이트에서 보면, unordered_map의 insert나 delete나 find 함수는 평균적으로 O(1)이라고 나와 있습니다. 그런데, 최악의 경우, O(n)이라고 나와 있습니다. [관련글] 해쉬 테이블의 평균 복잡도를 분석해 봅시다. 왜 최악의 경우에 O(n)일까요? 이유는 간단합니다. Chaining 방식이 List이기 때문입니다. 그러면, 왜 최악의 경우에 선형 시간이 걸리는지는 해결이 된 셈입니다. 하나의 버킷에 좌르르륵 skew가 되어 있으면 List의 경우에는 계속 찾아야만 하니까 O(n)이 걸립니다. 그런데, 아무리 최악의 경우가 O(n)이라고 한다면, 저격 데이터를 만드는 게 굉장히 어렵다면 사실 그냥 써도 무난할 겁니다만. 생각보다 충돌이 극단적으로 일어나는 데이터를 만드는 ..
레퍼런스/분석 검색 결과
String의 indexOf는 어떤 식으로 동작할까요? indexOf를 호출하면, 내부에서, 인자를 7개를 받는 함수가 호출이 되는데요. 1번째 source는 어떠한 문자열에서 찾을 것인지, target은 패턴을 의미합니다. 예를 들어서, "abababb"에서 "ab"를 찾는다고 한다면, "abababb"는 source가 되고, target은 "ab"가 됩니다. fromIndex는, string의 어느 위치부터 탐색을 할 것인지에 대한 정보를 담고 있는데요. 예를 들어서 string이 "abcde"라고 하고, 1번째 위치부터 탐색한다면 fromIndex는 1이 됩니다. 아래 코드들을 봅시다. 뭔가 조금 복잡해 보이는데요. fromindex가, string에서 어느 위치부터 탐색을 시작할 것인지를 나타냅니..
코딩 테스트에서 next_permutation의 사용 빈도는 상당히 높을 겁니다. 특히 역량 테스트라고 불리는 것에서는요. 구현이 들어가면 대략 50% 정도는 조합, 순열 등에서 나오는데요. 그 때, 이전 순열이라던지 다음 순열을 구하기 위해서 쓰는 함수가 저 함수입니다. 이전 순열은 데이터를 조금 변형을 하면 구할 수 있고요. 그러면 이 함수가 어떻게 구현이 되어 있을까요? 만약에 레퍼런스 없이 구현하라고 하면 어떻게 해야 할까요? 단계별로 이해해 봅시다. 사실 이 함수의 복잡도는 O(n)입니다. 왜 그렇게 나올 수가 있는 것인지, 상대적으로 비효율적인 구현 방법으로 먼저 구현해 보고 이야기 하도록 하겠습니다. O(n^2)의 핵심 접근은, 결정 함수입니다. 이게 무슨 어려운 것이냐라고 생각하실 수도 있..
java String의 startsWith 메서드는, str이 prefix로 시작하는지를 검사하는 함수입니다. 2번째 인자에 offset을 넣을 수도 있는데요. 이는 str의 offset부터 끝까지는 부분 문자열 sub로 잡았을 때, sub가 prefix로 시작하는지를 검사합니다. 그러면, endsWith도 내부적으로는 startsWith를 쓰겠네요. 쓰는 방법은 아래와 같습니다. boolean startsWith(String prefix); boolean startsWith(String prefix, int offset); 보통 위에 것을 꽤 쓰는 편입니다. 그러면 이들이 어떻게 동작하는지 내부를 간단히 보아야 겠군요. 먼저 String 인자만 하나 넘겨주면 그림에서의 1433번째 줄에 들어갑니다. 그..
Java의 String은 불변 객체입니다. String a와 String b가 있을 때, a = a+b; 이 문장은 어떻게 동작할까요? 결론부터 말하자면, 비효율적으로 동작합니다. 어디서 오버헤드가 많이 발생하는지 천천히 분석해 보도록 합시다. 디버깅을 해 볼 프로그램은 아래와 같습니다. String 객체 str에다가 "05"라는 String을 계속 +하고 있습니다. String a와 b가 있을 때, a+b의 결과값은, String a 뒤에 b를 이어 붙인 String 객체입니다. 예를 들어서, a가 "chogahui"이고 b가 "05"라면, a+b는 "chogahui05"입니다. 9번째 줄에 break point를 걸어두고 어떻게 함수를 호출하는지 간략하게 보도록 하겠습니다. 일단, 뜬금없이 Strin..
최근댓글