2주차 배열, 벡터, 연결리스트

https://share.note.sx/bt8i9cg8#ApGilAZ7dDnTTtnTTkPkFVo747ESuyukmyr3oFeNWmM

https://share.note.sx/bt8i9cg8#ApGilAZ7dDnTTtnTTkPkFVo747ESuyukmyr3oFeNWmM

2주차 배열,벡터, 연결리스트 설명 <담당자:고필규>
## 자료구조의 종류

1주차에 배운 스택,큐,덱과 2주차에 배울 배열(리스트)과 연결리스트는 선형구조이다.

## 배열과 벡터

##### 개념
배열(Array): 메모리에서 원소를 연속적으로 배치한 고정 크기의 자료구조. 
벡터(Vector): 동적 크기를 지원하는 배열과 유사한 자료구조로, ==자동으로 크기 조절 가능.==

##### 배열의 성질
1. 인덱스를 통해 데이터에 직접 접근할 수 있다.  
2. 추가적으로 소모되는 메모리의 양(오버헤드)가 거의 없다.
3. 캐시적중률(Cache hit rate)이 높다.
4. 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸린다.
크기 변경이 어렵다

##### 배열과 포인터

배열의 이름은 배열의 시작 주소이다. 
sizeof 나 &연산자를 사용하지 않고 그냥 사용하면 암묵적으로 배열의 첫 번째 원소 가리키는 포인터로 변환된다.

##### 배열과 벡터 비교

**정적인 데이터** 는 배열로 
**유동적인 데이터**에는 벡터를 주로 사용한다.

##### 배열은 언제쓰나요
1. 데이터의 크기가 고정되어 있고, 변경될 일이 없는 경우
2. 빠른 인덱스 기반 접근이 필요한 경우
##### 벡터는 언제쓰나요
  1.저장하려는 데이터 개수가 가변적일때
  2.중간에 데이터를 삽입/삭제할 일이 많이 없을때
  3.저장할 데이터가 적거나, 많다면 검색이 빈번하지 않을때
  4.랜덤한 데이터 접근을 허용할때
##### 게임에서 활용

1. **캐릭터 인벤토리 시스템**: 제한된 수의 아이템 보유, 빠른 접근  
2. **맵 타일 관리**: 그리드 형태의 맵을 배열로 관리, 특정 위치에 빠르게 접근 가능
3. **애니메이션 프레임 관리**: 프레임을 순서대로 저장하여 빠른 접근 가능
4. **스킬 및 능력치 시스템**: 고정된 스킬을 배열로 관리하여 접근 속도를 최적화
5. **순차적 데이터 처리**: 순차적으로 접근하는 경우 배열이 효율적 (예: 로그 데이터 저장)

#### STL Vector 
   
##### 1. 벡터 선언 

std::vector<int> vec; // 빈 벡터 생성
std::vector<int> vec(10); // 크기 10의 벡터 생성
std::vector<int> vec = {1, 2, 3, 4, 5}; // 초기화 리스트 사용

###### 1주차에서 공부한 stl 스택,큐,덱 에서 쓰는 함수들을 대부분 사용할 수 있다.
##### 2. 원소 추가/ 삭제

vec.push_back(6); // 맨 뒤에 요소 추가
vec.pop_back(); // 맨 뒤 요소 제거
vec.insert(vec.begin() + 2, 10); // 특정 위치에 삽입
vec.erase(vec.begin() + 2); // 특정 위치 요소 삭제
vec.clear(); // 모든 요소 삭제

##### 3. 원소 접근 및 수정

int first = vec.front(); // 첫 번째 요소 반환
int last = vec.back(); // 마지막 요소 반환
int element = vec[2]; // 인덱스를 이용한 접근
int safeElement = vec.at(2); // 인덱스 범위 체크 후 접근

###### [ ]연산자와 at( ) 멤버함수의 차이

