[코딩 테스트를 위한 자료 구조와 알고리즘 with C++] 1장 정리

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ - YES24

코딩 테스트를 위한 자료 구조와 알고리즘 with C++ - YES24

---

🔔 1장 리스트, 스택, 큐

 

1.1 들어가며

응용 프로그램 설계시 중요 고려 항목 중 하나는 데이터 관리.

데이터를 메모리에 저장하기 위해 여러 자료 구조를 사용할 수 있음

응용 프로그램에서 필요한 기능을 구현하고, 동작 성능과 안정성을 확보하려면 적절한 "자료 구조" 선택해야 함

 

1.2 연속된 자료 구조와 연결된 자료 구조

데이터를 처리하기에 앞서 데이터를 어떻게 저장할 것인가를 결정

👉 데이터를 이용해 수행할 작업의 종류와 작업 빈도에 따라 달라진다.

응용 프로그램이 제대로 동작, 지연 시간, 사용 메모리 등 고려해 최선의 성능을 제공하도록 구현 방법 선택

 

적합한 지표 : 시간 복잡도(특정 작업을 수행하는데 걸리는 시간을 데이터 크기에 대한 수식으로 표현)

 

1) 연속된 자료 구조

① 특징 

- 모든 원소를 단일 메모리 청크에 저장

- 각각의 원소는 모두 같은 타입, 같은 크기의 메모리를 사용 

* 주소 계산 : BA(Base Address) + sizeof(type)

- 위 수식을 사용해 모든 원소에 곧바로 접근 가능 => 데이터 접근 시간이 항상 일정 O(1)

 

② 배열의 유형

- 정적 배열 : 선언된 블록이 끝나면 소멸

* 스택 메모리 영역에 할당되어 함수 벗어날 때 자동 해제

int arr[size];

- 동적 배열  : 프로그래머가 생성 시점/해제 시점 자유롭게 결정

int* arr = new int[size];

* 힙 영역에 할당되어 사용자가 직접 해제

 

③ 캐시 지역성

- 배열 같은 연속된 자료구조는 서로 인접해 있어서 하나의 원소 접근 시 다른 원소 몇개도 함께 캐시 가져옴

- 그러므로 주변 원소 접근시 해당 원소를 캐시에서 가져오기 때문에 매우 빠르게 작동 (캐시 지역성)

- 배열에서 모든 원소에 순차적으로 접근하는 경우 인접 원소를 캐시에서 바로 참조 가능하기에 

  배열이 캐시 지역성이 좋다 라고 말할 수 있다.

* 캐시 지역성이 연산의 점근전 시간 복잡도 계산에 영향은 주지 않음

 

2) 연결된 자료 구조

① 개념 : 노드라고 하는 여러 개의 메모리 청크에 데이터를 저장, 서로 다른 메모리 위치에 데이터가 저장됨

연결 리스트

- 연결 리스트의 각 노드는 저장할 데이터, 다음 노드를 가르키는 포인터를 가짐

- 맨 마지막 노드는 자료 구조의 끝을 나타내는 NULL을 가짐

- 특정 원소에 접근하기 위해서는 헤드 부터 원하는 원소에 도달할 때까지 next 포인터를 따라 이동해야함

👉 i 번째 원소에 접근 하려면 연결 리스트 내부를 i번 이동하는 작업 필요 O(n)

 

- 원소의 삽입과 삭제를 매우 빠르게 수행 가능

1. 삽입
1) 이전 포인터 제거
2) 이전 노드의 next 포인터가 새로 삽입한 노드 가르키도록 지정
3) 삽입한 노드의 next 포인터가 다음 노드를 가르키도록 지정

- 캐시 지역성은 좋지 않다. 따라서 순차 접근에서는 배열보다 성능이 떨어짐

 

3) 연속된 자료 구조 vs 연결된 자료 구조

연속된 자료구조	연결된 자료구조
모든 데이터 연속적으로 저장	데이터가 메모리 곳곳에 흩어짐
임의 원소에 즉각 접근 가능	임의 원소 접근 시 선형 시간 복잡도 가짐
캐시 지역성으로 데이터 순회 매우 빠름	캐시 지역성 x 데이터 순회 느림
데이터 저장을 위해 데이터 크기만큼 메모리 사용	노드에서 포인터 저장을 위해 여분 메모리 사용

