📌 컨테이너 어댑터
: 기존 컨테이너의 인터페이스를 제한하여 만든 기능이 제한되거나 변형된 컨테이너
✔️ 기존 컨테이너를 감싸는 래퍼를 제공하는 몇 가지 이유
- 코드에 좀 더 의미를 부여하고 싶은 경우
- 의도하지 않는 함수를 실수로 사용하지 못하도록 제한하고 싶은 경우
- 특별한 인터페이스를 새롭게 제공하고 싶은 경우
❓ 스택 (stack)
: 데이터 처리와 보관을 위해 LIFO(Last In Fist Out, 후입선출) 구조를 사용한다.
✔️ 기능적 측면 : 컨테이너의 한쪽 끝에서만 데이터를 삽입하거나 삭제할 수 있으며, 한쪽 끝이 아닌 위치에 있는 데이터는 접근하거나 변경할 수 없다.
- 벡터나 덱은 이러한 기능을 기본적으로 지원하기 때문에 스택을 구현하기 위한 용도로 사용할 수 있다.
❗️ 벡터나 덱을 직접 스택처럼 사용하기에는 약간의 문제가 있다.
std::deque<int> stk1;
stk1.push_back(1); // 스택에 1 추가: {1}
stk1.push_back(2); // 스택에 2 추가: {1, 2}
stk1.pop_back(); // 스택에서 맨 위 원소 제거: {1}
stk1.push_front(0); // 원래 스택에서는 지원하지 않는 동작입니다. : {0, 1}
std::stack<int> stk2;
stk2.push(1); // 스택에 1 추가: {1}
stk2.push(2); // 스택에 2 추가: {1, 2}
stk2.pop(); // 스택에서 맨 위 원소 제거: {1}
stk2.push_front(0); // 컴파일 에러!-
std::deque을 사용하여 스택 객체 stk1을 만들어 사용
-> 이 경우 push_front() 함수처럼 스택에서 사용하면 안 되는 명령 코드를 작성하는 것을 막을 수 없다.
-> push_back()과 pop_back() 같은 함수 이름은 자료 구조 맨 뒤에 데이터를 추가하거나 삭제한다는 의미인데, 스택으로 사용할 때에는 어느 위치에 데이터가 저장되는지는 알 필요가 없다. -
std::stack을 사용하여 작성된 소스 코드는 어떤 작업을 하고 있는지 좀 더 직관적으로 알 수 있다.
-> 의도하지 않은 동작을 지시하거나 실수로 코드를 잘못 작성하는 경우가 발생하지 않게 된다.
1. std::stack
: std::deque으로 만든 간단한 래퍼 (기본 컨테이너 : std::deque)
: 스택 자료 구조에서 꼭 필요한 인터페이스만을 제공
✔️ 관련 함수 : empty(), size(), top(), push(), pop(), emplace()
-> push() : 기본 컨테이너의 push_back() 함수를 사용하여 구현
-> pop() : pop_back() 함수를 사용하여 구현
-> top() : 기본 컨테이너의 back() 함수 사용 (스택에서 맨 위에 있는 데이터가 덱 구조에서는 맨 끝에 있는 원소이기 때문이다.)
이처럼 기본 컨테이너의 한쪽 끝에서만 원소의 추가 및 삭제를 수행함으로써 LIFO 특징을 제공한다.
✔️ 스택의 모든 연산 시간 복잡도 : O(1)
- 스택에서 기본 컨테이너로 함수 호출을 전달하는 과정은 컴파일러의 최적화에 의해 모두 인라인(inline) 형식으로 호출될 수 있어서 여기서 발생하는 오버헤드는 없다.
2. std::queue
: FIFO(First In First Out, 선입선출) 구조
✔️ 스택과 비슷한 형태의 함수를 지원하며, LIFO 대신 FIFO를 지원하기 위해 그 의미와 동작이 조금 다르게 정의되어 있다.
-> push() : std::stack에서의 push_back()
-> pop() : pop_front()
-> 원소를 제거하는 pop() 함수와 달리, 단순히 양 끝단에 있는 원소에 접근하고 싶을 때에는 front() 또는 back() 함수를 사용한다.
std::queue<int> q;
q.push(1); // 맨 뒤에 1을 추가: {1}
q.push(2); // 맨 뒤에 2를 추가: {1, 2}
q.push(3); // 맨 뒤에 3을 추가: {1, 2, 3}
q.pop(); // 맨 앞 원소를 제거: {2, 3}
q.push(4); // 맨 뒤에 4를 추가: {2, 3, 4}✔️ 앞서 사용한 모든 함수의 시간 복잡도 : O(1)
3. std::priority_queue
: 우선순위 큐(priority queue)는 힙(heap)이라고 부르는 매우 유용한 구조를 제공
✔️ 힙
: 컨테이너에서 가장 작은(또는 가장 큰) 원소에 빠르게 접근할 수 있는 자료 구조
-> 최소/최대 원소에 접근하는 동작은 O(1)의 시간 복잡도를 가진다.
-> 원소 삽입은 O(log n) 시간 복잡도로 동작하며, 원소 제거는 최소/최대 원소에 대해서만 가능하다.
📌 백준 문제 풀이
📌 24-1 게임 개발 프로젝트 기획안 작성
<아이디어 브레인스토밍 및 Backlogs & Sprint 작성>
<게임 기획안 목차>
<회의 진행도>
✔️ 현재 게임 개발 진행중이므로 자세한 게임 기획안은 올리지 않음을 알립니다.
