본문 바로가기

알고리즘 부셔버렷/나만의 작은 STL정보6

[C++ STL] lower_bound, upper_bound 요약 설명 (실전 알고리즘) 설명 사용법 설명 lower_bound, upper_bound 둘 다 algorithm 헤더 안에 있는 함수이며 set같은 특정 컨테이너 안에도 메서드로 존재합니다,둘 다 이분탐색으로 구현되어있습니다. lower_bound는 찾고자 하는 값보다 크거나 같은 값 중 가장 처음 나오는 값의 반복자를 반환합니다. upper_bound는 찾고자 하는 값보다 큰 값 중 처음 나오는 값을 반환합니다. lower_bound는 upper_bound에서 찾고자 하는 값과 같은 경우가 더해진 것 입니다. 주어진 데이터에서 찾고자 하는 값이 없는 경우에는 다음과 같습니다. 찾는 값이 주어진 데이터들 보다 크다면 lower_bound는 end() 반복자를 반환합니다. upper_bound 또한 end() 반복자를 반환합니다... 2022. 7. 27.
빈 컨테이너의 iterator, begin()과 end()는 무엇을 가리킬까. 그리고 증감 연산. 빈 컨테이너의 경우 begin()과 end()는 서로 같은 값을 가진다. list li; auto it = li.begin(); for (auto i = li.begin(); i == li.end();) { cout > s; for (auto c : s) { if (c == '') { if (p != L.end()) p++; } else if (c == '-') { if (p != L.begin()) { p--; p = L.erase(p); } } else L.insert(p, c); } 다음 글들을 참고하였습니다. https://stackoverflow.com/questions/25600484/c-empty-container-iterator-behaviour https://stackoverflow.co.. 2022. 6. 16.
[STL] 부분조합 구하기 (prev_permutation과 bool 배열을 응용) 설명 구현 설명 STL의 prev_permutation과 bool 배열을 사용합니다. 우선 prev_permuation은 algorithm 라이브러리에 있는 함수로써 내림차순되어있는 컨테이너, 자료들을 순열로 정렬해줍니다. 이 때의 반환형은 순열로 정렬이 가능하다면 true, 불가능하다면 false를 반합니다. 다음과 같은 크기 5정도의 bool배열에서 5C3을 구할 때 일어날 과정에 대하여 나타내겠습니다. bool b_arr = {1, 1, 1, 0, 0}; 1, 1, 1, 0, 0 1, 1, 0, 1, 0 1, 1, 0, 0, 1 1, 0, 1, 1, 0 1, 0, 0, 1, 1 0, 1, 1, 1, 0 0, 1, 1, 0, 1 0, 1, 0, 1, 1 0, 0, 1, 1, 1 0, 1의 크기와 이 .. 2022. 6. 14.
[STL] erase remove idiom (설명, erase, remove 차이, 예) erase remove idiom이란 erase remove idiom은 c++ STL 컨테이너에서 어떤 특정한 원소를 제거하기 위한 기법입니다. 각 컨테이너의 멤버함수인 erase와 algorithm 라이브러리의 remove, remove_if 함수를 통하여 구현합니다. erase 함수와 remove 함수의 차이와 응용 우선 erase 함수와 remove 함수의 차이점을 말씀 드리자면 erase는 vector같은 연속적인 특성을 가진 컨테이너의 데이터를 지우는 경우 데이터를 지운 뒤 빈 공백, 틈들을 막기위해 뒤의 값들이 일제히 당겨집니다. 이때 상황에 따라 꽤 많은 오버헤드가 일어날 수 있습니다. 그리고 remove는 조건에 맞는 값을 그 뒤의 값들로 덮어씁니다. 그래서 해당 연속적인 특징을 가진 컨.. 2022. 6. 9.
[STL] next_premutation() (STL 순열 ) 순열, next_permutation c++ STL에서는 순열과 조합을 만들어주는 함수를 제공합니다. 두 함수는 라이브러리에 존재합니다. 순열, next_permutation 순열을 만들어주는 next_permutation. bool next_permutation(vec.begin(),vec.end()); 인자로 넘겨진 반복자를 이용해 순열의 형태로 정렬한 후 true를 반환합니다, 더 이상 순열의 형태로 정렬할 수 없다면 false를 반환합니다. 또 이 함수는 중복을 제외하며 2022. 6. 1.
문자열 문제에서 유용한 STL 함수 편의를 위하여 index와 iter를 축약하여 말하는데 index는 배열 등의 index를 뜻하며 unsigned int 타입으로 이해하시면 됩니다. iter는 반복자를 의미합니다. string 라이브러리 begin(),end() : 각 각 string의 시작 반복자와 마지막의 다음번째를 가리키는 반복자를 반환한다. front(), back() : 각 각 string의 첫번째 문자와 마지막 문자를 반환한다. empty() : string이 비었는지 확인하고 비었으면 true 아니면 false를 반환한다. insert(index, count, char) : index에서부터 count만큼 char를 삽입한다. (index, string) : index에서부터 string을 삽입한다. (index, stri.. 2022. 5. 27.

티스토리툴바