파라미터	배열	연결리스트
임의 접근	O(1)	O(n)
맨 뒤 원소 삽입	O(1)	O(1)
중간 원소 삽입	O(n)	O(n)
캐시 지역성	있음	없음

 

4) C 스타일 배열 제약 사항

- 메모리 할당과 해제를 수동으로 처리해야함

- [] 연산자에서 배열보다 큰 원소 참조하는걸 검사 못함(세그멘테이션 결함, 메모리 손상 우려)

- 배열 중첩 사용시 문법이 너무너무 복잡

- 깊은 복사가 기본적으로 동작 안함

 

👉 C++ 에서 std::array 사용 !

 

1.3  std::array 

- std::array는 메모리를 자동으로 할당하고 해제함

#include <iostream>
#include <array>
using namespace std;

int main() {
    array<int, 10> arr1;
    arr1[0] = 1;
    cout << "arr1 첫 원소 : " << arr1[0] << endl;
    
    array<int, 4> arr2 = { 1, 2, 3, 4 };
    cout << "arr2의 모든 원소 : ";
    for (int i = 0; i < arr2.size(); i++) {
        cout << arr2[i] << " ";
    }
}

- C 스타일과 마찬가지로 배열 원소에 접근할 수 있는 []연산자 제공

- [] 연산자 사용시 인덱스 넘어가면 디버그 자체가 안됨 

 

- 따라서 at(index) 함수 이용하여 인덱스 값이 유효하지 않으면 out_of_range 예외 발생 시킴 

- at() 연산자가 [] 보단 느리지만 잘 이용하면 예외를 적절하게 처리 가능

array<int, 4> arr2 = { 1, 2, 3, 4 };
try {
    cout << arr2.at(4) << endl;
}
catch (const out_of_range& ex) {
    cout << ex.what() << endl;  // invalid array<T, N> subscript
}

 

- array 객체를 다른 함수에 전달하는 방식은 값 또는 참조로 전달 가능

void print(array<int, 5> arr)
{
	for(auto ele: arr)
    	cout << ele << " ";
}

array<int, 5> arr = {1,2,3,4,5};
print(arr);

위 예제는 매개변수로 고정된 배열크기만 가능하다.

동적인 크기로 print() 메서드를 선언하고 싶다면 template를 이용한다.

template <size_t N>
void print(const array<int,N>& arr);

위와 같이 선언 했을 시, 자동으로 깊은 복사가 동작한다. (배열의 주소값을 가져오기 때문에)

 

 

- 배열의 원소에 차례대로 접근하는 연산 (int i=0~머시기 쓰는것보다 편리함)

array<int, 5> arr = {1,2,3,4,5};
for(auto element : arr) {
    cout << element << " ";
}

- array 연산자는 begin()과 end() 이름의 멤버 함수를 제공 

• begin() : 가장 첫 번째 원소의 위치
• end() : 가장 마지막 원소의 위치(정확하게는 마지막 원소 다음 위치)

- 범위 기반 for반복문은 begin() 위치부터 ++연산자를 통해 end()위치에 도달하면 종료됨

- 반복자(iterator)를 사용하면 소스 코드의 재사용성, 유지 보수, 가독성 측면에서 이득

* start()~end()(포함x)전까지 

for (auto it = arr.begin(); it != arr.end(); it++) {
        auto element = (*it)++;
        cout << element << " ";
}

- const_iterator 또는 reverse_iterator 같은 형태의 반복자도 사용이 가능하다.

함수	설명
front()	배열의 첫 번째 원소에 대한 참조를 반환
back()	배열의 마지막 원소에 대한 참조 반환
data()	배열 객체 내부에서 실제 데이터 메모리 버퍼를 가르키는 포인터 반환

cout << *(arr.data()+1) << endl; // 이와 같은 형태로 사용

- array는 깊은 비교를 위한 관계 연산자와 깊은 복사를 위한 복사 할당 연산자를 지원

* c스타일에서는 배열 원소 값을 비교하는 게 아닌 포인터 주소 값을 비교하기에 실용적이지 않다.

깊은 비교 vs 얕은 비교
1. 얕은 비교는  기본 타입 데이터의 경우 값이 동일한지만 비교하고, 객체의 경우 참조만 비교한다.
그래서 객체를 관계연산자(==)로 비교할 때 값이 같더라도 참조값이 다르기 때문에 같지 않다고 나옴
2. 깊은 비교는 객체의 경우에도 값으로 비교한다. 

 