기능과 결과는 같지만 범위 점검(out of range의 예외처리) 여부에 차이가 있다.
[ ]연산자는 보다 빠른 성능을 보이며
at( ) 함수는 비교적 속도가 느리고 안전하다.

###### 예시 코드

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

int main()
{
vector<int> v;

v.push_back(0);
v.push_back(10);
v.push_back(20);
v.push_back(30);
v.push_back(40);

for (vector<int>::size_type i = 0; i < v.size(); ++i)
{
cout << v[i] << " ";
}
cout << endl;


try {
cout << v.at(6) << endl; //at 멤버함수에서 out of range 유도
}
catch (out_of_range& e)
{
cout << e.what() << endl;
}

return 0;
}

at함수를 이용해 인덱스밖의 원소를 출력하려 할때

<at ( ) 함수 사용>

<[ ] 연산자 사용>

 

##### 4. 크기 및 상태 확인

int size = vec.size(); // 요소 개수 반환
int capacity = vec.capacity(); // 할당된 전체 공간 크기 반환
bool isEmpty = vec.empty(); // 벡터가 비었는지 확인

##### 5.메모리 관리 및 최적화

vec.resize(20); // 크기 변경 (기존 요소 유지)
vec.shrink_to_fit(); // 벡터의 용량을 실제 크기로 줄임
vec.reserve(50); // 벡터의 용량을 미리 50으로 설정 (성능 최적화)

## 리스트

 

##### 개념        

 배열의 문제점을 해결하기 위한 자료 구조
인덱스라는 장점을 버리고, 빈틈없는 데이터의 적재라는 장점을 취한 인터페이스
하지만 데이터가 메모리 상에 연속적으로 저장되진 않기 때문에 연결 리스트라 불린다.

 데이터를 논리적인 순서대로 나열한 자료구조
리스트 각 요소는 포인터로 연결 ,각 요소에 접근할 때도 포인터를 이용해 순서대로 접근 
리스트의 데이터는 노드(node) 혹은 요소(element)라고 한다.

###### 리스트의 구조

노드: 리스트에서 데이터를 저장하는 단위 (데이터 + 다음 노드의 포인터)
Head : 리스트의 맨 처음 노드 (리스트 생성시 꼭 필요함)
Tail : 리스트의 맨 끝 노드

###### 리스트의 종류  
 - **단일 연결 리스트(Singly Linked List)**:   각 노드가 다음 노드의 주소만 저장.
        
 - **이중 연결 리스트(Doubly Linked List)**: 각 노드가 앞뒤 노드의 주소를 저장.
        
- **원형 연결 리스트(Circular Linked List)**: 마지막 노드가 첫 번째 노드를 가리킴.



##### 연결리스트의 성질

1. 삽입/삭제가 빠르다
2. 연속된 메모리 공간이 필요 없다.
3. 크기 제한이 없다.
4.  특정 위치의 데이터를 검색에 O(n)의 시간이 걸리는 단점
5. 구현이 어렵고 오류가 발생하기 쉽다.

##### 배열과 연결리스트의 차이

##### 리스트는 언제쓰나요 

데이터가 자주 추가되거나 제거되는 상황
데이터 접근하는 게 순차적인 상황
데이터 크기가 불확실할 때

중간 삽입/삭제가 자주 일어나는 경우 → 연결 리스트
빠른 임의 접근이 중요한 경우 → 배열 또는 벡터

##### 게임에서 활용

1. NPC 행동 관리

행동을 순차적으로 수행, 게임 상황에 따라 행동이 추가되거나 삭제될 때

2. 레벨 내 동적 객체 관리

 적, 아이템, 장애물 등이 계속 추가되거나 제거되는 경우

3. 멀티 플레이어 게임에서 플레이어 관리

 플레이어가 접속하거나 접속 해제하는 경우가 빈번하므로, 플레이어 목록을 관리하기 용이함.

4. 타이머 이벤트 관리

