[C++] 기초부터 공부하기 (2. 이차원 배열 정렬 feat.좌표 정렬하기)

지난번에 이어 이번에도 C++ 기초를 공부하려고 한다! 백준 문제를 풀면서 C++에 익숙해지는 것을 첫번째 목표로 두고 있기 때문에 쉬운 문제 위주로 생각하려고 한다. 

 

1) C++ 기초(Vector)

 문제를 풀면서 이차원 배열을 사용할 일이 생겼는데 C에서 쓰는 기초적인 이차원 배열을 쓰려고 했더니 C++에는 vector이 있다는 것을 깨닫고 이것에 대한 기초를 조금 알아보고자 한다.

 

1-1) Vector?

 

 vector은 C++ STL(Standard Template Library: 이미 만들어진 탬플릿을 이용하기 위해서 사용됨)에 속하며 배열처럼 원소들을 순서대로 보관하는 Sequence Container에 속한다. 한 문장으로 vector을 정리하자면 "자동으로 메모리가 할당되는 배열"이라고 할 수 있으며 heap 메모리에 동적으로 할당이 된다. 또한 데이터 타입이 자유롭게 이용가능하고 원소의 삽입과 삭제가 효율적인 메모리 관리하에 매우 원활하다는 특징을 가지고 있다. 또 중간의 원소를 삭제하거나 크기를 구하는 등의 유용한 함수들이 많다는 특징을 가지고 있다.

 

  Vector VS Array: vector는 메모리 재할당이 용이한 것에 비해 array는 선언시 메모리가 고정된다. 그렇기 때문에 저장할 데이터의 개수가 가변적이라면 vector을 사용하는 것이 좋다. 다만 vector은 포인터를 통한 접근이기 때문에 속도 측면에서 array가 더 빠르다.

 

 vector을 사용해야할 케이스: 저장할 데이터 개수가 적거나 많아도 비번하게 검색되지 않을 경우에 써야한다. 검색을 자주한다면 map이나 set,hash_map이 효율적일 수 있다. 또한 어디까지나 배열 기반 컨테이너이기 때문에 push_front와 같은 기능이 지원되지 않아 중간에 데이터 삽입이나 삭제가 많이 일어나지 않은 경우에 사용해야한다.

 

1-2) 2차원 백터 기본 코드 및 초기화

 

vector<vector<int>> v; : 벡터를 선언할 때 자료형을 벡터로 선언하면 벡터 자료형을 담을 수 있는 벡터 자료형으로 사용할 수 있음

vector<int> tmp; v.push_back(tmp); : 벡터에 자료를 넣을 때는 1차원 벡터를 선언해서 값을 저장한 뒤 2차원 벡터에 삽입할 수 있다.

cout<<v.at(0).at(0); : 2차원 배열의 첫번째 원소에 접근한다. 값을 push_back한 이후에 접근할 수 있다.

cout<<v[0][0]; : 배열과 같이 인덱스로 접근할 수 있다.

 

벡터의 행과 열의 크기를 아는 경우 다음과 같이 벡터의 크기를 초기화 할 수 있다.

vector<vector<int>> tmp(n,vector<int>(m)); : N*M만큼 2차원 벡터 공간만 확보

vector<vector<int>> tmp(n,vector<int>(m,0)); : N*M만큼 2차원 벡터 0으로 값 초기화

 

 

1-3) pair을 이용한 백터 선언

  Pair 이란? 

  pair은 두 객체를 하나로 묶어주는 역할을 하는 컨테이너로 이차원 배열처럼 사용할 때 백터와 묶어 사용할 수 있다.

pair<int ,int> tmp

와 같은 형식으로 int형과 int형 pair tmp를 선언한다는 의미이고 make_pair(a,b)를 통해 a,b를 쌍으로 하는 값을 표현할 수 있다.

 

따라서 이 두 개를 종합하여 이차원 배열을 pair을 이용하여 선언하면 vector<pair<int,int>> tmp가 된다.

 