1) 연습 문제 1 : 동적 크기 배열 구현하기

C++ 개념을 다 알지 못한채 보다보니 코드가 너무 어려웠다... 템플릿 관련해서 공부하는 걸 추천

#include <iostream>
#include <algorithm>
#include <sstream>
#include <array>
using namespace std;

template <typename T>
class dynamic_array {
	T* data;
	size_t n;
	
public:
	// 배열 크기를 인자로 받는 생성자
	dynamic_array(int n) {
		this->n = n;
		data = new T[n];
	}
	// 복사 생성자
	dynamic_array(const dynamic_array<T>& other) {
		n = other.n;
		data = new T[n];
		for (int i = 0; i < n; i++) {
			data[i] = other[i];
		}
	}
	T& operator[](int index) { // [] 연산자를 만드는 함수
		return data[index];
	}
	const T& operator[](int index) const { 
		return data[index];
	}
    // 두번씩 선언한 이유는 const 유형이 아닌 객체와 const 유형인 객체를 둘다 처리하기 위해
    
	T& at(int index) {
		if (index < n) return data[index];
		throw "Index out of range";
	}
	size_t size() const {
		return n;
	}
	~dynamic_array() {
		delete[] data;
	}
	T* begin() { return data; }
	const T* begin() const { return data; }
	T* end() { return data + n; }
	const T* end() const { return data + n; }

	friend dynamic_array<T> operator+(const dynamic_array<T>& arr1, dynamic_array<T>& arr2) {
		dynamic_array<T> result(arr1.size() + arr2.size());
		copy(arr1.begin(), arr1.end(), result.begin());
		copy(arr2.begin(), arr2.end(), result.begin() + arr1.size());
		return result;
	}

	string to_string(const std::string& sep = ", ") {
		if (n == 0) return "";
		ostringstream os;
		os << data[0];
		for (int i = 1; i < n; i++) {
			os << sep << data[i];
		}
		return os.str();
	}
};

struct student {
	string name;
	int standard;
};

ostream& operator<<(ostream& os, const student& s) {
	return (os << "[" << s.name << ", " << s.standard << "]");
}

int main() {
	int nStudnets;
	cout << "1반 학생 수를 입력하세요: ";
	cin >> nStudnets;

	dynamic_array<student> class1(nStudnets);
	for (int i = 0; i < nStudnets; i++) {
		string name;
		int standard;
		cout << i + 1 << "번째 학생 이름과 나이를 입력하세요: ";
		cin >> name >> standard;
		class1[i] = student{ name, standard };
	}
	try {
		class1.at(nStudnets) = student{ "John", 8 }; // 예외 발생
	}
	catch (...) {
		cout << "예외 발생" << endl;
	}

	auto class2 = class1;
	cout << class2.to_string() << endl;
	auto class3 = class1 + class2;
	cout << "class3 : " << class3.to_string() << endl;

	return 0;

}

 

2) 연습 문제 2: 빠르고 범용적인 데이터 저장 컨테이너 만들기

// 이건 코드 내용 이해를 못하겠어서 생략 

 

1.4 std::vector

- C++ array의 단점 : array 크기가 컴파일 시간에 결정되는 함수여야 함, 크기 고정, 항상 스택메모리 사용

- 위 단점을 해결한 방법이 vector 이다.

1) 가변 크기 배열

#include <vector>
#include <iostream>
using namespace std;

int main() {
	vector<int> vec;
	vector<int> vec = { 1,2,3,4,5 };
	vector<int> vec(10); //크기가 10
	vector<int> vec(10, 5); // 크기가 10, 모든 원소 5 초기화
}

ⓐ push_back() : 새 원소 추가

push_back() 메서드의 내부 동작 : 
만약 새 원소를 추가할 공간이 있다면 마지막 원소 다음에 저장 👉 O(1)
만약 공간이 없다면, 2*size 만큼의 메모리를 새로 할당해서, 기존 원소를 옮긴다.
새로 할당한 메모리에 원소를 저장. 👉 O(n)

ⓑ insert() 함수 : 삽입할 위치(반복자)를 지정하여 새 원소 삽입 (O(n))

vec.insert(vec.begin(), 0); // 맨 앞에 0추가
vec.insert(find(vec.begin(), vec.end(), 1), 4); // 1앞에 4추가

