[C++] 2. 자료 구조(+ STL)

 

서론

이번 글은 몇 주간 백준이나 구름톤 등 여러 문제들을 풀어보며 개인적으로 필요하다고 느꼈던 자료구조들을 메모하기 위해 쓴 것이다. C++에 존재하는 라이브러리를 이용한 자료 구조들과 이 외의 기타 데이터 저장 방법을 기술해보려고 한다. 해당 글은 C++을 기준으로 작성하였으나, 통상적으로 사용하는 다른 언어들(Java, Python 등) 다른 언어에서도 약간의 변경만 하여 적용해 볼 수 있다.

 

 

 

변수(Variable)

• 가장 기초적인 데이터를 담는 공간
• 다른 언어에서 봐왔듯이 int, char, string, bool, float, double 등 자료형과 정의를 통해 선언하여 사용한다.
• 선언의 위치에 따란 전역 변수(어디서든 사용이 가능함),지역 변수(해당 지역(Scope)에서만 사용 가능)로 구분된다.

- 변수의 지정자

const	변수 선언 전 const를 붙이게 되면 상수로 전환되어 프로그램이 실행되는 동안 해당 데이터의 변경이 불가능하다.
static	정적 변수라고 하며 지역 변수로 선언해도 전역 변수 처럼 사용이 가능하다. 프로그램이 종료 될 때 까지 존재한다
extern	다른 파일에 존재하는 전역변수를 사용하고자 할 때 선언한다.

 

 

배열(Array)

• 선언해야 할 변수가 많을 때 주로 사용 (변수와 같이 자료형을 선언해주어야 한다.)
• 배열의 구성 값을 요소(element)라 하며, 그 값들의 위치를 인덱스(index)라고 한다.
• 배열의 선언 방식에 따라 1차원 배열, 2차원 배열...으로 선언 가능하다.
• 고정 배열과 동적 배열로 나뉜다.

고정 배열	arr[n]	컴파일에서 배열의 크기를 결정
동적 배열	new arr[n]	런타임 동안에 배열의 크기를 결정, C의 malloc과 같은 역할을 한다.

 

 

 

Vector

• 전체적인 구성은 배열과 유사하지만, 메모리 크기의 변경이 가능하다.
• 백터를 선언한 뒤, 데이터의 삽입과 삭제가 가능하다.

#include <vector>   // vector를 쓰기 위한 라이브러리 추가

vector<int> v   // int형의 빈 vector를 생성한다
vector<int> v(n)   // 0으로 초기화된 n개의 원소를 보유한 int형의 빈 vector를 생성한다
vector<int> v(n, 5)   // 5으로 초기화된 n개의 원소를 보유한 int형의 빈 vector를 생성한다
vector<int> v1(v2)   // v2를 복사한 v1 vector를 생성한다
vector<vector<int>> v   // 2차원 int형의 vector를 생성한다

- 주요 함수

v.at(n)	인덱스가 n인 원소가 존재 할 경우 해당하는 값을 반환
v.front()	첫 번째 원소를 반환
v.back()	마지막 원소를 반환
v.clear()	백터의 초기화 (메모리(백터의 size)는 유지)
v.begin()	첫번째 원소를 가르키는 iterator를 반환
v.end()	마지막 원소를 가르키는 iterator를 반환
v.push_back(n)	n을 백터의 마지막 원소 뒤에 추가
v.pop_back()	마지막 원소를 제거
v.size()	백터의 크기를 출력
v.insert(iter, n)	iter가 가르키는 위치에 n을 삽입, 해당 위치의 iterator를 반환
v.erase(iter)	iter가 가르키는 원소를 삭제

 

 

 

Pair

• 앞으로 나올 STL들과 함께 응용하기 좋은 클래스
• 사용자가 지정한 2개 타입의 데이터를 저장하는 데 사용
• utility  이용하여 사용가능하나, vector, algorithm 라이브러리에 utility가 포함되어 있음

#include <utility>
#include <vector>
#include <algorithm> 

vector<pair<int,int>> v;

v.push_back(make_pair(5, 6));
v.push_back(make_pair(-2, 3));

 

 

 

Stack

• 통상적으로 생각하는 LIFO(Last In First Out) 구조의 배열이다.
• Vector과 같이 메모리가 가변이며, 삽입과 삭제가 가능하다. 

#include <stack>   // stack을 쓰기 위한 라이브러리 추가

stack<int> s;    // int 자료형의 stack 선언

- 주요 함수

s.push(n)	n을 추가
s.pop()	top에 해당하는 데이터를 삭제
s.top()	s 스택의 top을 반환
s.empty()	스택이 비어있는지 확인 (비어 있다면 true 출력)

 

 

 

Queue

• 위의 Stack과는 다르게 FIFO(First In First Out) 구조의 배열이다.

#include <queue>   // queue를 이용하기 위한 라이브러리 추가

queue<int> q;   // int 자료형의 queue q 선언

- 주요 함수

s.push(n)	마지막 원소 뒤에 n을 추가
s.pop()	맨 앞 데이터를 삭제
s.front()	맨 앞 데이터를 반환
s.back()	마지막 데이터를 반환
s.empty()	큐가 비어있는지 확인 (비어 있다면 true 출력)

 

- 우선순위 큐

• 최대 또는 최소 원소를 탐색하거나 삭제 가능하고, 임의의 원소를 삽입할 수 있는 자료 구조
• 힙(heap)이라고 하는 이진트리를 이용하여 구현된다.

priority_queue<int> q;   // 최대 힙 기반
priority_queue<int, vector<int>, greater<int>> q; /// 최소 힙 기반

 

 

 

List

• LinkedList(연결리스트)라고도 하며, 각 요소가 값뿐만 아니라 다음 요소를 가리키는 포인터를 같이 가지고 있음
• 데이터의 삽입이나 삭제가 일어날 때, 뒤의 데이터를 가져오거나 밀 필요 없이 포인터로 지정

#include <list> // list를 쓰기 위한 라이브러리 추가

list<int> l;  // int자료형의 리스트 l 선언

- 주요 함수

list.front()	첫 번째 원소를 반환
list.back()	마지막 원소를 반환
list.begin()	첫번째 원소를 가르키는 iterator를 반환
list.end()	마지막 원소를 가르키는 iterator를 반환
list.push_front(n)	리스트 맨 앞에 n을 추가
list.push_back(n)	리스트 맨 뒤에 n을 추가
list.insert(iter, n)	iter가 가르키는 위치에 n을 삽입
list.pop_front()	첫번째 원소를 제거
list.pop_back()	마지막 원소를 제거
list.erase(iter)	iter가 가르키는 원소를 삭제