C++
[C++] lower bound, upper bound
lower bound lower bound는 찾고자 하는 값 이상이 처음 나타나는 위치다. lower bound의 경우에는 같은 원소가 여러개 있더라도 상관없다. 찾고자 하는 값 이상의 값이 처음 나타나는 위치를 찾아내기 위해, 이분탐색 방법에서의 조건을 조금 변경하면 된다. [문제] n개로 이루어진 정수 집합에서 원하는 수 k이상인 수가 처음으로 등장하는 위치를 찾으시오. 단, 입력되는 집합은 오름차순으로 정렬되어 있으며(이분 탐색 가능), 같은 수가 여러개 존재할 수 있다. 입력) 첫 줄에 한 정수 n이 입력된다. 둘째 줄에 n개의 정수가 공백으로 구분되어 입력된다. 셋째 줄에는 찾고자 하는 값 k가 입력된다. (단, 2 0) { m = (s + e) / 2; if (A[m] < k) s = m + ..
[C++] Iterator (반복자)
개념 C++ 라이브러리는 반복자를 제공하는데 이것을 사용하면 라이브러리의 방식대로 자료구조를 액세스 할 수 있다. 따라서 라이브러리가 효과적으로 동작한다는 것을 보장 할 수 있다는 장점이 있다. 즉, 포인터와 상당히 비슷하며, 컨테이너에 저장되어 있는 원소들을 참조할 때 사용한다. 추상적으로 말하자면, 반복자란 컨테이너에 저장되어 있는 모든 원소들을 전체적으로 훑어 나갈 때 사용하는, 일종의 포인터와 비슷한 객체라고 할 수 있다. 알고리즘 마다 각기 다른 방식으로 컨테이너를 훑어가기 때문에, 반복자에도 여러가지 종류가 있게 된다. 성질 - 컨테이너와 컨테이너 안의 있는 요소를 구별 - 요소의 값 확인 - 컨테이너 안에 있는 요소들 간에 이동할 수 있는 연산 제공 - 컨테이너가 효과적으로 처리할 수 있는 ..
[C++] iterator (반복자) vector와 list의 비교
개념 어떤 컨테이너(자료구조)에 접근하든 동일한 방법으로 접근하기 위해서 제공되는 객체. 반복자는 원소의 위치를 갖고 있는 포인터와 비슷한 형태이다. 반복자를 이해하기 위해 먼저 벡터와 리스트의 접근 방식을 비교해보자. 벡터는 배열 기반으므로 연속된 메모리 공간을 가지고 있다. 그래서 인덱스 연산으로 임의 접근이 가능하고, 인덱스에 넣은 값을 증가시키는 방식으로 순회도 가능하다. 모든 컨테이너에 이런 간단한 방식으로 접근이 가능하다면 반복자는 필요하지 않을 것이다. 하지만 컨테이너들마다 접근 방식이 다르다. 하지만 리스트는 우선 연속된 메모리 공간을 가지지 않기 때문에 벡터처럼 인덱스 로 접근하는 것이 불가능하다. 즉 다른 방법으로 순회를 해야 한다. 리스트는 현재 가리키고 있는 노드와 다음 노드의 주소..
[C++] map value sort - 맵 값 정렬
Map 컨테이너에서 처음 선언하는 방식의 따라 Key 기준으로 오름차순, 내림차순을 지정할 수 있지만 만약 Key가 아닌 Value를 비교하여 정렬을 하고 싶을 경우라던지 단순히 오름차순, 내림차순이 아닌 특정 조건에 의하여 정렬을 하고 싶을 경우 Map을 Vector로 변환한다음 Vector에서 정렬을 하던것처럼 해주면 된다. #include #include #include #include using namespace std; typedef pair ii; int main() { map map; map[5] = 20; map[2] = 50; map[3] = 10; map[4] = 40; map[1] = 30; map[6] = 60; for (auto it : map) { cout
[LeetCode] Majority Element
#include using Intpair = pair; class Solution { public: int majorityElement(vector& nums) { map m; for (const auto& item : nums) m[item]++; vector v(m.begin(), m.end()); sort(v.begin(), v.end(), [&](Intpair& lRef, Intpair& rRef) { return lRef.second < rRef.second; }); return (*(v.end() - 1)).first; } };
[C++] 계단 오르기 알고리즘
예로 들어서 n이 3이라면 꼭대기에 도달 하는데까지 총 3가지의 방법이 존재한다. 다른 예시로는 n = 1 // 한 가지의 방법만 존재하므로 1을 출력 n = 2 // 2, (1 , 1)과 (2) n = 4 // 5, (1, 1, 1, 1), (1, 1, 2), (2, 1, 1), (1, 2, 1), (2, 2) 재귀를 사용한 방식 방법의 수(n) = 방법의 수(n - 1) + 방법의 수(n - 2) 피보나치 수열을 이용하여 구할 수가 있다. 방법의 수(1) = 피보나치(2) = 1 방법의 수(2) = 피보나치(3) = 2 방법의 수(3) = 피보나치(4) = 3 int fib(int n) { if (n
Doxygen 을 이용한 C++ API 문서 만들기
step 01 : Doxygen Download http://www.stack.nl/~dimitri/doxygen/download.html step 02 : Graphviz Download (선택 사항) http://www.graphviz.org/Download_windows.php step03 : Doxygen 문서로 만들 Sample Code 생성 Doxygen 문서를 만들기 위해서는 하기 초록색 색인 된 주석 부분이 필요하다. //---------------------------------------------------------------------------- // @file 파일명, @brief 파일에 대한 설명 해당 주석이 가장 먼저 선언되어야 함 /** @file main.cpp @bri..
[C++] string > int 변환 (개인 작성)
class MyString { string str; public: MyString() = default; MyString(string str) : str(str) { cout
[LeetCode] Rotate Array
void rotate(vector& nums, int k) { deque dq; for (int j = 0; j < nums.size(); j++) dq.push_back(nums[j]); nums.clear(); for (int i = 0; i < k; i++) { int val = dq.back(); dq.pop_back(); dq.push_front(val); } while (!dq.empty()) { nums.push_back(dq.front()); dq.pop_front(); } }