- push_back(), insert() 둘다 추가할 원소를 임시로 생성한후, 벡터 버퍼 내부 위치로 복사/이동 한다는 단점이 있음

👉 emplace_back(), emplace() 함수를 이용 (새 원소 위치에서 곧바로 객체가 생성)

 

ⓒ pop_back() : 맨 마지막 원소 제거(벡터 크기 1감소)

ⓓ erase() : 반복자 인자를 받아 해당 원소 제거 / 시작원소~ 끝원소-1 제거

vec.erase(vec.begin()); // 첫 번째 원소 제거
vec.erase(vec.begin()+1, vec.begin()+4); // 1~3까지 제거

ⓔ clear() : 모든 원소 제거 

ⓕ reserve(capacity) : 벡터에서 사용할 용량을 지정(매개변수로 지정한 값이 현재 용량보다 크면 재할당)

ⓖ shrink_to_fit() : 여분의 메모리 공간을 해제하는 용도

 

2) 할당자

- vector는 템플릿 매개변수에서 데이터 타입 다음에 할당자를 전달할 수 있음

* 할당자? 메모리 할당과 해제에서 사용하는 stl

 

1.5 forward_list

- 배열과 벡터는 데이터 중간에 자료추가, 삭제 작업이 매우 비효율적임

- 따라서 연결리스트 같은 자료구조가 등장

- new와 delete를 이용해 연결리스트를 구현할 수 있지만, C++ 에서는 stl이 따로 존재함!

- forward_list는 전체 리스트의 크기를 반환하거나 첫 번째 원소를 제외한 나머지 원소에 직접 접근 불가

 

1) forward_list에서 원소 삽입과 삭제 

- push_back() 함수를 제공하지 않는다. (왜냐하면 마지막 원소에 직접 접근할 수 없기 때문)

ⓐ push_front() : 연결 리스트 맨 앞에 새로운 원소를 삽입

ⓑ insert_after() : 특정 원소에 원소 삽입

- 배열 구조에서의 삽입 함수에 비해 매우 빠르게 동작 왜냐하면 노드의 포인터 조작으로 구현되기때문에)

forward_list<int> fwd_list = {1, 2, 3};
fwd_list.push_front(0); // 맨 앞에 0 추가
auto it = fwd_list.begin();
fwd.list.insert_after(it, 5); // 맨 처음 원소 뒤에 5 추가

 - emplace_front() 와 emplace_after() 함수 제공함 (벡터와 달리 추가적인 복사/이동 없기에 효율적임)

 

ⓒ pop_front() : 맨 앞 원소를 삭제

ⓓ erase_after() : 삭제할 범위의 시작 원소 앞을 가르키는 반복자를 이용해 삭제

 

2) 기타 함수

ⓐ remove() : 삭제할 원소 값 하나를 매개변수로 받아 일치하는 값을 모두 삭제

ⓑ  remove_if()  : 데이터 원소 값 하나를 인자로 받아 bool 값을 반환하는 조건자함수를 인자로 받아 true 일때 삭제

- 둘다 시간복잡도는 O(n) 이다.

list::remove_if - C++ Reference (cplusplus.com)

list::remove_if - C++ Reference

 

3) 연습문제 3 : 연결리스트에서 remove_if()함수 이용한 조건부 원소 삭제

#include <iostream>
#include <string> 
#include <forward_list>
using namespace std;

struct citizen {
    string name;
    int age;
};

// 연산자 "<<" 의 오버 로딩. 매개변수로 
ostream& operator<<(ostream& os, const citizen& c) {
    return (os << "[" << c.name << ", " << c.age << "]");
}
int main() {

    forward_list<citizen> citizens = {
        {"Kim", 22}, {"Lee", 25}, {"Park", 18}, {"Jin", 16}
    };
    auto citizens_copy = citizens;
    cout << "전체 시민들: ";
    for (const auto& c : citizens) {
        cout << c << " ";
    }
    cout << endl;

    citizens.remove_if([](const citizen& c) {
        return (c.age < 19);
        });
    cout << "투표권이 있는 시민들: ";
    for (const auto& c : citizens) {
        cout << c << " ";
    }
    cout << endl;

}

- 연결리스트 sort 방법

forward_list<int> list1 = { ... };
list1.sort(); // 오름차순
list1.sort(greater<int>()); //내림차순

- 그 외 멤버 함수

ⓐ reverse() : 지정된 원소의 순서를 역순으로 변경

