ZeroOne

가끔 배열이나 벡터를 전부 초기화 해야할 일이 생긴다.

평소에 for문을 돌려서 초기했다면 fill, fiil_n을 사용해서 코드를 간결하게 만들자.

1) fill

template< class ForwardIt, class T >
void fill( ForwardIt first, ForwardIt last, const T& value );

 fill(초기 위치, 마지막 위치, 초기화값); (초기위치<= arr < 마지막위치)

 예제 : fill(arr,arr+5,1);

2) fill_n

template< class OutputIt, class Size, class T >
void fill_n( OutputIt first, Size count, const T& value );

 fill_n(초기 위치, 사이즈, 초기화값);

 예제 : fill_n(arr,5,1);

0으로 초기화하려면 memset(arr, 0, sizeof(arr)); 이 제일 좋다.

그러나, fill, fill_n을 써도 문제 없다.

그리고 2차원 이상의 배열의 경우 fill_n은 1차원으로 인식하는 문제가 있으므로 fill을 사용하는 습관을 들이자.

 예제 : fill(&arr[0][0], &arr[5][3], 7);

결론 : fill 마스터하자

set

키들을 이진 탐색 트리를 기반으로 저장한다. 따라서 자동 정렬되는 컨테이너이고 탐색 시간은 O( log n ) 입니다. 삽입과 제거가 빈번해지면 느리다.

undorderd_set

해쉬 테이블 기반으로 저장한다. 어떤 해쉬를 쓰느냐에 따라 다르겠지만, 같은 해쉬값을 중복적으로 저장한다면 최대 O(n)의 시간복잡도를 갖는다. 따라서 탐색시간이 기본적으론 O(1) 이지만 최악의 경우 O(n) 입니다. 자동 정렬되지 않는 set이다.  버킷 때문에 메모리 사용량이 증가할 수 있다.

결론 : 알고리즘 문제의 경우 최악의 복잡도가 중요하므로 기본 set을 이용하여 풀자. (이진탐색의 경우 set을 쓰면 좋다.)

Set은 중복을 찾기에 최적화된 자료구조다.

#include <unordered_set>                // 0. include the library

int main() {
    // 1. initialize a hash set
    unordered_set<int> hashset;   
    // 2. insert a new key
    hashset.insert(3);
    hashset.insert(2);
    hashset.insert(1);
    // 3. delete a key
    hashset.erase(2);
    // 4. check if the key is in the hash set
    if (hashset.count(2) <= 0) {
        cout << "Key 2 is not in the hash set." << endl;
    }
    // 5. get the size of the hash set
    cout << "The size of hash set is: " << hashset.size() << endl; 
    // 6. iterate the hash set
    for (auto it = hashset.begin(); it != hashset.end(); ++it) {
        cout << (*it) << " ";
    }
    cout << "are in the hash set." << endl;
    // 7. clear the hash set
    hashset.clear();
    // 8. check if the hash set is empty
    if (hashset.empty()) {
        cout << "hash set is empty now!" << endl;
    }
}

LeetCode : Sort an Array 문제를 풀다가 의문점이 생겼다.

제약조건은 다음과 같다.

• 1 <= nums.length <= 5 * 10^4
• -5 * 104 <= nums[i] <= 5 * 10^4

즉, nlog(n)으로 sorting해야하는 간단한 문제다.

근데 C++의 STL인 sort는 내부적으로 quick sort를 사용한다는데 어떻게 STL을 사용해 통과했을까?

quick sort는 최악의 경우 O(N^2)이다.

당연히, merge sort 같은 O(Nlog(N))을 사용해야할 줄 알았다.첫번째 풀이 merge sort다.

class Solution {
    public:
    void mergeSort(vector<int>& nums, int s, int e) {
        if (s != e) {
            int mid = (s+e)/2;
            mergeSort(nums, s, mid);
            mergeSort(nums, mid+1, e);
            merge(nums, s, mid, e);
        }
    }
    void merge(vector<int>& nums, int s, int m, int e) {
        int i = s;
        int j = m+1;
        int k = e;
        vector<int> tmp;
        while(i <= m && j <= e) {
            if (nums[i] < nums[j]) {
                tmp.push_back(nums[i++]);
            }
            else {
                tmp.push_back(nums[j++]);
            }
        }

        while (i <= m) {
            tmp.push_back(nums[i++]);
        }
        while (j <= e) {
            tmp.push_back(nums[j++]);
        }

        for (int i = s; i <= e; i++) {
            nums[i] = tmp[i-s];
        }
    }

