Level 1. [1차] 비밀지도 지도 1과 지도 2를 각각 계산하여 합칠 필요 없이 OR 연산자로 미리 합칠 수 있다. & 1 연산으로 마지막 자리를 하나씩 가져와 벡터에 담고 transform 함수로 문자열로 변환했다. 벡터나 문자열에 값을 추가하는 도중에 메모리 재할당이 일어나지 않게 하기 위해 필요한 만큼의 크기를 미리 할당했다. #include #include #include using namespace std; vector toBinary(int n, int value) { vector v(n); for (auto rit = v.rbegin(); rit != v.rend(); ++rit) { *rit = value & 1; value >>= 1; } return v; } vector solut..

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 블룸 필터 뻐꾸기 해싱과 마찬가지로 여러 개의 해시 함수를 사용한다. 실제 값을 저장하지 않으며 키가 있는지 없는지 여부만 알 수 있다. 삽입 시 모든 해시 함수의 값에 해당하는 비트를 1로 설정한다. 확인한 모든 비트의 값이 1이면 키가 존재한다는 뜻이고, 모두 0이면 존재하지 않는다는 뜻이다. 해시 테이블에 비해 공간 효율이 매우 높지만 결정적(Deterministic) 결과 대신 부정확한 결과를 얻을 수 있다. 거짓-부정(False negative)이 없는 것은 보장하지만 거짓-긍정(False Positive)은 나올 수 있다. ※ 거짓-부정: 있는데 없다고 하는 경우 ※ 거짓-긍정: 없는데 있다고 하는 경우 블룸 필터를 사용하는 경우 데이터..

Level 1. 콜라 문제 전에 풀었던 치킨 쿠폰 문제와 비슷한 문제다. #include using namespace std; int solution(int a, int b, int n) { int answer = 0; while (a b ? n - b : 0) / (a - b) * b; }

Level 1. 크기가 작은 부분 문자열 크게 더 고민해 볼 것은 없는 문제였다. #include #include using namespace std; int solution(string t, string p) { int answer = 0; double numP = stod(p); size_t lenT = t.length(), lenP = p.length(); size_t last = lenT - lenP; for (int i = 0; i

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 뻐꾸기 해싱 크기가 같은 2개 이상의 해시 테이블을 사용한다. 각 테이블을 다른 해시 함수를 갖는다. 모든 원소는 테이블 어디든 저장될 수 있고 그 중 하나에 존재한다. 원소는 다른 테이블로 이동할 수 있다. 뻐꾸기 해싱에서의 삽입 해시 테이블1에서 공간이 비어 있으면 삽입한다. 비어 있지 않으면 기존 원소를 해시 테이블2로 이동한 후 삽입한다. 기존 원소를 옮길 공간이 비어 있지 않으면 원래 있던 원소를 해시 테이블 1로 이동한 후 삽입한다. 빈 공간이 발견되어 이동이 멈출 때까지 2부터 반복한다. 여기서 루프가 발생할 수 있고 이때는 재해싱을 수행해야 한다. 뻐꾸기 해싱의 성능 검색, 삭제는 원소의 개수와 상관 없이 테이블의 개수만큼만 확인하면..

Level 1. 삼총사 next_permutation() 함수는 현재 순열의 다음 순열을 만든다. 1, 2, 3, 4의 경우 1, 2, 4, 3 1, 3, 2, 4 1, 3, 4, 2 1, 4, 2, 3 ... 비트마스크에 순열을 적용하면 조합을 만들 수 있다. 4개 중 2개를 뽑을 경우 0, 0, 1, 1 0, 1, 0, 1 0, 1, 1, 0 1, 0, 0, 1 ... #include #include #include using namespace std; int solution(vector number) { int answer = 0; vector comb(number.size() - 3, 0); comb.insert(comb.end(), {1, 1, 1}); do { int sum = 0; auto ..