Mnemonic

[ C++ : push_back()과 emplace_back(), Add()와 Emplace() ] C++의 vector에서 push_back() 대신에 emplace_back()를 쓰라는 말이 종종 있다.이것은 UE5 C++에서 TArray에도 공유되는 개념인데, TArray의 공식문서에서 다음과 같이 설명하고 있다. [ UE5 C++ : TArray Document ]The array's allocator provides memory as needed when new elements are added to the array. The default allocator adds enough memory for multiple new elements whenever the current array size ..

* 사용전 오름차순 정렬 필수 [ lower_bound ]찾으려는 값보다 같거나 큰 숫자가 배열의 몇 번째에서 처음 등장하는지 이분 탐색. [ upper_bound ]찾으려는 값을 초과하는 숫자가 배열의 몇 번째에서 처음 등장하는지 이분 탐색. 이분 탐색이므로 둘 다 O(log N).vector v;/* ... */::sort(v.begin(), v.end());const int lowerCnt = (::lower_bound(v.begin(), v.end(), 3) - v.begin());const int upperCnt = (::upper_bound(v.begin(), v.end(), 3) - v.begin());  [ 연습 문제 ]lower_bound과 upper_bound를 같이 사용하는 풀이 존재..

[ Hash Table ] Key를 알면, 데이터를 단번에 찾을 수 있는 자료구조탐색에 상수시간, O(1)이 소요된다.메모리를 내주고 대신 빠른 시간을 얻는 방식 [ Table ]우선 테이블은, 예를 들어 UserId 같은 것을 인덱스로해서 버킷(bucket)에 접근, 데이터를 얻을 수 있음하지만 만약, 게임내의 유저 수가 몇백만명을 넘어가는 상황이라면 어떻게 해야할까? 메모리가 터질 수도 있을 것이다.→ 여기에 해시를 추가해서 사용해보자. [ Hash ]userId를 인덱스로 써서 직접적으로 접근하는게 아닌, 해시함수를 통해서 한 번 변환된 걸 Key값으로 사용해서 접근. Example) 보안DB에 있는 유저 아이디에 대한 비밀번호의 경우 평문을 그대로 넣지 않고 해시값을 저장함.비밀번호를 통해 해시값..

[C++] 퀵 정렬 일반적인 경우 단일 정렬 알고리즘 중 가장 빠른 정렬  [ 작동원리 ]Partition의 기준점인 Pivot이 존재간단히 Pivot을 left로 설정해서 생각해보자.Pivot = leftlow = left + 1high = right - 1단계pivot >= arr[low]일 동안 low를 오른쪽으로 이동: pivot보다 큰 값을 만날 때까지 low를 오른쪽으로 이동pivot : pivot보다 작은 값을 만날 때 까지 high를 왼쪽으로 이동 - 2단계low  ... 다시 1단계로 - 3단계low와 high가 교차되는 상황이 온다high 결과 : pivot의 위치는 확정됨 ! (정렬된 자리를 찾음)pivot을 기준으로 왼쪽에는 더 작은 숫자, 오른쪽에는 더 큰 숫자가 오게 됨.자리를 ..

[C++] 병합 정렬 (또는 합병 정렬) 1945년 폰 노이만에 의해 개발됨. 분할 정복 (Divide and Conquer)를 이용한 정렬 알고리즘분할 (Divide) : 문제를 더 단순하게 분할정복 (Conquer) 분할된 문제를 해결결합 (Combine) 결과를 취합하여 마무리  처음 MergeSort() 내에서, 원소가 1개가 될 때 까지, 즉 경계를 의미하는 left와 right가 같아질 때 까지 재귀적으로 쪼갠다.1개가 되면, 그 때 부터 개별적으로 정렬한 뒤, 원래 배열에 정렬된 부분을 넣으며 합친다.  절반 씩 쪼갤 때 O(log N), 다시 합칠 때 총 N개를 합치므로 O(N)으로 총 O(N log N)의 시간 복잡도를 가진다.그러므로 최선, 평균, 최악의 시간 복잡도 O(N log N)..

Heap Tree, Priority Queue when ?데이터들 중 가장 큰 값 또는 가장 작은 값을 계속해서 추출해야 하는 필요성이 있을 때 사용 [ 구조 ]우선은 이진 트리의 형태를 갖는다. (각 노드가 최대 2개의 자식 노드를 갖는 트리)힙 트리의 구조를 유지하기 위해서 2가지 규칙이 존재한다. (공식용어는 아님) ( 규칙 1 )[부모 노드]가 가진 값은 항상 [자식 노드]가 가진 값보다 커야함. (Predicate에 따라 다름): 위 조건만 만족한다면 어떻게든 괜찮다 (이진 탐색 트리보다 조건이 느슨함)( 규칙 2 )마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 함. (완전 이진 트리)마지막 레벨에 노드가 있을 때는, 항상 왼쪽부터 순서대로 채워야 함.위 2가지 구조를 통해 알 수 있는..

STL (Standard Template Library)프로그래밍할 때 필요한 자료구조/알고리즘들을 템플릿으로 제공하는 라이브러리 vector : 동적 배열 알아볼 내용- vector의 동작 원리 (size/capacity)- 중간 삽입/삭제- 처음/끝 삽입/삭제- 임의 접근 기본적인 내부 동작- 여유분을 두고 메모리를 할당한다- 여유분까지 꽉 찼으면, 메모리를 증설한다=> 기존에 쓰던 영역을 버리고 더 큰 영역을 할당받아서 쓴다 Q1) 여유분은 얼마만큼이 적당할까?Q2) 증설을 얼마만큼 해야할까?Q3) 기존의 데이터를 어떻게 처리할까? 실제 데이터가 있는 크기를 size, 여유분까지 해당하는 크기를 capacity라 칭한다.capacity는 컴파일러에 따라 다른데, visual studio기준 1.5배..