Notepad

C++/Algorithm

2의 n제곱 수인지 판별하기

1. 개 요 2의 n제곱 수를 2진수로 나타낸다면 2의 1제곱 2 -> 10 2의 4제곱 16 -> 10000 2의 6제곱 64 -> 1000000 2의 0제곱 1 -> 1 와 같이 1로 시작하며 오른쪽의 0이 채워지는 형태이다. 그렇다면 이제 각 수에서 1을 뺀 수를 2진수로 나타내보면 (2의 1제곱-1) 1 -> 1 (2의 4제곱-1) 15 -> 1111 (2의 6제곱-1) 63 -> 111111 (2의 0제곱-1) 0 -> 0 그러면 여기서 0제곱을 제외하고는 1로 2진수가 1로 이루어진 것을 확인 할 수 있다. 그렇다면 이와 같은 사실을 이용하여서 임의의 수 n이 2의 제곱수인지 판별할 수 있다. 임의의 수 n과 n-1를 비트 연산자 &를 사용하여 연산하면 n이 2의 제곱 수인 경우 그 결과 0이..

C++/Container

[STL] Multimap 생성, 삽입, 삭제 등 사용법

1. multimap multimap 또한 set과 multiset과의 관계와 마찬가지로 map과는 중복되는 원소를 갖을 수 있다는 차이점만이 있다. 따라서 map에서 사용하였던 insert, erase, count, find와 같은 함수들을 그대로 사용할 수 있다. 단, map에서 insert 시 [] 연산자를 사용할 수 있었다면 multimap에서는 [] 연산자를 사용할 수 없다. 따라서 삽입 시 insert 멤버 함수를 사용하여서 pair 객체를 넣어주거나 해야 한다. 또한, find 멤버 함수는 똑같은 key값의 여러 원소가 존재하여도 맨 앞에 오는 원소의 반복자를 반환한다. 따라서 해당 key값의 모든 원소들의 접근하고자 한다면 multiset에서 사용하였던 것처럼 lower_bound()와 u..

C++/Container

[STL] Map 생성, 삽입, 삭제 등 사용법

1. map map은 쌍의 값들을 저장하는 구조이다. map은 쌍의 값을 갖는다는 것 빼고는 대부분 set과 유사한 구조이다. [STL] Set 생성, 삽입, 삭제 등 사용법 1. set set은 특정 기준에 의하여 원소들이 자동 정렬되는 노드 기반 컨테이너이다. set은 기본적으로 오름차순(less) 정렬이고 greater 조건자를 줌으로써 내림차순으로 정렬할 수도 있다. set은 유 notepad96.tistory.com 따라서 set에서 사용하였던 count, find, upper_bound 와 같은 멤버 함수들도 그대로 존재한다. 하지만 set과 다르게 [] 연산자를 지원하여 insert 함수를 사용하지 않아도 쉽게 삽입을 할 수 있다. map은 set과 마찬가지로 특정 정렬 기준(less 또는 ..

C++/Container

[STL] Multiset 생성, 삽입, 삭제 등 사용법

1. multiset multiset은 중복된 원소를 저장할 수 있다는 점 외에는 set과 동일한 특성을 갖는다. multiset 또한 기본적으로 오름차순으로 정렬되며 조건자로 greater를 사용함으로써 내림차순으로 정렬할 수 있다. [STL] Set 생성, 삽입, 삭제 등 사용법 1. set set은 특정 기준에 의하여 원소들이 자동 정렬되는 노드 기반 컨테이너이다. set은 기본적으로 오름차순(less) 정렬이고 greater 조건자를 줌으로써 내림차순으로 정렬할 수도 있다. set은 유 notepad96.tistory.com 그래서 set이 집합을 의미했다면 multiset은 중복집합을 의미한다는 것을 알 수 있다. 따라서 수학적인 문제를 해결할 시 집합이 필요하다면 set을 중복집합이 필요하다면..

C++/Container

[STL] Set 생성, 삽입, 삭제 등 사용법

1. set set은 특정 기준에 의하여 원소들이 자동 정렬되는 노드 기반 컨테이너이다. set은 기본적으로 오름차순(less) 정렬이고 greater 조건자를 줌으로써 내림차순으로 정렬할 수도 있다. set은 유일한 원소만을 갖을 수 있는 구조로서 수학적으로 집합을 의미하는 것을 알 수 있다. 중복된 원소를 갖고자 한다면 multiset을 사용하여야 한다. 또한, 균형 이진 트리로 구현되어 빠른 시간으로 원소를 탐색할 수 있으며 이에 따라 탐색할 수 있도록 여러가지 탐색 함수를 제공해 준다. 2. 코 드 환경 : Visual Studio 2019 #include #include using namespace std; int main() { /* 생성자 */ set set;// 오름차순, 기본 값 : le..

C++/Container

[STL] List 생성, 삽입, 삭제 등 사용법

1. list list는 vector와 deque처럼 상대적인 순서를 유지하는 컨테이너이다. 하지만 vector와 deque가 배열 기반이였다면 list는 노드 기반으로서 이중 연결 리스트로 구현되어 있다. 그래서 vector와 deque와 멤버 함수가 유사하면서도 추가적으로 여러 함수가 더 있다. list는 이중 연결 리스트로 구현되어 있기 때문에 vector, deque에서 비효율적이였던 insert()를 사용한 중간 삽입 또한 효율적으로 동작한다. ( 이중 연결 리스트에서는 링크만 바꾸어 주면되므로...) 따라서 상대적인 순서를 유지해야하며 중간에 삽입, 삭제가 빈번하게 발생할 것으로 예상된다면 list 컨테이너를 사용하는 것이 좋다. 2. 코 드 환경 : Visual Studio 2019 #inc..

C++/Container

[STL] Deque 생성, 삽입, 삭제 등 사용법

1. deque deque, 디큐 혹은 덱이라고 부른다. deque 또한 vector와 마찬가지로 배열 기반 컨테이너로서 vector의 있는 멤버 함수들과 거의 유사하다. vector와 다른점을 말하면 바로 보이는 것으로는 push_front(), pop_front()가 있다. 해당 멤버 함수들을 사용하여서 vector에서는 뒤에서만 push, pop 하였다면 deque는 앞과, 뒤 2방향에서 원소를 삽입하거나 삭제할 수 있다. (사실 insert, erase 멤버 함수를 사용하면 vector도 삽입, 삭제 가능함. 단, 비효율적) 그래서 스택+큐의 구조라 볼수 있다하지만 이는 엄밀히 말하자면 아니며, 쉽게 기억하기 위하여 스택+큐 구조다라고 생각만 하면 될 것이다. 또한, 눈에 보이지는 않지만 vect..

C++/Algorithm

C++ 문자열 나누기 - string split

1. split Java, JavaScript, Python 등등 대부분의 언어에서 지원하는 문자열 함수이다. split은 특정 문자를 기준으로 문자열을 나누어 준다. ex) 문자열 "abc ef ghi" 을 " "로 나눈다하면 "abc", "ef", "ghi" 를 리턴해준다. 2. 코 드 환경 : Visual Studio 2019 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include using namespace std; vector split(string s, string divid) { vector v; char* c = strtok((char*)s.c_str(), divid.c_str()); while (c) { v.push_bac..