관심이 가는 개발 보물창고

이번에는 우선순위 큐에 대해서 알아보자. 최근 코딩 테스트도 그렇고 가끔 잊을만하면 나오는 개념이다. 기본적으로 학부생 때 알고리즘 시간에 Heap 구현을 해본 적이 있어서 생각보다 쉽게 받아들여진 것 같다. 우선순위 큐 priority_queue 이름 그대로 우선순위로 정렬된 큐를 의미한다. 어떤 원소를 삽입하거나 삭제할 때 그 내부에서는 우선순위에 따라서 자동으로 정렬되어 보존된다. 내부적으로 Heap을 사용해서 정렬하기 때문에 삽입과 삭제에 대한 연산은 O(logN)에 이루어진다. 운영체제 시간에 선점하는 프로세스 스케줄링의 경우, 우선순위가 기존 ready큐에서 있던 다른 프로세스의 우선순위보다 높은 프로세스가 들어오면 그것부터 cpu를 할당하는 우선순위 스케줄링 알고리즘에서도 나온다. 사용법 #..

stoi c++의 매력을 느낄 수 있는 함수입니다. 바로 문자열을 정수로 바꿔주는 엄청난.. #include int a = stoi("1234"); // 1234 int b = stoi("-1234"); // -1234 int c = stoi("+1234"); // 1234 신기한 점은 문자열 앞에 '+' 나 '-' 부호가 있어도 그것을 반영해서 나타내 준다는 점!!

multimap? multimap은 기본적으로 map과 비슷하지만 다른 부분들이 있다. 비슷한 부분은 [map]에서 확인하자. 1. Key의 중복을 허용한다. 2 [] 연산자를 지원하지 않기 때문에 insert() 멤버 함수로 삽입해야 한다. 연습해보기 #include #include using namespace std; int main() { // less < // left child key < parent key

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이 가질 수..