코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 일종의 래퍼이며, 기존 컨테이너의 인터페이스를 제한하여 만든 기능이 제한되거나 변형된 컨테이너이다. #include #include using namespace std; void main() { // 덱을 사용해 스택을 만들었다. deque stck1; stck1.emplace_back(1); stck1.emplace_back(2); stck1.pop_back(); // 스택에서는 지원하지 않는 기능이다. stck1.emplace_front(); // 스택 컨테이너 어댑터 stack stck2; stck2.emplace(1); stck2.emplace(2); stck2.pop(); // 컴파일 에러!! // stck2.emplace_front();..
코딩 테스트를 위한 자료 구조와 알고리즘 with C++ std::deque STL에서 제공하는 양방향 큐(Double-ended Queue) 컨테이너다. 크기가 같은 여러 개의 메모리 청크로 나누어 데이터를 저장하는 일종의 페이징 기법을 사용한다. std::vector와 달리 용량 부족으로 추가 메모리 할당 시 전체 원소를 이동시키지 않아도 된다. 내부적으로 첫 번째 청크가 아닌 중간 위치의 청크부터 원소를 저장하여 메모리 재할당을 최소화하는 등의 최적화 기법이 적용되어 있다. size()는 제공하나 capacity()는 구현 방법에 의존적이므로 제공하지 않는다. C++ 표준에서 규정하는 std::deque의 구현 조건 push_front(), pop_front(), push_back(), pop_ba..
Level 0. OX퀴즈 예전에 Stack을 활용해서 다항식 파싱했던 방법이 가물가물한데 이 문제는 항의 개수가 2개로 정해져 있어 그럴 필요까지는 없었다. istringstream을 이용해 파싱을 진행하여 해결했다. 벡터 내에서 메모리가 재할당되는 것을 막기 위해 emplace_back 대신 필요한 만큼 크기를 미리 할당하여 사용했다. #include #include #include using namespace std; vector solution(vector quiz) { size_t size = quiz.size(); vector answer(size); for (int i = 0; i < size; ++i) { istringstream iss(quiz[i]); int n1, n2, nResult;..
코딩 테스트를 위한 자료 구조와 알고리즘 with C++ 반복자는 내부적으로 포인터로 구현되어 있다. 그러므로 특정 노드 또는 원소의 주소가 바뀌면 그 주소를 갖는 반복자는 무효화될 수 있고 Crash로 이어질 수 있다. std::vector에서의 반복자 무효화 삽입 시 용량 부족으로 메모리가 재할당 된 경우 발생할 수 있다. 중간에 원소를 삽입하여 뒤 원소들의 위치가 밀린 경우 발생할 수 있다. (용량이 충분하더라도 기존 주소를 포인터가 아닌 값으로 직접 참조하는 것으로 인식하여 오류 발생) std::list에서의 반복자 무효화 삽입/삭제 시에는 원소의 이동이 필요치 않으므로 발생하지 않는다. 할당 해제된 주소를 참조하는 경우만 주의하면 된다. #include #include #include using..
2의 개수 count(v.begin(), v.end(), 2); 30세 미만인 사람의 수 count_if(v.begin(), v.end(), [](const Person &prsn) { return prsn.age < 30; }); accumulate에서 다음은 같다. accumulate(v.begin(), v.end(), 0); // 전달된 Lambda 함수에서 n은 현재 까지의 합, e는 현재 원소를 뜻한다. accumulate(v.begin(), v.end(), 0, [](const int n, const int e) { return n + e; }); 2차원 벡터에서 8의 개수 vv의 원소 자료형이 vector이기 때문에 Lambda 식 함수 op의 2번째 인자 형식도 맞춰주어야 한다. // 현재..
Level 0. 안전지대 폭탄과 인접한 칸들만 위험 지역으로 표시하기 때문에 깊이 1까지만 수행하는 BFS라고 볼 수도 있다. 나는 원소에 접근할 때 범위를 검사하기보다는 vector::at() 함수와 예외 처리를 활용했다. 폭탄이 있을 경우 인접 칸들을 위험 지역(2)으로 표시하고 마지막에 안전 지역(0)의 개수를 세어 해결했다. #include #include #include #include using namespace std; void setDanger(vector& board, int i, int j) { for (int k = i - 1; k