ⓑ unique() : 중복되는 원소 제거(첫번째만 놔둠)

 

1.6 반복자

- 반복자는 포인터와 비슷하지만 STL컨테이너에 대해 공통의 인터페이스 제공

- 배열과 벡터는 역방향 이동이 가능하지만 연결리스트는 없음(순방향 반복자)

 

1) 연습문제 4: 다양한 반복자에서 이동하기

#include <iostream>
#include <vector> 
#include <forward_list>
using namespace std;

int main() {
	vector<string> vec = {
		"Kim", "Eun", "Lee", "Seb", "Lew"
	};
	auto it = vec.begin();
	cout << "가장 최근 우승자: " << *it << endl;

	it += 3;
	cout << "3년 전 우승자: " << *it << endl; //Seb
	advance(it, -2);
	cout << "그후 2년 뒤 우승자: " << *it << endl; //Eun

	forward_list<string> fwd(vec.begin(), vec.end());
	auto it1 = fwd.begin();
	cout << "가장 최근 우승자: " << *it1 << endl;

	advance(it1, 3); 
	cout << "3년 전 우승자: " << *it1 << endl; //Seb

	//advance(it1, -2); // 순방향 이동만 가능하기에 에러 , += 연산도 안됨
	//cout << "그후 2년 뒤 우승자: " << *it1 << endl; //Eun

}

2) 연습 문제 5: 기본적인 사용자 정의 컨테이너 만들기

#include <iostream>
#include <algorithm>
using namespace std;

struct singly_ll_node {
	int data;
	singly_ll_node* next;
};

class singly_ll {
public:
	using node = singly_ll_node;
	using node_ptr = node*;
private:
	node_ptr head;
public:
    // push_front 함수를 직접 구현.(원소를 맨 앞으로 삽입)
	void push_front(int val) {
		auto new_node = new node{ val, NULL };
		if (head != NULL) new_node->next = head; // 리스트가 비어있지 않다면
		head = new_node; // 새 노드가 head가 된다.
	}
    // pop_front 함수를 직접 구현.(맨 앞 원소 삭제)
	void pop_front() {
		auto first = head;
		if (head) { // head가 있다면?
			head = head->next;
			delete first;
		}
	}
    
    // 리스트 반복자 정의
	struct singly_ll_iterator {
	private:
		node_ptr ptr;
	public:
    	// 링크 참조 - 생성자 정의(멤버변수 ptr을 p로 초기화)
		singly_ll_iterator(node_ptr p) : ptr(p) {} 
        
        // *연산자 사용시 ptr->data을 리턴하도록함
        // 포인터에서 int& n = 3; 이라할 때 *n 이 3인거
		int& operator*() { return ptr->data; }
        
        // 사용자 정의 메서드 get으로 ptr을 반환하도록 함
		node_ptr get() { return ptr; }

		// ++(선행,후행) 연산자 정의
		singly_ll_iterator& operator++() {
			ptr = ptr->next;
			return *this;
		}
		singly_ll_iterator operator++(int) {
			singly_ll_iterator result = *this;
			++(*this);
			return result;
		}

		// == 연산자 정의 
		friend bool operator==(const singly_ll_iterator& left, const singly_ll_iterator& right) {
			return left.ptr == right.ptr;
		}
		friend bool operator!=(const singly_ll_iterator& left, const singly_ll_iterator& right) {
			return left.ptr != right.ptr;
		}
	};

	// begin(), end() 연산자 정의 - const인것과 const 아닌거 둘다 정의함 왜그렇게 하는진 몰겟음
	singly_ll_iterator begin() { return singly_ll_iterator(head); }
	singly_ll_iterator end() { return singly_ll_iterator(NULL); }
	singly_ll_iterator begin() const{ return singly_ll_iterator(head); }
	singly_ll_iterator end() const{ return singly_ll_iterator(NULL); }

	singly_ll() = default; // 기본 생성자 정의
    
    // 초기화 리스트 정의
    // 매개변수로 other(리스트)을 받아왔을 때 head를 NULL로 초기화 해주는 생성자
    // singly_ll sll3(singly_ll형태 리스트);이런 식으로 선언 가능하도록?? 해주는듯
	singly_ll(const singly_ll& other) : head(NULL) {
		if (other.head) {
			head = new node{ 0, NULL };
			auto cur = head;
			auto it = other.begin();
			while (true) {
				cur->data = *it; //매개변수로 들어온 리스트의 1..2..3..번째 원소 데이터 값 
				auto tmp = it;
				++tmp;
				if (tmp == other.end()) break;
				
				cur->next = new node{ 0, NULL }; 
				cur = cur->next;
				it = tmp;
			}
		}
	}

