코딩 테스트를 위한 자료 구조와 알고리즘 with C++ std::array의 문제점 Compile time에 크기가 정해져야 하며 실행 도중 변경할 수 없다. 크기가 고정되어 있어 원소의 추가, 삭제가 불가능하다. 항상 스택 영역을 사용한다. std::vector 공간이 부족할 경우 크기가 동적으로 늘어난다. - 보통 2배 크기와 용량이 별도로 존재한다. 두 벡터의 크기가 달라도 비교 연산이 지원된다. std::vector의 성능 맨 뒤에 삽입 시 크기가 충분하면 O(1), 부족하면 모든 원소를 새로운 메모리에 복사해야 하므로 O(n) 중간에 원소를 삽입하는 경우 O(n) std::vector의 원소 삽입 의사 코드 push_back(val): if size < capacity data[size++] ..

Level 0. 최빈값 구하기 첫 번째 풀이 map 내의 키가 정렬된 상태를 유지할 필요가 없기 때문에 레드-블랙 트리를 사용하는 map보다는 해시 테이블을 사용하는 unordered_map을 사용했다. 개수가 최대인 pair를 찾고 최댓값이 여러 개인지 확인하여 해결했다. 최댓값을 찾는 부분에서 O(n), 최댓값과 같은 값이 찾는 부분에서 O(n)이 소요되기 때문에 원소들을 2번 순회해야 한다. #include #include #include #include using namespace std; int solution(vector array) { int answer = 0; unordered_map umap; for (int num : array) ++umap[num]; unordered_map::it..

Level 0. 다음에 올 숫자 #include #include using namespace std; int solution(vector common) { int diff = common[1] - common[0]; return (diff == common[2] - common[1]) ? common.back() + diff : common.back() * (common[1] / common[0]); } 특별한 것은 없었던 문제다. 첫 번째, 두 번째, 세 번째 원소를 확인해 등차수열인지 확인하고 마지막 원소에 등차를 더하거나 등비를 곱해 해결한다.

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ #include #include #include using namespace std; template class dynamic_array { private: T* data; size_t n; public: dynamic_array(size_t n) : data(new T[n]), n(n) {} dynamic_array(const dynamic_array& other) { n = other.n; data = new T[n]; for (int i = 0; i < n; ++i) data[i] = other[i]; } friend dynamic_array operator+(const dynamic_array& da1, const dynamic_array&..

for_each 원소를 수정하지 않는 경우 사용(레퍼런스로 원소를 받을 경우 수정 가능하나 권장하지 않음) 모든 원소를 순차적으로 접근함을 보장 transform 원소를 수정하거나 다른 곳으로 적용할 경우 사용 모든 원소가 순차적으로 접근됨을 보장하지 않음 #include #include using namespace std; void main() { string s = "Hello World!"; // s의 모든 문자를 1씩 증가시켜 s에 다시 저장한다. transform(s.begin(), s.end(), s.begin(), [](char c) { return ++c; }); // s의 모든 문자를 순서대로 출력한다. for_each(s.begin(), s.end(), [](char c) { cout

Level 0. 연속된 수의 합 #include #include using namespace std; vector solution(int num, int total) { vector answer(num, total / num - (num - 1) / 2); for (int i = 0; i < num; ++i) answer[i] += i; return answer; } 시작 = 평균 - (개수 - 1) / 2 시작 값을 num 개수만큼 만들고 index 별로 증가시켜준다.