hash map4 C++ 136. Single Number(Leet Code) Leet Code_136. Single Number https://leetcode.com/problems/single-number/ 문제 해석 이 문제를 풀기위해 이해해야 할 내용은 다음과 같습니다. 목표 vector 원소 중 중복되지 않는 숫자 구하기 방법 1. vector 원소 중 중복되지 않는 숫자 구하기 2. hash table을 사용하기 결과 vector 원소 중 중복되지 않는 숫자 구하기 통과한 코드 class Solution { public: int singleNumber(vector& nums) { unordered_map map; for(int i = 0 ; i < nums.size() ; i++) { map[nums[i]]++; } for (unordered_map::iterator.. 2020. 6. 22. C++ 자료구조 - unordered map(hash map) unordered map(hash map) map과 비슷하지만 정렬이 되어있지 않다. insert, erase, find 모두가 O(1)O(1) 으로 수행된다 셋이나 맵의 경우 O(log n)O(logn) 이었지만, unordered_set 과 unordered_map 의 경우 상수 시간에 원소를 삽입하고, 검색할 수 있다. 원소의 key 값(데이터형)을 hash function을 통해 생성한다.(대부분 정수값) 다른 원소이지만 같은 해시값을 가질 수 있다(해시 충돌(hash collision)) 1. 사용 - #include - unordered_map [변수이름] 2. 생성자와 연산자(int로) - unordered_map um; - 비어있는 unordered_map um을 생성 3. 멤버 함수 - .. 2020. 6. 22. C++ 1. Two Sum(Leet Code) Leet Code_1. Two Sum https://leetcode.com/problems/two-sum/ 문제 해석 이 문제를 풀기위해 이해해야 할 내용은 다음과 같습니다. 목표 더해서 target 값이 되는 두개의 원소 찾기 방법 1. 더해서 target 값이 되는 두개의 원소 찾기 2. hash map을 사용한다. 결과 더해서 target 값이 되는 두개의 원소 찾기 통과한 코드 그냥 순회하면서 찾는 코드 class Solution { public: vector twoSum(vector& nums, int target) { vector res; for(int i = 0 ; i < nums.size() ; i++) { for(int j = i+1 ; j 2020. 6. 22. C++ 자료구조 정리 1. LIST - 더블 링크드 리스트로 구현되어 있다. - 더블 링크드 리스트의 장점을 그대로 가져오며 중간에 삽입/삭제가 빠르다. - 하지만 특정 원소에 접근하려면 선형탐색을 해야한다. 상호 포인터 정보를 가지고 있기 때문에 메모리 사용비율이 높다. 2. Stack 3. Queue 4. Vector - 배열인데, 동적으로 크기를 확장 또는 축소가 가능하게 되어있는 자료구조(크기조절 시 오버헤드 큼) - 역시 배열의 특징을 그대로 가져온다. 데이터의 위치를 알고 있으면 랜덤 엑세스가 가능하다. - 하지만 중간에 데이터를 삽입 또는 제거하려면 땡기거나 밀어야 되는 단점도 그대로 가지고 온다. - 하지만 끝부분에 삽입할 땐 빠름 5. Deque(덱) - LIFO, FIFO 두 가지 방식을 다 사용할 수 있는.. 2020. 6. 19. 이전 1 다음
