[Algorithm] Queue,Pair,Vector

출처: https://sarah950716.tistory.com/5 [알고리즘 정복기]

출처: https://sarah950716.tistory.com/4 [알고리즘 정복기]

1) 정의

FIFO(First In First Out, 선입선출) 자료구조

2) 용도

① BFS(Breadth First Search, 너비우선탐색)

② 특별한 알고리즘을 사용하는 것이 아니라 직접 문제 상황을 구현하는 문제들 중 FIFO의 구조를 가지는 문제를 풀 때

(Ex. 다리에 올라갈 수 있는 최대 하중과 각 트럭의 무게가 주어질 때, 모든 트럭이 다리를 지나가는 데 걸리는 최소 시간을 구하는 문제. 다리에 먼저 올라간 트럭이 먼저 나오게 되기 때문에 queue를 이용해 구현하면 풀 수 있다.)

3) 사용법

queue를 사용하기 위해서는 <queue>를 include 해야 합니다.

편의상 멤버 함수의 적용 대상이 되는 queue를 q라고 부르도록 하겠습니다.

멤버 함수	기능
q.size()	q의 사이즈(물리적인 저장 용량이 아닌 원소의 개수)를 리턴
q.empty()	q의 사이즈가 0인지 아닌지를 확인
q.front()	q에 가장 먼저 들어간 원소를 리턴
q.back()	q에 가장 나중에 들어간 원소를 리턴
q.push(val)	q의 위(뒤에 val 추가
q.pop()	q에 가장 먼저 들어간 원소를 삭제

<front와 back>

<push와 pop>

4) 예제

queue<pair<int,int>> q;
 
q.push(make_pair(1,2));
 
int a = 2, b = 3;
pair<int,int> p = make_pair(a,b);
q.push(p);
 
cout << q.front().first << ' ' << q.front().second;        // 1 2
cout << q.back().first << ' ' << q.back().second;          // 2 3
 
//q가 비어있지 않은 동안
while(!q.empty())
{
    pair<int,int> n = q.front();
    q.pop();
 
    cout << n.first << ' ' << n.second << '\n';            // 1 2
                                                           // 2 3
}
 
cout << q.size();                                          // 0

q.push(make_pair(4,5));
q.push(make_pair(5,6));


queue<pair<int,int>> emt;
swap(q, emt);

cout << q.size();                                           // 0
                                  

29번째 줄을 보면 swap이라는 함수를 사용한 것을 볼 수 있습니다. 자주 쓰이지는 않지만, vector와는 달리 queue는 clear() 멤버 함수가 없으므로 swap이라는 함수를 이용해 clear() 하고자 하는 queue를 빈 queue와 swap해줌으로써 clear()와 같은 효과를 낼 수 있습니다. 이렇게 swap을 이용하는 것이 queue가 빌 때까지 원소를 pop()하는 것보다 빠르기 때문에 알아두는 것이 좋겠습니다.

가장 기본적인 STL 컨테이너라고 할 수 있는 pair와 vector에 대해서 먼저 알아보도록 하겠습니다.

이해하기 쉽도록 제 나름대로 정한 정의와 문제를 풀 때의 쓰임새를 알아보고 난 후, 멤버 함수들과 예제를 통해 사용법을 익혀보도록 하겠습니다.

1. pair

1) 정의¹

이름이 'first', 'second'인 두 개의 변수를 저장할 수 있는 struct

2) 용도²

① 이차원 배열의 인덱스 

② 이차원 좌표평면에서의 좌표 

③ 정점 번호와 해당 정점 번호까지의 최단거리를 묶어서 저장해야 되는 경우 

3) 사용법

pair를 사용하기 위해서는 <utility>를 include 해야 합니다.

pair는 다른 컨테이너들에 비해 간단한 구조이기 때문에 멤버 함수가 적습니다. 따라서, 바로 예제를 통해 pair의 기본적인 사용법을 익혀보도록 하겠습니다.

4) 예제

//pair 선언
pair<int,int> p;
pair<char,double> p;
 
//pair 생성
int a = 1, b = 2;
pair<int,int> p = make_pair(a,b);
pair<int,int> p = make_pair(1,2);
 
//pair의 멤버 변수에 접근
int valA = p.first;
int valB = p.second;

first가 1이고 second가 2인 pair를 만들기 위해, pair<int,int>를 선언한 후에 각 멤버 변수(first, second)를 초기화해주는 것이 아니라 make_pair를 이용해 바로 만들어낼 수 있다는 것을 알아두면 좋을 것 같습니다(예제의 8번째 줄 참고).

2. vector

1) 정의

사이즈가 유동적인 배열

2) 용도

배열을 사용하는 모든 경우

3) 사용법

vector를 사용하기 위해서는 <vector>를 include 해야 합니다.

vector는 특히 많이 사용되는 컨테이너입니다. 그래서, 그만큼 많은 종류의 멤버 함수를 사용하기도 합니다. 

편의상 멤버 함수의 적용 대상이 되는 벡터를 v라고 부르도록 하겠습니다.

멤버 함수	기능
v.size()	v의 사이즈(물리적인 저장 용량이 아닌 원소의 개수)를 리턴
v.resize(new_size)	v를 new_size로 사이즈를 바꿔줌
v.empty()	v의 사이즈가 0인지 아닌지를 확인
v.begin()	v의 0번째 원소를 가리키는 iterator3 리턴
v.end()	v의 마지막 원소를 가리키는 iterator 리턴
v.front()	v의 0번째 원소를 리턴
v.back()	v의 마지막 원소를 리턴
v.push_back(val)	v의 끝에 val을 추가
v.pop_back()	v의 마지막 원소를 삭제
v.clear()	v의 모든 원소를 삭제

cf 1) <algorithm>에 있는 reverse()를 이용하면, vector에 속한 원소들의 순서를 거꾸로 뒤집을 수가 있습니다.

만약 원래의 vector가 1 5 2 3 였다면 reverse()한 결과는 3 2 5 1 이 됩니다.

사용법 : reverse(v.begin(), v.end());

cf 2) <algorithm>에 있는 sort()를 이용하면, vector에 속한 원소들을 오름차순으로 정렬할 수 있습니다.

만약 원래의 vector가 1 5 3 4 였다면 sort()한 결과는 1 3 4 5 가 됩니다.

사용법 : sort(v.begin(), v.end());

덧) 오름차순 뿐만 아니라 다른 정렬 기준으로도 정렬할 수 있으며, int로 이루어진 vector뿐만 아니라 다른 자료형으로 이루어진 vector도 정렬할 수 있습니다.

4) 예제

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

vector<int> iv; vector<pair<int,int>> pv;   //사이즈가 3인 vector 생성 vector<int> myv(3);   //사이즈가 N(5)이고, 각 원소가 2로 초기화된 vector 생성 int N = 5; vector<int> myv(N, 2);   //vector에 원소 추가 iv.push_back(1);                 // iv : 1 iv.push_back(2);                 // iv : 1 2 iv.push_back(3);                 // iv : 1 2 3   pv.push_back(make_pair(2,4));   //vector의 size 조정 iv.resize(4); cout << iv.size();                // 4   cout << iv.front();               // 1 cout << iv.back();                // 0 (resize를 4로 했기 때문에 마지막 원소는 자동적으로 0으로 초기화됨)   iv.pop_back();                    // iv : 1 2  iv.clear();                       // iv :  Colored by Color Scripter

cs

1.