	// singly_ll sll3(initializer_list형태 리스트) 생성자 정의
	singly_ll(const initializer_list<int>& ilist) : head(NULL) {
		for (auto it = rbegin(ilist); it != rend(ilist); it++) push_front(*it);
	}

};


int main() {
	singly_ll sll = { 1,2,3 };
	sll.push_front(0);

	cout << "첫 번째 리스트: ";
	for (auto i : sll) {
		cout << i << " ";
	}
	cout << endl;

	auto sll2 = sll;
	sll2.push_front(-1);
	cout << "첫 번째 리스트를 복사한 후, 맨 앞에 -1을 추가: ";
	for (auto i : sll2) {
		cout << i << ' ';
	}
	cout << endl;

	// 얕은 복사는 같은 메모리 값을 가져 첫번째 리스트에 영향을 주게 된다.
	cout << "깊은 복사 후 첫 번째 리스트: ";
	for (auto i : sll) {
		cout << i << ' ';
	}
	cout << endl;

}

코드 이해 어려워서 참고한 링크

c++ - 생성자에서 콜론(:)은 왜 쓰는 건가요? | Hashcode

[ C++ ] 깊은 복사( deep copy )와 얕은 복사 ( shallow copy ) (tistory.com)

수까락의 프로그래밍 이야기 (zum.com)

 

 

3) 실습 문제 1: 음악 재생 목록 구현하기

- 원형 연결 리스트 구현하기

080239/Activity01.cpp at master · gilbutITbook/080239 (github.com)

GitHub - gilbutITbook/080239

너무.. 어려운데요 ?

 

 

1.7 list 

- forward_list는 아주 기본적인 형태로 구현된 연결 리스트(성능을 위해)

- list는 forward_list의 단점을 보완한 stl로, 이중 연결 리스트 구조로 되어 있음 그대신 메모리 사용 더 많음

- 노드의 기본 형태는 data, *next, *prev 형태

- 역방향 이동 가능하며, push_back, size 등의 함수 지원 가능

 

1) 멤버 함수

ⓐ insert(), emplace() : 원소 삽입

ⓑ push_back(), emplace_back(), pop_back() 

ⓒ remove(), remove_if(), sort(), unique(), reverse() 함수 제공

 

2) list의 삽입 또는 삭제 함수 사용하기

#include <iostream>
#include <list>
using namespace std;

int main() {
	list<int> list1 = { 1, 2, 3, 4, 5 };
	list1.push_back(6); // 맨 뒤에 원소 삽입
	list1.insert(next(list1.begin()), 0); // 맨 처음 원소 바로 뒤에 삽입 
	list1.insert(list1.end(), 7); // 맨 뒤에 원소 삽입

	list1.pop_back(); // 맨 뒤 원소 삭제

}

* forward_list와 list 에서 삽입/삭제의 멤버함수의 시간복잡도는 같지만, list에서 더 많은 연산이 필요하다.

  왜냐하면 list는 두 개의 포인터를 가지고 있기 때문에 두 배의 연산이 필요함

 

3) 양방향 반복자

- list 반복자는 배열 기반 반복자와 forward_list의 반복자 중간 정도의 유연성을 가짐

 but 배열 반복자(임의 접근 반복자) 보단 유연하지 않음(어느 방향으로든 원하는 만큼 한번에 이동 불가)

- list 반복자를 양방향 반복자 라고함

 

4) 반복자 유효화

- 반복자는 메모리 주소를 가르키는 포인터를 이용해 구현되었기 때문에 컨테이너가 변경될 시 제대로 동작 안할 수 있음

- 예를 들어 vector에서 size를 벗어나 새 원소 삽입시 새로 메모리 공간을 할당해야하는데, 

  이 때 기존에 사용하던 반복자, 포인터, 참조 모두 무효화 된다.

- 연결리스트에서는 원소 이동이 필요없기때문에 반복자가 무효화 되지 않음

- list에서 size, push_back, pop_back 함수는 O(1)의 시간 복잡도를 가진다.

 

5) 실습 문제 2: 카드 게임 시뮬레이션