vector는 가변 길이 배열이다.
그래서 pop_front(), push_front()와 같은 동작이 느리다.
선형 시간 복잡도를 가지게된다. ( O(n) )
이러한 단점을 극복하기 위한 것이 std::deque이다.
Double Ended Queue
덱의 구조
필요조건 ❗
-
push_front(), pop_front(), push_back(), pop_back() 동작이 O(1) 시간 복잡도로 동작해야한다.
-
모든 원소에 대해 임의 접근 동작이 O(1) 시간복잡도로 동작해야한다.
-
덱 중간에서 원소 삽입 삭제 또는 삭제는 O(n) 시간복잡도로 동작해야하며, 실제로는 최대 n/2 단계로 동작한다. (여기서 n은 덱의 크기이다)
덱은 양방향으로 매우 빠르게 확장이 가능해야하고,
모든 원소에 임의 접근을 제공해야한다.
따라서 vector와 비슷하지만 앞/뒤 모두 확장할 수 있다.
그래서 내가 생각한 메모리 구조인데
실제 std::deque 도식화를 검색해보면은
이런식으로 메모리 블럭을 만든다고 설명을 한다..
deque는 단일 메모리 청크를 사용하지 않는다.
대신 크기가 같은 여러 개의 메모리 청크를 사용하여 데이터를 저장한다.
std::deque는 덱의 맨 앞에 원소를 추가를 할 경우 첫반째 메모리 청크에 여유 공간이 없다면 새로운 청크를 할당한다.
(이런식으로 블록? 청크를 이어 붙이는 거같다)
메모리 재할당 최소화 ❗
첫번째 메모리 청크에 여유 공간이 없을 경우 메모리 재할당을 하는데
이런 재할당을 최소화 할려면은 첫번째 청크부터 원소를 추가를 하지않고 중간 위치의 청크부터 원소를 저장할 수도 있다.
이러한 방식으로 사용하면 일정횟수의 push_front함수에 대해 메모리 재할당을 피할 수 있다.
삽입 삭제시 ❗❗
원소 삽입과 삭제시 n/2 단계를 허용을 하는데,
이는 벡터에서 삽입/삭제시 발생하는 연산이다. (O(n))
다만 덱은 어느 방향으로든 빠르게 확장이 가능하기 때문에
원소 삽입시 나머지 원소를 항상 오른쪽으로 이동해야만 하는 것은 아니다.
원소 삽입 위치에서 가장 가까운 끝 쪽으로 나머지 원소를 이동해도 된다.
특정 위치에서 가장 가까운 끝은 컨테이너 내부의 삽입 위치에서 n/2 이상 떨어져 있을 수 없기 때문에 최대
n/2단계의 시간 복잡도를 가지는 것이다.
https://velog.io/@jinh2352/stddeque-double-ended-queue-%EC%96%91%EB%B0%A9%ED%96%A5-%ED%81%90
이그림 보니까 삽입시 최대 n/2라는 말이 조금은 이해가 간다.
std::deque의 삽입/삭제는 std::vector와 시간복잡도는 비슷하지만
실제로 std::deque가 조금 더 빠르다.
std::vector와 마찬가지로 std::deque또한
"사용자 정의 할당자" 를 지정할 수 있다.
할당기 및 알고리즘
https://dosundosun.tistory.com/41
메모리 할당자
https://wikidocs.net/29955
카드 게임 시뮬레이션 구현
한 게임에 4명의 플레이어가 있고, 각각의 임의의 카드 13장을 가지고 게임을 시작합니다.
그리고 각 플레이어의 카드에서 임의의 카드 한 장을 선택을 합니다. 그렇게하면 비교할 카드가 4장이 생기게 되고, 이중 서로 중복되는 카드쌍은 제거 합니다.
세장의 카드가 같을 경우에는 이 중 임의로 두장만 제거합니다.
네장의 커드가 모두 같으면 네 장을 모두 제거합니다.
남겨진 카드는 카드를 낸 플레이어가 다시 가져갑니다.
일치하는 카드쌍이 없으면 플레이어의 카드 세트를 섞을 수 있습니다.
이제 이과정을 어느 한 사람의 카드가 다 없어 질 때까지 반복합니다.
제일먼저 자신의 카드를 모두 없앤 사람이 게임의 승자입니다.
최종 승리자 출력하고 종료합니다.
알고 가야할 개념
-
- std::chrono
https://kukuta.tistory.com/410
뭔가 시간 재는 라이브러리?
- std::chrono
-
- std::sstream
https://deukyu.tistory.com/48
문자열 분석할 때 좋은 라이브러리?
- std::sstream
-
- ostringstream
https://doitnow-man.tistory.com/entry/C-%EA%B0%9C%EB%B0%9C%EC%9E%90%EB%90%98%EA%B8%B0-6-istringstream-ostringstream-stringstream-%EC%82%AC%EC%9A%A9%EB%B2%95
문자열 분석 및 저장할 때 좋은 라이브러리?
- ostringstream
2, 3번은 #include < sstream>를 include 하면 사용 가능하다.
그중에서도 ostringstream을 잠깐 볼 것인데
뭐 대충 이런 느낌으로 사용을 한다.
- vector 초기화 하는 방법
https://www.techiedelight.com/ko/initialize-vector-cpp/
이런식으로 {} begin(), begin() + 2} 이런식으로 가능하다.
#include <iostream>
#include <vector>
#include <array>
#include <sstream>
#include <algorithm>
#include <random>
#include <chrono>
// 22/11/04
// p63 카드 게임 시뮬레이션
struct Card
{
int _number;
enum SUIT
{
HEART,
SPADE,
CLUB,
DIAMOND
} suit;
std::string to_string() const
{
std::ostringstream os;
if (_number > 1 && _number <= 10)
os << _number;
else
{
switch (_number)
{
case 1:
os << "Ace";
break;
case 11:
os << "Jack";
break;
case 12:
os << "Quene";
break;
case 13:
os << "King";
break;
default:
return "Invalide Card";
}
}
os << " of ";
switch (suit)
{
case SUIT::HEART:
os << "hearts";
break;
case SUIT::SPADE:
os << "spades";
break;
case SUIT::CLUB:
os << "clubs";
break;
case SUIT::DIAMOND:
os << "diamonds";
break;
default:
return "";
}
return os.str();
}
};
struct Game
{
std::array<Card, 52> _deck;
std::vector<Card> player1, player2, player3, player4;
void BuildDeck()
{
for (int i = 0; i < 13; ++i)
_deck[i] = Card {i + 1, Card::HEART};
for (int i = 0; i < 13; ++i)
_deck[i + 13] = Card{ i + 1, Card::SPADE };
for (int i = 0; i < 13; ++i)
_deck[i + 26] = Card{ i + 1, Card::CLUB };
for (int i = 0; i < 13; ++i)
_deck[i + 39] = Card{ i + 1, Card::DIAMOND };
}
void DealCards()
{
unsigned int seed = std::chrono::system_clock::now().time_since_epoch().count();
std::shuffle(_deck.begin(), _deck.end(), std::default_random_engine(seed));
player1 = { _deck.begin(), _deck.begin() + 13 };
player2 = { _deck.begin() + 13, _deck.begin() + 26 };
player3 = { _deck.begin() + 26, _deck.begin() + 39 };
player4 = { _deck.begin() + 39, _deck.end()};
}
bool CompareAndRemove(std::vector<Card>& p1, std::vector<Card>& p2)
{
if (p1.back()._number == p2.back()._number)
{
p1.pop_back();
p2.pop_back();
return true;
}
return false;
}
void PlayOneRound()
{
if (CompareAndRemove(player1, player2))
{
CompareAndRemove(player3, player4);
return;
}
else if (CompareAndRemove(player1, player3))
{
CompareAndRemove(player2, player4);
}
else if (CompareAndRemove(player1, player4))
{
CompareAndRemove(player2, player3);
return;
}
else if (CompareAndRemove(player2, player3))
{
return;
}
else if (CompareAndRemove(player2, player4))
{
return;
}
else if (CompareAndRemove(player3, player4))
{
return;
}
unsigned int seed = std::chrono::system_clock::now().time_since_epoch().count();
std::shuffle(player1.begin(), player1.end(), std::default_random_engine(seed));
std::shuffle(player2.begin(), player2.end(), std::default_random_engine(seed));
std::shuffle(player3.begin(), player3.end(), std::default_random_engine(seed));
std::shuffle(player4.begin(), player4.end(), std::default_random_engine(seed));
}
bool IsGameComplete() const
{
return player1.empty() || player2.empty() || player3.empty() || player4.empty();
}
void PlayGame()
{
int round = 1;
while (not IsGameComplete())
{
std::cout << "Round : " << round << std::endl;
PlayOneRound();
std::cout << "Round : " << round << " End" << std::endl;
round = round + 1;
}
}
int GetWinner() const
{
if (player1.empty())
return 1;
if (player2.empty())
return 2;
if (player3.empty())
return 3;
if (player4.empty())
return 4;
}
};
int main()
{
Game newGame;
newGame.BuildDeck();
newGame.DealCards();
newGame.PlayGame();
auto winner = newGame.GetWinner();
std::cout << winner << "번 플레이어가 이겼습니다!" << std::endl;
return 0;
}배운거
-
deque 개념
-
std::chrono : 뭐하는 건지
-
std::sstream : 뭐하는 건지
-
std:: ostringstream : 뭐하는 건지
이해 안가는 부분
PlayOneRound()함수 에서 if 조건문 부분이 이해안감
한턴 게임하고 섞는거는 이해가는데
