관심이 가는 개발 보물창고

map? 1. 연관 컨테이너이며 노드 기반 컨테이너 2. 특정 정렬 기준으로 원소(Key)가 자동으로 정렬된다. 3. 균형 이진트리의 장점을 가지고 있어 찾기, 삭제, 삽입의 성능 O(lgN)을 보장한다. 자주 사용하는 멤버 함수 기본적으로 연관 컨테이너 set과 똑같지만 차이점을 주자면 [] 연산자를 제공한다. [] 연산자를 이용해서 원소(key, value)를 삽입하거나, key에 매핑된 value를 갱신할 수 있다. 아래에는 자주 사용하는 부분들을 정리했다. insert(pair(key,value)) map에 pair 객체로 key와 value를 저장한다. map[key] = value map에 key에 해당하는 원소가 없다면 (key, value) 저장하고 key에 해당하는 원소가 있다면 valu..

특징 1. 자동적으로 정렬되지 않는다. 2. hash 사용으로 bucket 으로 인해 메모리 사용량 증가 3. insertion, deletion, find O(1)에 수행, 다만 충돌이 너무 많이 일어나면 O(N) (그러면 기존 set 보다 더 느리게 수행될 수 있다는 말이다.) 4. hash 자료구조를 사용한다. 원소의 개수가 많을수록 해시 충돌이 일어날 확률도 많아지게 되므로 경우에 따라 사용하자. 원소의 개수가 적고 빠른 성능 : unordered_set 원소의 개수가 많고 안정성 : set Hash function 정의는 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수. unordered_set 에 특정 value 를 찾거나 넣을 때 해당 value 를 hash function 에 ..

특징 set의 경우 key 값이 중복되지 않지만, multiset의 경우 key 값이 중복될 수 있다. 대부분의 특징들은 set과 동일하므로 바로 예제를 통해서 하나씩 배워보자. 삽입 set과 마찬가지로 insert(key); 를 이용해서 삽입할 수 있다. #include #include using namespace std; int main() { multiset ms; // less < // left node < parent node

스택의 응용 중 하나인 후위 표기식에 대해서 배워보자. 후위 표기식 우리가 자주 사용하는 표기식은 중위 표기식(infix expression)을 따른다. 5 + 3 후위 표기식(postfix expression)은 연산자가 피연산자 뒤에 나오는 것을 말한다. 5 3 + 후위 표기식 계산법 7 4 -3 * 1 5 + / * 스택 자료구조를 이용해서 계산할 수 있다. 핵심은 두 수를 뽑을 때의 순서가 중요하다. 방법은 다음과 같다. 1) 피연산자(즉, 숫자)가 들어오면 무조건 출력 2) 연산자가 들어오면 스택의 최상단에서 두 값을 뽑아 연산자에 맞게 계산하고 다시 스택에 넣어준다. 단계별로 확인해보자. input : 7 4 -3 * 1 5 + / * Stack 7 7 4 7 4 -3 7 -12 ( * 연산자..

특징 집합은 요소의 값이 요소를 식별하기 때문에 각 요소가 고유(유니크) 해야 하는 연관 컨테이너 유형이다. 1. 중복 값이 올 수 없다. (유니크하다, -> 중복 제거 기능) 2. 삽입하는 순서에 상관없이 무조건 정렬된다. 3. Balanced Tree(균형 이진 트리) 중 R-B Tree를 통해 구현되어 있다. 4. 연관 컨테이너이며 key를 변경할 수 없다. 5. 삽입, 삭제, 검색 O(lgN)의 성능을 가지고 있다. 추가적으로 count(), lower_bound(), upper_bound(), equal_range()도 O(lgN)에 수행된다. 자주 사용하는 멤버 함수 empty() 비어있다면 true, 아니면 false size() 저장된 원소의 개수 리턴 max_size() set이 가질 수..