코딩테스트, 기초, HashTable

유료강의: / @코드없는프로그래밍
챕터 list: • 코딩테스트 HashMap
code: colab.research...
C++ : github.com/NoC...

[@강태-o7y]

노코프님 2020년 수고 하셨습니다~ 2021년에도 더 많은 영상 부탁드리겠습니다.

[@코드없는프로그래밍]

감사합니다. 더 좋은 영상으로 찾아뵙겠습니다.

[@서울개발자95]

항상 좋은영상 감사합니다. 궁금한게 있습니다. Ranking시스템을 만들때 1. 대용량의 데이터가 들어온다. 2. 이름을 통해 순위를 찾을 수 있다. 3. 순위를 통해 이름을 찾을 수 있다. 이러한 기능이 필요한 상황에서 vector를 정렬한 후 해쉬맵에 넣는거 말고 더좋은 방법이 있을까요..?

[@코드없는프로그래밍]

안녕하세요.우선 검토없이 바로 댓글을 다느라 틀린 내용이 있을 수 있습니다. 벡터를 선언해서 ranking별로 정렬한뒤,이름으로 hashmap을 정하는 방법도 되긴 합니다. 이럴때는 정렬에 n lg n , 랭킹검색에 lg n , 이름검색에 O(1)이 필요합니다. 이러한 방법의 문제는 새로운 elem이 추가/삭제 될때 hashmap을 다시 만들어야 합니다.O(n) 또다른 방법은 ranking기준으로 BST를 만들고 이름 기준으로 hashmap (이름 -> BST node)으로 처리한다면 새로운 데이터가 들어오거나 빠져도 (lg n)에 처리가 가능할것 같습니다. 이보다 더 좋은 방법이 있을수도 있습니다.

[@코드없는프로그래밍]

알고리즘 Test/코딩Test가 아니라 실제 업무라면 업무의 목적,언어,환경에 따라 다르겠지만, 자유도가 높은 환경이라면 SQL아니면 혹은 SQL기능을 프로세스 안에서 처리해주는 모듈을 사용해서 대용량의 data를 넣고 index처리를 해줄것 같습니다.

[@서울개발자95]

@@코드없는프로그래밍 공부 목적으로 만들어 보고 었는데 하다보니 벡터를사용하자니 다른 사용자의 데이터가 들어오면서 밀려나는 과정이 발생하고 맵을 사용하자니 인덱스부분에서 문제가 발생해서 어떻게 하는게 좋을까 고민해보고있었습니다 ㅠㅠ

[@코드없는프로그래밍]

네 댓글에 말한것과 같이 BST와 hashmap을 섞으면 될 것 같습니다. 혹시 이해 안가시면 또 질문주세요.

[@서울개발자95]

@@코드없는프로그래밍 감사합니다! 말씀해주신대로 공부해보고 여쭙겠습니다.

[@CJB-uy5ey]

해시 테이블이라는게 그냥 개념이고 이게 라이브러리로 제공하지 않아서 직접 구현해야하는 것인가요?

[@코드없는프로그래밍]

아닙니다. 대부분의 언어는 해시 테이블을 사용한 data structure를 제공하고있습니다.

[@user-no1oe2rg1v]

Redis같은 키 벨류 인메모리 디비도 해쉬맵처럼 처리될까요?

[@코드없는프로그래밍]

Redis는 O(1) time complexity를 제공하기때문에 기본적인 인덱싱 메카니즘에는 해시를 사용할 것입니다. 하지만 Redis는 단순한 Key-Value를 넘어서 sorted set,list, time limit등을 제공하는것으로 알고있습니다. 거기에 concurrency와 physical memory layout에 optimization이 되야할겁니다. 따라서 내부는 hash base의 Key indexing을 기본으로 더 복잡하게 구성이 되어있을것이고 우리는 그냥 솔루션을 가져다 사용하는 것이겠죠. 제가 Redis 전문가는 아니기 때문에 직접 검색을 해보셔도 좋을듯 합니다. 감사합니다.

[@plttji2615]

hash_table = {} for idx,num in enumerate(nums): hash_table[num] = idx print(hash_table) for num in nums: new_target = target - num print(new_target,num) if hash_table.get(new_target) is not None: return [hash_table[num],hash_table.get(new_target)] return -1 혹시 이렇게 해쉬테이블을 먼저만들고 하면 안되나요?

[@코드없는프로그래밍]

당연히 됩니다.

[@rootelon]

영상 뒷 부분 two sum에 대해서 설명하실 때, 해시테이블을 이용해 답을 구할 경우 최대 두 번의 루프를 돌기 때문에 O(n)의 시간 복잡도를 가진다고 말씀을 하셨습니다. 제곱이 아니고 왜 O(n)인지 이해가 잘 가지 않습니다. 전체 해시테이블을 도는게 O(n), 짝이 맞는 다른 pair를 확인하는데 O(1)이기 때문에 두 번의 루프를 돈다고 말씀하신걸까요? 그리고 시간복잡도를 구할 때 배열->해시테이블로 만드는데 필요한 시간은 빼고 말씀하신건가요?

[@코드없는프로그래밍]

O(n) + O(n) 은 O(n)이기 때문입니다. 따라서 처음 해쉬테이블을 만들때 O(n) 두번째 해시테이블에서 매칭시킬때 O(n)이 필요합니다.

[@rootelon]

@@코드없는프로그래밍 답변 감사합니다!