C++ STL pair 클래스 정리(vector, sort,백준,응용)

 

 

 

C++ STL pair 클래스 총정리(vector, sort)

 

 

 

C++ STL 중 <utility> 라이브러리에 pair클래스가 있다.

오늘은 이 pair클래스에 대하여 알아보겠다.

추가로 알고리즘 문제를 풀 때 어떻게 응용되는지도 보자.

pair를 사용하면 자료 두 개를 한 가지 자료에 저장할 수 있다.

pair는 2차원 좌표 저장등 많은 곳에서 유용하게 쓰이므로

꼭 익혀두자.

 

 

 

일단 <utility>라이브러리에 있으니 추가해 준다.

 

이제 사용해 보자

 

 

 

생성

 

pair <type1,type2> p;

 

type1, type2 두 개의 데이터를 저장하는 pair p를 만든다.

예를 들어 좌표를 저장하려면 y좌표, x좌표 두 개를 저장할 int형 공간이 필요하므로

pair<int,int> p;와 같이 선언해 주면 된다.

int형뿐만 아니라 string, char, float 등을 자유롭게 사용가능하며

서로 다른 자료형을 섞어서 쓸 수도 있다.

ex) pair<string,int> p;

 

 

지금 상태로는 선언만 되었지 초기화된 것은 아니다.

즉 값이 아직 들어가지 않았다.

이제 값을 넣어보자.

 

 

 

 

초기화

 

make_pair(y,x)

 

이를 이용하면 된다.

y는 1, x는 2인 경우 p에 넣으려면

p=make_pair(1,2)

이렇게 해주면 값이 들어간다.

 

선언과 동시에 초기화를 해주려면

pair<int,int> p=make_pair(1,2)

pair<int,int> p={1,2}

이 두 가지 방법 모두 가능하다.

 

 

 

 

데이터까지 넣었으니 이제 사용해야 하지 않겠나?

사용 방법을 알아보겠다.

 

 

 

 

사용

 

p.first

p.second

 

이 두 가지를 이용한다.

p.first는 pair p의 첫 번째 인자 값,

p.second는 pair p의 두 번째 인자 값을 의미한다.

예를 들어 아까 위에서 pair<int,int> p=make_pair(1,2)를 써서

pair p에 1,2 값을 넣어 주었다.

여기서 p.first값을 출력하면 1이 나오고

p.second값을 출력하면 2가 나온다.

 

 

 

응용

 

 

좌표 저장

 

pair를 가장 많이 쓰게 되는 곳은 좌표값을 저장할 때이다.

좌표는 Y좌표, X좌표 두 개가 쌍을 이루므로 pair를 쓰기 매우 좋다.

좌표 하나를 저장하려면 위에 나온 것처럼 pair<int,int> p 이런 식으로 선언을 한 후 사용하면 된다.

좌표가 여러 개라면?

이때는 pair를 배열처럼 만들어서 사용하면 된다.

이때 array를 이용해서 

pair<int,int> p[10];

이런 식으로 선언해도 되지만 이곳에서는 vector를 사용하겠다.

vector를 사용하는 것이 여러모로 더 편하다.

후에 소개할 정렬(sort)할 때 편리하다.

 

vector<pair<int,int>> p;

vector를 이용해 pair를 선언하였다.

vector를 선언할 때 자료형을 pair<int,int>로 해준 것이다.

 

여기에 한번 값을 넣어볼까?

p.push_back(make_pair(1,2))

이런 식으로 넣어주면 된다.

make_pair()를 하나의 값으로 생각해 주면 된다.

값을 출력해 주거나 확인할 때는 그냥 배열 쓰듯이 쓰면 된다.

p에 가장 처음 push_back 해준 값은 p[0], 그다음 push_back해준 값은 p[1]에 저장되어 있다.

 

 

 

정렬

 

위에서 vector에 값을 넣어 주었다.

이것을 STL sort() 함수를 이용하여 정렬할 수 있다.

sort() 함수에 대한 설명은 이곳에 있다.

C++ STL sort() 정리(2차원배열 정렬, 오름차순, 내림차순) (tistory.com)

C++ STL sort() 정리(2차원배열 정렬, 오름차순, 내림차순)

아래 코드를 보자

 

#include<iostream>
#include<utility>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
    vector<pair<int,int>> p;
    p.push_back(make_pair(3,3));
    p.push_back(make_pair(1,2));
    p.push_back(make_pair(1,1));
}