    vector<int> sortArray(vector<int>& nums) {
        mergeSort(nums, 0, nums.size()-1);
        return nums;
    }
};

Runtime: 133 ms

두번째 풀이, sort STL이다.

class Solution {
    public:
    vector<int> sortArray(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums;
    }
};

Runtime: 22 ms

성공했다. 심지어 시간도 훨씬 빠르다.

테스트 케이스도 1~50000의 정렬된 vector를 넣어봤다.

왜 되는 걸까?

내부적으로, sort는 단순히 quick sort가 아니라 최악의 경우를 대비한 로직이 있다고 한다.

따라서 문제풀때는 닥치고 sort쓰면 된다.

2개의 데이터를 묶을 땐 pair를 사용하면 됐다.

그런데 leetcode hard단계를 풀다 보니 3개 묶는일이 많아지더라.

주로 tuple형태로 return되는 값을 받을 때 사용한다.

  ! c++ 11버전 이상에서만 사용가능하다

#include <iostream>
#include <tuple>
using namespace std;

int main() {
    auto t = make_tuple(1, 2, 3);

    int x = get<0>(t);
    int y = get<1>(t);
    int z = get<2>(t);

    cout << x << ' ' << y << ' ' << z << '\n';    //1 2 3

    x = y = z = 0;
    cout << x << ' ' << y << ' ' << z << '\n';    //0 0 0
    
    tie(x, y, z) = t;
    cout << x << ' ' << y << ' ' << z << '\n';    //1 2 3

    x = y = z = 0;
    tie(x, y, ignore) = t;    //세번째 자리는 무시 : ignore
    cout << x << ' ' << y << ' ' << z << '\n';    //1 2 0

    return 0;
}

다음은 cpp reference url : https://en.cppreference.com/w/cpp/utility/tuple/tie

알고리즘 공부를 할때만 C++을 사용하다 보니 매번 헷갈려서 정리를 시작한다.

주로 Stack 이후에 배우지만, Stack보다 헷갈리는 함수가 많다.

특히, push_back이 아니라 push를 사용한다. (뒤로만 붙이기 때문)

그리고 emplace로 tuple같은 애들을 쉽게 넣을 수도 있더라. 꿀팁!

• front(): 큐에 있는 첫 번째 원소에 대한 참조를 반환한다. 큐가 const이면 const 참조를 반환한다. 큐가 비어 있을 때 반환되는 값은 정의되어 있지 않다.

• back(): 큐에 있는 마지막 원소에 대한 참조를 반환한다. 큐가 const이면 const 참조를 반환한다. 큐가 비어 있을 때 반환되는 값은 정의되어 있지 않다.

• push(const T& obj): obj의 복제본을 큐의 끝에 추가한다. 이 작업은 기반 컨테이너의 push_back() 멤버를 호출해서 수행된다.

• push(T&& obj): 큐의 끝에 obj를 이동해서 추가한다. 이 작업은 기반 컨테이너의 우측값 참조 매개변수 버전의 push_back() 멤버를 호출해서 수행된다.

• pop(): 큐에서 첫 번째 원소를 삭제한다.

• size(): 큐에 있는 원소의 개수를 반환한다.

• empty(): 큐에 원소가 하나도 없으면, 즉 비어 있으면 true를 반환한다.

• emplace(): emplace()에 전달된 인수로 T 생성자를 호출해 컨테이너 내부에 객체를 바로 생성하고 큐의 끝에 추가한다.

• swap(queue<T> &other_q): 현재 큐에 있는 원소들과 인수로 전달된 원소들을 교환한다. 인수는 현재 큐와 같은 타입으로 된 원소들을 담고 있어야 한다. queue 객체에 대해 같은 일을 하는 전역 함수 템플릿 swap() 같은 특수화도 있다.