자료구조

데이터를 효율적으로 저장, 접근, 수정하기 위한 그릇.

주어진 입력 데이터의 형태와 사용해야 하는 알고리즘에 따라
적절한 그릇을 선정해 사용하는 것이 좋다.

배열

메모리의 연속 공간 에 값이 채워져 있는 형태.

배열의 값은 인덱스를 통해 참조할 수 있으며,
선언한 자료형의 값만 저장할 수 있다.

int array[10];

• 선언할 때 배열의 크기를 지정할 수 있으며, 한 번 선언하면 크기를 늘리거나 줄일 수 없다.
• 새로운 값을 삽입하거나 특정 인덱스에 있는 값을 삭제하기 어렵다.
  (해당 인덱스 주변에 있는 값을 이동시키는 과정이 필요하다.)

리스트

값과 포인터를 묶은 노드를 포인터로 연결한 형태.

Head 포인터부터 순서대로 접근해야 하므로, 접근 속도가 느리다.

#include <list>
list<int> l;

• 포인터로 연결되어 있으므로 데이터를 삽입, 삭제하는 연산 속도가 빠르다.
• 선언할 때 크기를 별도로 지정하지 않아도 된다.
• 포인터를 저장할 공간이 필요하므로 배열보다 구조가 복잡하다.

벡터

기존 배열과 같은 특징을 가지면서 배열의 단점을 보완한 동적 배열의 형태.
C++ 표준 라이브러리 (STL) 에 있는 자료구조 컨테이너 중 하나.

#include <vector>
vector<int> v;

• 동적으로 원소를 추가할 수 있다.
• 맨 마지막 위치에 데이터를 삽입, 삭제할 때는 문제가 없지만
  중간 데이터의 삽입, 삭제는 배열과 같은 메커니즘으로 동작한다.
• 배열과 마찬가지로 인덱스를 이용하여 각 데이터에 직접 접근할 수 있다.

스택

삽입과 삭제 연산이 후입선출(LIFO : Last-in, First-out) 로 이뤄지는 형태.
삽입과 삭제가 한 쪽에서만 일어난다.

#include <stack>
stack<int> s;

top : 삽입과 삭제가 일어나는 위치

• push : top 위치에 새로운 데이터를 삽입하는 연산
• pop : top 위치에 현재 있는 데이터를 삭제하고 확인하는 연산
• top : top 위치에 현재 있는 데이터를 단순 확인하는 연산

깊이 우선 탐색(DFS), 백트래킹 알고리즘에서 자주 사용된다.

큐

삽입과 삭제 연산이 선입선출(FIFO : First in, First out) 로 이뤄지는 형태.
삽입과 삭제가 양방향에서 이뤄진다.

#include <queue>
queue<int> q;

back : 큐에서 가장 끝 데이터를 가리키는 영역
front : 큐에서 가장 앞 데이터를 가리키는 영역

• push : back 부분에 새로운 데이터를 삽입하는 연산
• pop : front 부분에 있는 데이터를 삭제하고 확인하는 연산

너비 우선 탐색(BFS) 에서 자주 사용된다.

트리