일단 이렇게 값을 넣어준다면 

정렬 전 vector

 

이렇게 저장되어 있다.

이제 정렬해 주자

 

이렇게 정렬을 해주고 이제 차례대로 출력해 보자

 

#include<iostream>
#include<utility>
#include<algorithm>
#include<vector>
using namespace std;
int main()
{
    vector<pair<int,int>> p;
    p.push_back(make_pair(3,3));
    p.push_back(make_pair(1,2));
    p.push_back(make_pair(1,1));
    sort(p.begin(), p.end());
    for(int i=0; i<3; i++)
    {
        cout<<p[i].first<<' '<<p[i].second<<'\n';
    }
}

 

 

정렬 후 모습

 

first값을 기준으로 오름차순 정렬되었다.

여기서 주목해야 될 점이 (1,1), (1,2)처럼

first값이 같다면 second값을 기준으로 다시 오름차순 정렬되었다는 점이다.

바로 좌표 정렬이 된 것이다.

이 정렬은 백준 문제등 여러 알고리즘 문제를 풀 때 많이 사용된다.

 

정렬 기준을 바꾸고 싶을 수도 있는데

방법을 알려주겠다.

 

bool cmp(pair<int,int>a,pair<int,int>b)
{
    if(a.first==b.first) // first 값이 같다면
        return a.second<b.second; // second값을 기준으로 오름차순 정렬
    else // first값이 다르다면
        return a.first<b.first; // first값을 기준으로 오름차순 정렬
}


sort(v.begin(),v.end(),cmp);

이 코드는 기본 정렬처럼

first값을 기준으로 오름차순 정렬한 후

first값이 같다면 second값을 기준으로 오름차순 하는 정렬이다.

return a.first < b.first라는 말은 first를 기준으로 오름차순으로 정렬하겠다는 말이다.

위 코드를 참고하여 원하는 대로 변형하면 되겠다.

 

 

 

 

 

pair 중첩

 

pair안에 pair를 넣어서 중첩시킬 수도 있다.

바로 이런 식이다. 

pair<type1,typ2> 형식인데

typ1에 pair를 넣은 것이다.

 

pair 구조1

 

구조를 보면 위와 같다.

코드에서 살펴보면 아래와 같다.

 

pair 구조2

 

이렇게 하면 어떤 장점이 있을까?

3개의 정보를 한 번에 저장할 수 있다.

원래 pair에서 2개의 정보를 한꺼번에 저장할 수 있었는데

중첩을 하여 더욱 많은 정보를 한꺼번에 저장할 수 있게 된다.

위의 예시에서는 3개를 한꺼번에 저장하니 3차원 좌표를 저장할 때 유용하다.

이때 어떻게 정보에 접근할까?

생각을 해보면 쉽다.

pair p의 first부분은 pair, second 부분에는 초록 int이 저장되어 있다.

p의 first 부분 pair의 first에는 빨간 int, second 부분에는 파란 int가 저장되어 있다.

 

즉 위의 사진에서 빨간 부분은 p.first.first

파란 부분은 p.first.second

초록 부분은 p.second가 된다.

 

아래 예시 코드이다.

#include<iostream>
#include<utility>
using namespace std;
int main()
{
    pair<pair<int,int>,int> p=make_pair(make_pair(1,2),3); // make_pair도 중첩해서 사용!
    cout<<p.first.first<<'\n'; // 1
    cout<<p.first.second<<'\n'; // 2
    cout<<p.second<<'\n'; // 3
}

 

위 예제 출력 시 1 2 3이 나온다.

값을 넣을 때 어떻게 해주었는지도 보자.

 

 

 

 

이 정도만 익혀둬도 코딩테스트를 진행하는 데 있어 아무 무리가 없다.

익숙해지도록 하자.

 

마지막으로 pair를 응용할 수 있는 백준 문제들을 알려주겠다.

 

 

 

백준 11650 - 좌표 정렬(실버 5)

 

백준 10814 - 나이순 정렬(실버 5)

 

백준 2178 - 미로 탐색(실버 1)(BFS개념 필요)

 

백준 7576 - 토마토(골드 5)(BFS개념 필요)

 

단순 정렬, BFS, DFS 등 광범위하게 응용된다.

자유자재로 다루도록 노력해 보자.

 

 

 

이상 글을 마치겠다.