노는 게 제일 좋아

[문제풀이(Problem Solving)/C++ 문제풀이에 유용한 것들] - 문자열 정수 변환 string to int, int to string [문제풀이(Problem Solving)/C++ 문제풀이에 유용한 것들] - 배열을 초기화시키는 여러가지 방법 [문제풀이(Problem Solving)/C++ 문제풀이에 유용한 것들] - vector에서 iterator 활용 [문제풀이(Problem Solving)/C++ 문제풀이에 유용한 것들] - 컨테이너 원소들의 최대, 최소 그리고 최대 최소 비교 [문제풀이(Problem Solving)/C++ 문제풀이에 유용한 것들] - 입출력이 많음으로 인해 시간초과나는 것 해결 [문제풀이(Problem Solving)/C++ 문제풀이에 유용한 것들] - C++에서의..

어떠한 값을 찾을 때 정렬이 되어있는 데이터들 안에서(이게 핵심이다) 정렬하는데 시간이 더 걸린다면 그냥 이진탐색 사용하지 않는게 낫다. 선형 탐색보다 훨씬 빠른 탐색속도를 가진 이진탐색이다. 일반적으로 Array가 이용된다. 우선보자 23을 찾기 위해서 중앙값을 조사한다. 중앙값보다 크기에 이번에는 중앙값으로 나눠진 오른쪽 그룹에 대해 중앙값을 조사한다. 그 나눠진 그룹의 중앙값보다는 작기에 다시 왼쪽 그룹을 만들어 조사한다. 나올 때까지 조사한다. 만약 값이 없다면 값이 없는 것은 어떻게 판단할 수 있을까?? 다시 보자 이번엔 24를 찾는다고 해보자 0-9까지 10개의 원소가 있다. 4번 인덱스를 조사했고 해당 값이 더 커서 5번부터 9번까지 사이의 중앙값인 7번을 조사했다. 7번보다는 작아서 5번과..

유용한 STL인 큐 중에서 우선순위 큐를 알아보자 그냥 큐와 무엇이 다른지도 알아보자 Priority queues are a type of container adaptors, specifically designed such that its first element is always the greatest of the elements it contains, according to some strict weak ordering criterion. 일반적으로 첫번째 원소가 제일 큰 값을 가지게 하는 컨테이너다. **물론 첫번째 원소가 제일 작은 값을 나오게 할 수도 있다. This context is similar to a heap, where elements can be inserted at any mome..

set를 알아보자 set란 Sets are containers that store unique elements following a specific order. ++기본적으로는 오름차순으로 정렬된다. 집합과 같다. 같은 원소는 존재하지 않고 정렬되어있는 컨테이너를 말한다. 정렬되어있고 유일성을 가져서 중복제거에 많이 쓰이고는 한다. **만약 중복원소를 가지고 싶다면 Multiset을 이용할 수 있다. 주요 함수로는 set: 원하는 자료형 및 클래스 T를 통해 생성 iterator(반복자) begin(): beginning iterator를 반환 end(): end iterator를 반환 Insert & Update & Delete insert(element): 세트에 element를 추가 erase(el..

맵이 뭔가 싶지만 C++의 dictionary를 맵이라 부른다. 즉, key ,value 짝의 자료구조를 맵이라 부른다. 그래서 선언할 때도 key자료형, value자료형 같이 선언한다. map: key와 value를 pair 형태로 선언한다. **unordered_map은 체이닝을 사용하는 해시 테이블로 구현되어 있다. 부하율이 1이 되면 해시 테이블의 크기를 키우고 재해싱을 하게 된다. 우선 Map이란 Maps are associative containers that store elements formed by a combination of a key value and a mapped value, following a specific order. 일반적으로 맵에서 key를 찾아서 value를 반환하는..

나는 벡터를 가장 많이 쓰지만...그래도 알아둬야할 것들은 알아둬야지 항상 자료구조를 배울 땐 중요한 것이 있다. CRUD, 삽입, 수정, 접근, 삭제 Create, Read, Update, Delete 이다. 우선 list란 Lists are sequence containers that allow constant time insert and erase operations anywhere within the sequence, and iteration in both directions. 시퀀스형 컨테이너 구조로 삽입과 삭제에 O(1)복잡도를 가지며 iterator는 bidirectional이란다. property로는 Sequence Elements in sequence containers are order..

1. fill 함수 - 헤더에 포함 특정한 값으로 채우고 싶을 때나 그냥 초기화할 때 fill(시작주소, 끝주소, 넣고싶은 값) 이라고 생각하면 좋다. void 라 반환값은 없다. #include // std::fill #include // std::vector int main () { std::vector myvector (8); // myvector: 0 0 0 0 0 0 0 0 std::fill (myvector.begin(),myvector.begin()+4,5); // myvector: 5 5 5 5 0 0 0 0 std::fill (myvector.begin()+3,myvector.end()-2,8); // myvector: 5 5 5 8 8 8 0 0 return 0; } 만약 배열이라면 f..

어떤 컨테이너에 원소들이 들어있고 역순으로 정렬되기를 원한다면 을 include해야 쓸 수 있다. https://www.cplusplus.com/reference/algorithm/reverse/ reverse()를 쓰면 된다. #include #include using namespace std; int main(){ vector a; reverse(a.begin(), a.end()); return 0; } https://www.cplusplus.com/reference/iterator/BidirectionalIterator/ 다만 눈에 띄는 점이라면 void reverse (BidirectionalIterator first, BidirectionalIterator last); 즉, 그냥 이터레이터가 아..

[문제풀이(Problem Solving)/C++ 문제풀이에 유용한 것들] - 유클리드 호제법, 최대공약수 구하기, GCD [C++] 위 글도 참고하면 좋다. 아무튼 특정 숫자의 약수를 구하기 위해서는 약수의 정의부터 알 필요가 있다. 일반적으로 b=an인 정수 n이 존재할 때, a|b라 하고, 이때의 a를 b의 약수라 한다. 다르게 말하면 어떤 정수를 나누어 떨어지게 하는 0이 아닌 정수라고 한다. 모든 자연수는 최소한 1과 자기 자신을 약수로 갖는다. **소수는 최소한의 약수만을 가진 1을 제외한 자연수를 말한다. 다시 말해서 약수가 1과 자기 자신뿐인 자연수를 말한다. **합성수는 1과 자기자신 외에 다른 약수를 가지면 즉, 약수가 3개 이상이면 합성수라고 할 수 있다. 다시 말하면 소수들의 곱으로 ..

최소공배수보다 최대공약수가 정말 많이 쓰인다. 어차피 최대공약수를 알 수 있으면 최소공배수도 알 수 있다. 즉, 쓰이는 곳이 많다. 최소공배수 구하기, 최대공약수 구하기, 기약분수 구하기 등 여기서 만능공식이 있으니 그것이 바로 유클리드 호제법이다. 기본 형태는 이렇다. 수학자가 증명한 것이 참이라고 가정하고 이용한다. 공학자는 증명보다는 활용을 하기에 하지만 굳이 증명하고 싶다면 말리지는 않는다. 즉, 작은 것으로 치환할 수 있다는 말이다. 만약 gcd함수를 불러온다면.. 그것보다 작은함수를 불러오는 건가..? 재귀같네?? 라고 생각하면 생각이 깊은 사람 굿 아무튼 C++에서는 여러가지 방법으로 구현할 수 있다. 일반적으로 a>b를 가정하고 만들긴한다. 하지만 굳이 a>b를 가정해야하느냐? 라는 사람이..