시간 순서에 따라 이벤트를 처리하는 경우
 예정된 이벤트가 시간이 되면 해당 이벤트를 실행하거나 제거할 때도 편리함

#### STL List

##### 리스트 선언

list<int> li1; // 비어있는 int list 생성 
list<int> li3(5); // int list 생성 후 5개의 원소를 0으로 초기화
list<int> li4(4, 3) // int list 생성 후 4개의 원소를 3으로 초기화 { 3, 3, 3, 3 } 
list<int> L = { 3, 7 }; // int list 생성 후 3, 7로 초기화

##### 리스트의 반복자

  begin()   // beginning iterator 반환
  end()     // end iterator 반환
  itr++     // itr ++
  itr--     // --itr 도 됩니다.
  itr + 5   // 불가능

리스트 에서 정의되는 반복자의 타입을 보면 `BidirectionalIterator` 타입임을 알 수 있다. 이름에서도 알 수 있듯이 양방향으로 이동할 수 있되, 노드를 따라 앞뒤로 한 칸씩밖에 이동할 수 없다.

반면에 벡터에서 정의되는 반복자의 타입은 `RandomAccessIterator` 타입 이다.
즉, 임의의 위치에 접근할 수 있는 반복자이다. it + n 처럼 원소이동이 가능하다.
(참고: `RandomAccessIterator` 는 `BidirectionalIterator` 를 상속)

##### 원소의 추가/삭제

myList.push_back(6);  // 맨 뒤에 추가
myList.push_front(0); // 맨 앞에 추가
myList.insert(std::next(myList.begin(), 2), 10); // 특정 위치(2번째)에 삽입
myList.pop_back(); // 맨 뒤 요소 제거
myList.pop_front(); // 맨 앞 요소 제거
myList.erase(std::next(myList.begin(), 2)); // 특정 위치(2번째) 요소 삭제
myList.remove(3); // 값이 3인 모든 요소 제거
myList.clear(); // 모든 요소 삭제

##### 원소 접근

int first = myList.front(); // 첫 번째 요소 반환
int last = myList.back(); // 마지막 요소 반환
auto it = myList.begin();
int element = *it; // 이터레이터가 가리키는 원소 접근```

##### 크기 및 상태 확인

int size = myList.size(); // 요소 개수 반환
bool isEmpty = myList.empty(); // 리스트가 비었는지 확인

##### 정렬 및 조작

리스트는 stl::list에서 sort()함수 등 전용 멤버함수를 제공한다. 

myList.sort(); // 오름차순 정렬
myList.reverse(); // 리스트 순서 뒤집기
myList.unique(); // 중복 원소 제거 (정렬된 상태에서만 작동)

##### 리스트의 병합 및 교환

std::list<int> otherList = {7, 8, 9};
myList.merge(otherList); // 정렬된 두 리스트 병합
myList.swap(otherList); // 두 리스트의 요소를 교환
myList.splice(myList.begin(), otherList); // otherList의 모든 요소를 myList의 맨 앞으로 이동

##### 리스트가 std::sort( ) 를 사용할 수 없는 이유

 메모리 배치 및 자료구조의 특성 때문에 벡터는 `std::sort()`를 사용할 수 있지만
리스트는 사용할 수 없다. 

STL `<algorithm>` 헤더의 `std::sort()`는 **IntroSort (IntroSortion Sort)** 를 사용한다.
 **IntroSort(IntroSortion Sort)란?**
- **퀵 정렬(QuickSort)** + **힙 정렬(HeapSort)** + **삽입 정렬(InsertionSort)** 을 조합한 **하이브리드 정렬 알고리즘**
- 기본적으로 **퀵 정렬(QuickSort)** 을 사용하지만, **비효율적인 경우** 자동으로 **힙 정렬(HeapSort)** 또는 **삽입 정렬(InsertionSort)** 로 변경한다. 

리스트는 `list.sort()`를 사용해야 하며, 내부적으로 병합 정렬(Merge Sort) 을 사용한다.