1-4) 이차원 vector 구현

 vector<pair<int,int>> v1를 통해 pair을 이용한 이차원 vector v1을 선언한다.

 v1.push_back(make_pair(a,b))를 통해 a와 b를 하나의 pair로 만들고 이를 v1 vector에 저장한다.

 printf("%d %d\n",v1[i].first,v1[i].second)  를 통해  출력 가능하다.

 

 

2) Sort 함수 3번째 인자!!

sort 함수 원형은 void sort(T start, T end)이며 3번째 인자를 넣지 않으면 default로 오름차순 정렬이 되고 인자를 넣으면 정의한 기준에 따라 정렬이 가능하다.

• sort(arr, arr+n);
• sort(v.begin(), v.end());
• sort(v.begin(), v.end(), compare);                //사용자 정의 함수 사용
• sort(v.begin(), v.end(), greater<자료형>());    //내림차순 (Descending order)
• sort(v.begin(), v.end(), less<자료형>());        //오름차순 (default = Ascending order)

이때 3번째 줄과 같이 사용자 정의 함수를 이용하여 임의로 배열을 정렬할 수 있다. 아래 문제와 같은 경우에서는  좌표를 x좌표가 증가하는 순으로, x좌표가 같으면 y좌표가 증가하는 순서로 정렬해야하므로 새로운 함수를 만들어야한다. 

 

이때 함수는 bool로 만들어주고 오름차순으로 정렬해줘야하기 때문에 처음받은 수보다 두번째 받은 수가 작다면 0을 반환해주도록 만들어야 한다. 이때 주의해야할 점은 compare 함수를 만들때 main함수에서도 pair로 묶었기 때문에 compare 함수가 받는 인자도 pair이 되도록 구현해야한다.

 

 

3) 이차원 배열 정렬하기

https://www.acmicpc.net/problem/11650

11650번: 좌표 정렬하기

 위에 나온 내용들을 통해 구현하면 문제를 쉽게 풀 수 있다.

 

이 모든 것을 종합하여 문제를 풀면 아래 소스코드와 같다

 

#include <iostream>
#include <ostream>
#include <algorithm>
#include<bits/stdc++.h>

using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역

bool compare_v(pair<int,int>tmp1,pair<int,int>tmp2)
{
  bool result;
  if(tmp1.first==tmp2.first)
  {
    result=tmp1.second<tmp2.second?1:0;
    return result;
  }
  return result=tmp1.first< tmp2.first? 1:0;
}

int main() {  
  
  int n;
  cin>>n;
  //vector<vector<int>> v(n,vector<int>(2));
  vector<pair<int,int>> v1;
  for(int i=0;i<n;i++)
    {
      int tmp1,tmp2;
      cin>>tmp1>>tmp2;
      v1.push_back(make_pair(tmp1,tmp2));
    }
  sort(v1.begin(),v1.end(),compare_v);

  for(int i=0;i<n;i++)
    {
      printf("%d %d\n",v1[i].first,v1[i].second);
    }

}

 

근데 풀고 나서 생각을 해보니 이미 main함수에서 pair을 만들었다면 sort 함수에서 정렬을 할때 자동으로 첫번째부터 정렬하고 같으면 두번째를 정렬하도록 작동이 되어있었다. 이를 이용하여 코드를 간략히 만들면 아래와 같다

 

#include <iostream>
#include <ostream>
#include <algorithm>
#include<bits/stdc++.h>

using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역

int main() {    
  int n;
  cin>>n;
  vector<pair<int,int>> v1;
  for(int i=0;i<n;i++)
    {
      int tmp1,tmp2;
      cin>>tmp1>>tmp2;
      v1.push_back(make_pair(tmp1,tmp2));
    }
  sort(v1.begin(),v1.end());

  for(int i=0;i<n;i++)
    {
      printf("%d %d\n",v1[i].first,v1[i].second);
    }

}