J.Althea

..9/17 18:00 쯤에 카카오톡이 와서 이메일을 확인해봤다. 작년에 보았을 때는 2.5솔 정도 했었는데, 이번에는 4솔로 마무리하게 되었다. (1, 2, 3, 4 풀고, 5번 푸는 도중에 테스트 종료) 내가 느낀 문제별로 필요한 지식 및 아이디어는 다음과 같다. 1번 문제 - 문자열 처리 (+ 정규식) -> 문제에서 시키는 대로 차례대로 조건에 맞게 문자열을 필터링하였다. 2번 문제 - 적절한 자료구조 사용 능력 (완전탐색 / 해시) -> map을 사용하여 해당 값이 들어온 횟수를 세고, 큰 순서대로 담았다.     데이터의 개수가 많지 않기 때문에, 빈틈없이 잘 처리하는게 중요한 것 같았다. 3번 문제 - 적절한 자료구조 사용 능력 + 이분 탐색 응용 (트라이?) -> (1) 다차원 배열(마지막 차원은 동적 배열)을 사용하여 데이터를 담아 정렬한 뒤,     (2) lower_bound를 사용하여 조건에 맞는 데이터들을 가져왔다.     예를 들어서, "java, backend, junior, pizza, 100" 라는 데이터를     h[1][2][1][1].push_back(100); ~ h[0][0][0][0].push_back(100); 까지 저장했고,      "python, frontend, senior, pizza, 200" 라는 데이터는     h[2][1][2][1].push_back(200); ~ h[0][0][0][0].push_back(200); 까지 저장했다.     문제에 조건에 따라, "언어(3종류), 직무(2종류), 경력(2종류), 음식(2종류), 점수" 의      각 항목마다 정해진 개수가 있었는데,      이때, "- and - and - and - and 100" 이라는 형태로 쿼리가 들어올 수 있으므로  ...

decltype은 알고자 하는 변수 식의 타입으로 치환하는 역할을 한다. 예를 들어서 int a = 10; decltype(a) b = 3; b의 타입은 a의 타입인 int로 된다. 이로써, 정확하게 타입 그대로를 전달할 수 있게 된다. 또, 타입의 결과를 알 수 없을 때도 사용한다. template <typename T, typename U> void add(T t, U u, decltype(t + u) *result) {     *result = t + u; } (1) double t, double u => double * result (2) double t, int u => double * result (3) int t, int u => int * result

예를 들어서, while (arrSum[end] - arrSum[start - 1] < s) end++; 라는 코드가 있다고 하자. 반복문 안에서 end를 증가시키기 때문에, 배열의 범위를 벗어나지 않는 선에서 검사해야 한다. 인덱스에 대한 처리를 while 내부에 쓰거나, while의 조건문에 쓰는 방법 등이 있지만 아래처럼 범위를 검사하는 부분을 가장 먼저 쓰면 좋다. while (end < n && arrSum[end] - arrSum[start - 1] < s) end++; 이렇게 하면, if 문의 뒷 부분(arrSum[end] - arrSum[start - 1] < s)을 검사하기 이전에 앞 부분(end < n)을 검사하고 빠져나오게 된다. 왜냐하면, and 조건은 if (true && true) 인접한 두 조건을 모두 만족시켜야 하기 때문에 앞에서 하나라도 거짓인 명제를 만나면, 뒤를 볼 필요없이 빠져나오게 되기 때문이다.

//예외를 반환하지 않는다. int func1(int a, int b, int c) noexcept {     ... } //예외를 반환할 수 있다. int func2(int a, int b, int c) noexcept(false) {     ... } 예외처리에 관해서 한정자 noexcept를 작성하면 얻는 이점은 다음과 같다. (1) 예외 처리 여부를 바로 알 수 있다. (2) Strong exception guarantee (강한 예외 보증)     copy semantics가 아닌 move semantics로 처리한다. (3) Performance improvement (성능 향상)     해당 함수가 예외처리를 무조건적으로 하지 않는다고 가정하므로     예외를 반환할 수 있는 상황에 대한 고려를 하지 않는다. (여분공간X)

