Tutorial : STL Vector ( 2차원 ) timer 2s memory 1024MB

앞선 문제에서는 1차원 Vector 에 대한 기본 문법을 배웠다.

Vector 은 배열과 매우 비슷한 개념이다.

2차원 배열이 있듯이, 2차원 Vector 도 있을 것이다.

2차원 Vector 가 유용하게 쓰이는 상황을 보자.

"50명의 학생들이 50개의 반 (0반 ~ 49반) 중 하나에 반 배정을 받는다.

학생이 없는 반이 생길 수도 있고, 50명의 학생들이 하나의 반에 몰릴 수도 있다."

위 상황을 우리가 알던 2차원 배열로 저장하면 어떤 문제가 생길까?

2차원 배열은, 각 행마다 열의 개수를 다르게 만들 수 없다.

각 반마다 최대 50명의 학생들이 배정될 수 있으니, 어쩔 수 없이 A[50][50] 처럼 50행 50열로 선언해야 한다.

이러면 굉장히 비효율적이다.

실제로 들어가는 학생은 50명 뿐인데, 이를 위해 총 50 × 50 = 2500개의 칸을 만들어야 하기 때문이다.

만약 0반에 배정되는 학생이 없더라도, 혹시 모르니 0반도 50개의 칸을 만들어 놓는 셈이다.

50명의 학생을 위해 2500개의 칸을 만드니, 2450개의 칸은 그냥 낭비되는 것이다...

하지만 이를 2차원 Vector 로 구현하면 얘기가 다르다.

아래처럼 선언해보자.

vector <int> V[50];

이러면 V[0] ~ V[49] 까지 50개의 1차원 Vector 들이 만들어진다.

이 50개의 Vector 들은 처음에 크기가 모두 0 이다.

즉, 각 반에는 아직 아무 학생도 배정되어 있지 않기 때문에, 메모리도 전혀 사용하지 않는다.

i 번째 반에 x 라는 학생이 배정될 때마다, 그 때만 아래 코드를 실행하면 된다.

v[i].push_back(x);

3반에 5번 학생이 배정되면, v[3].push_back(5) 가 되는 것이다.

이러면 3반의 크기가 1 증가한다. 나머지 반들의 크기는 변하지 않는다.

이 방식은 실제로 데이터가 들어가는 만큼만 메모리를 사용하는 구조다.

50명의 학생들이 전부 0반에 몰렸다고 해보자.

그러면 v[0] 만 50개의 원소를 갖게 되고, 나머지 v[1] ~ v[49] 는 텅 빈 Vector 가 되는 것이다.

메모리도 학생 수에 맞추어 50칸만 만들어진다.

이처럼 2차원 Vector 는 2차원 배열에 비해 메모리 측면에서 매우 효율적이다.

Vector는, 데이터를 넣는 만큼만 메모리를 만들기 때문이다.

<응용 문제>

n 개의 정수 수열이 주어지며, 각 수열은 길이가 각각 다르다.

각 수열을 입력으로 주어진 순서대로 재배치하여 출력하는 프로그램을 작성하라.

Vector 를 사용하지 않으면 0점처리...하는 장치는 따로 없으나, 여러분들 본인의 학습을 위하여 지금 막 배운 Vector 를 사용해서 풀어보자!