C++11 이후부터 이동 생성자라는 것이 생겼는데, 사용법을 간단하게 살펴보면 //이동 생성자 Test(Test &&test) {     data = test.data;     test.data = nullptr;    //이동 후, 다시는 기존의 변수를 사용하지 않을 목적. } //복사 생성자 Test(const Test &test) {     ... } 이런식으로 참조자(&)를 사용해서 클래스 내부에 정의해줄 수 있다. 불필요한 복사와 임시 변수를 최대한 없애기 위한 과정에서 탄생하였다고 한다. 더 이상 사용하지 않을 변수를 포인터를 활용하여 바꿔치기 한다. (소유권 이전) 클래스에서 생성자를 정의할 때, 복사 생성자도 같이 정의하는 경우가 많다. STL에 있는 자료구조에 이 사용자 정의한 클래스 객체들을 초기화할 때를 생각하면 vector<Test> v; v.push_back(test1); v.push_back(test2); ... 이런식으로 넣게 되는데, 이 때 push하는 과정에서 v의 사이즈를 필요할 때마다 늘리므로 기존의 데이터를 옆 칸으로 복사하는 과정이 필요하다. 그러나 이동 생성자가 정의되어 있으므로 이 과정에서 복사가 일어나지 않게 되어 낭비를 막는다. 이러한 취지에서 move()라는 함수가 있다. move()는 인자를 받아서 'r-value 참조자' 형태로 바꿔주는 역할을 하는데, ('r-value 참조자'는 위에서 이동 생성자를 정의할 때, 매개변수로 작성하였던 모습이다.) 이 함수를 이용하면, 불필요한 낭비없이 초기화가 가능하다. v.push_back(std::move(test));    //더 이상 test를 사용하지 않음을 유의 여기에 더해 한번 더 최적화를 할 수 있는 방법이 있다. push_back() 대신 emplace_back()...

문득, 트리 구조(Tree)로 이루어진 set과 해쉬 테이블(Hash Table)로 이루어진 unordered_set의 속도 차이를 손쉽게 경험할 수 있을 것 같아서 기존의 코드를 수정하고 제출해보았다. * 수정 전 실행 결과(set을 이용) : * 수정 후 실행 결과(unordered_set을 이용) :  모든 테스트 케이스에 대해서 유의미한 속도 향상을 보였다. 아래는 수정한 코드이다. https://github.com/JAlthea/Algorithm/blob/master/BFS/Programmers%20%EB%B8%94%EB%A1%9D%20%EC%9D%B4%EB%8F%99%ED%95%98%EA%B8%B0.cpp #include <vector> #include <queue> #include <unordered_set> #include <algorithm> using namespace std; struct hashFuction {     size_t operator()(const vector<int> &a) const {         int resultA = 0;         int digit = 1;         for (int i=0; i<4; i++)         {             resultA += a[i] * digit;             digit *= 10;         }         return resultA;     } ...

연속된 데이터를 출력문에 대한 코드를 작성하다보면, 마지막 출력의 경우에는 줄바꿈을 하고 싶을 경우가 있다. for (int i=0; i<n; i++)     if (i == n - 1)         cout << a[i] << "\n";     else         cout << a[i] << " "; 위와 같이 작성하는 경우가 많은데, 이것을 for (int i=0; i<n; i++)     cout << a[i] + " \n "[i==n-1]; 이렇게 바꿔서 작성할 수 있다. const char* tmp = " \n"; 형태로 볼 수 있고,  tmp[0], tmp[1]을 사용하듯이 " \n"[0], " \n"[1]로 보는 것이다. 특정 규칙을 갖는 문자열을 작성해두고, 인덱스를 넣어서 활용하는 방법도 있다. 예) "122333444455555..."[n%k];