JUNGOL...173

Intermediate_Coder/그래프탐색-DFS/Tutorial: STL vector 1

---

문제                                            

여러분이 만든 프로그램은 항상 어떤 비용(cost)을 지불한다.
비용이란 돈을 뜻하는 것이 아니라, 컴퓨터가 프로그램을 실행함으로써 소모하는 자원을 뜻한다.

프로그램 작성 과정에서 여러분들이 제일 많이 고민하게 되는 비용은 크게 두 가지,프로그램 실행시간과 사용 메모리(쉽게말해 시간과 공간)일 것이다.
오늘은 이중에서도, 공간 절약(메모리 절약)의 방법으로써 벡터(vector)를 사용하는 방법을 배워보도록 한다.

우선 정적(static)이라는 말과, 동적(dynamic)이란 말의 차이를 알아보자.

배열을 정적(static)으로 선언한다는 것은 아래와 같이 선언 단계에서 배열의 크기를 미리 정해놓는다는 뜻이다.
여러분들이 늘 사용하는 방식이다.​

 

int arr[ 1010 ]; /// 숫자 배열
char name[ 510 ][ 30 ]; /// 1차원 문자열 배열 (또는 2차원 문자 배열, 해석하기 나름)
Data list[ 110 ]; ///struct를 통해 만든 Data형 배열

 

배열을 동적(dynamic)으로 선언한다는 것은 아래와 같이 선언 단계에는 배열의 크기가 얼마일지 모르고, 입력값에 따라 배열의 크기를 맞추어서 선언하는 것을 말한다. 
이를 포인터 단원에서 배우긴 했겠지만, 아래 코드는 굳이 이해가 안되더라도 포인터를 복습하러 갈 정도로 중요하지는 않으므로, 모르겠다면 자연스럽게 그냥 스크롤을 내리자.​ 

 

int n;
int* arr;
scanf("%d",&n);
arr = new int[n+5];

 

그러나 new 키워드를 가지고 위와 같은 방식으로 동적배열을 선언하는 것은, 한 번 new 키워드로 정한 배열의 크기를 변경하는 것이 쉽지는 않다.

따라서, 찐으로 편한 완전한 동적배열, 내 맘대로 크기를 늘였다 줄였다 할 수 있는 배열이라고는 생각하기 어렵다. 이를 여러분이 쓰기 조금 더 편하게 만들어놓은 배열이 바로 벡터(vector)이다.

(참고로 기하학에서의 벡터와는 조금 다르므로, 구분해서 생각해야 한다. 아래에서도 반복적으로 강조하겠지만, 여기서 설명하는 벡터는 그냥 배열이다.)

 

따라 쳐 보자

 

크기 n(≤100)의 배열을 입력받아, 그대로 출력하는 프로그램인 아래 예시를 보자. 

 

#include <stdio.h>
 
int main()
{
    int n;
    int arr[ 110 ]; /// (늘 쓰던) 정적 배열 선언
    scanf("%d",&n);
    for(int i = 0 ; i < n ; i++ ) scanf("%d",&arr[i]);
 
    ///고전적인 방식    
    for(int i = 0 ; i < n ; i++ ) printf("%d " , arr[i]); ///고전적인 for문으로 n개의 원소 출력
    printf("\n");
 
    ///range based for문
    for(int x : arr)printf("%d " , x); ///range based for문으로 출력, 110개의 원소를 모두 출력하게 됨(맨앞에서부터 n개 이외에는 쓰레기값)
    return 0;
}

 

​배열의 크기가 110으로 고정되어 있기 때문에 생기는 문제점은 다음 두 가지이다.

 

1. 만약 n이 5라고 가정하자. 그런 경우에는 크기 110의 배열에서 앞의 5칸만큼의 메모리만 사용하는 것이고, 나머지 105칸은 모두 낭비되는 메모리로 전락하게 된다. 만약 문제에서 주어진 배열의 최대 크기가 100이 아니라 100만이었다면, 이런 류의 메모리 낭비는 더욱 심해질 것이다.

2. range based for문을 쓰게 될 경우 110개의 모든 원소를 순회하게 되므로, 실제로는 쓰이지 않는 공간 역시 순회하게 되는 문제점이 생긴다.

 

따라 친 코드를 수정해 보자

 

위 코드를 vector를 이용하여 개선하면 다음과 같이 쓸 수 있다. ​ 

 

#include <stdio.h>
#include <vector>
using namespace std;
 
int main()
{
    int n,element;
    ///int arr[ 110 ]; /// (늘 쓰던) 정적 배열 선언...은 주석처리해버리자.
    vector<int> arr;   /// 크기 0의 int형 동적 배열 선언. 
    scanf("%d",&n);
    for(int i = 0 ; i < n ; i++ ){
        scanf("%d",&element);
        arr.push_back(element); /// 배열의 크기를 하나 늘려주면서, 맨 뒤에다가 원소 element를 삽입
    }
 
    ///고전적인 방식    
    for(int i = 0 ; i < (int)arr.size() ; i++ ) printf("%d " , arr[i]); ///고전적인 for문으로 n개의 원소 출력. n이 없더라도 size()로 구할 수 있다.
    printf("\n");
 
    ///range based for문
    for(int x : arr)printf("%d " , x); ///range based for문으로 출력. 배열 크기가 원소 개수와 일치하므로 문제없음. 고전적인 방식보다 가독성 훨씬 높음.
    return 0;
}

 

주목해야 할 것은 push_back()이라는 메소드 함수이다. 배열의 (arr.size())크기를 하나 늘려주면서, 새로 생긴 뒷공간에 매개변수로 받은 원소를 삽입해 준다.

이렇게 push_back을 통해 구성한 벡터는 일반 배열처럼 사용할 수 있다는 것을 쉽게 알 수 있다.

너무 중요한 말이라 다시 한번 강조한다.

벡터=배열이다. 단지 크기를 늘였다 줄였다 할 수 있다는 차이점이 있을 뿐이다! 벡터 사용을 무서워하지 말라! 그냥 배열이니깐!

 

이 시점까지의 설명이 이해가 되었다면, 아직 메모리 절약이 왜 필요한지, 혹은 벡터를 언제 써야 할지에 대해 감이 안 올 수도 있다. 

이를 이해하기 위해 아래 문제를 풀어보고, 다음으로 넘어가도록 하자.

 

- 문제 -

 

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

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

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

 

입력 형식                                     

첫 줄에 n이 주어진다. n은 수열의 개수이다.

다음 n줄에 걸쳐 각 수열의 정보가 아래와 같이 주어진다:

각 줄의 첫번째 정수 ni는 그 수열의 길이이다. 다음으로 주어지는 ni개의 정수는 그 i번 수열을 구성하는 원소이다.

마지막 줄에는 각 수열이 재배치될 순서를 나타내는 n개의 정수 ai가 공백을 사이에 두고 주어진다. 

 

제약조건

 

1≤n≤1,000 , 1≤ni≤100,000.

 

모든 수열의 원소들의 총 개수를 다 합해도 100만개를 넘지 않는다.

(즉 n ≤ n0+n1+...+nn-1 ≤ 1,000,000)

 

각 수열의 원소들은 1이상 10만 이하이다.

ai는 0부터 n-1까지의 정수가 한 번씩만 입력된다.​

 

출력 형식                                     

입력된 순서대로 각 수열을 재배치하여 출력한다. 자세한 사항은 입출력예시를 참고한다.​

 

입력 예                                        

4
5 1 2 3 4 5
7 1 1 2 3 5 8 13
3 1 10 100 
8 256 128 64 32 16 8 4 2
2 0 3 1

 

출력 예                                        

1 10 100
1 2 3 4 5
256 128 64 32 16 8 4 2
1 1 2 3 5 8 13

 

Hint!

n개의 원소가 들어오는 배열을 입력받고 출력하는 프로그램은 다음과 같이 쓰는 방법도 있다.

#include <stdio.h>
#include <vector>
using namespace std;
 
int main()
{
    int n;
    scanf("%d",&n);
    vector<int> arr(n); ///먼저 n개의 원소를 가진 배열 arr을 선언.
 
    for(int& x : arr)scanf("%d",&x);   ///arr의 모든 원소 x에 대해서,(x값이 입력의 결과로써 변하므로 참조형(&)사용!)
    for(int  x : arr)printf("%d ", x); ///arr의 모든 원소 x를 출력.
    
    return 0;
}

---

STLVector1.h

#include <iostream>
#include <vector>

using std::vector;

 

STLVector1.cpp

void STLVector1::Code()
{
	int n;
	std::cin >> n;

	vector<vector<int>> numberList;
	for (int i = 0; i < n; i++)
	{
		int length;
		std::cin >> length;

		numberList.push_back(vector<int>());
		for (int j = 0; j < length; j++)
		{
			int temp;
			std::cin >> temp;

			numberList[i].push_back(temp);
		}
	}

	for (int i = 0; i < numberList.size(); i++)
	{
		int idx;
		std::cin >> idx;

		for (int j = 0; j < numberList[idx].size(); j++)
		{
			std::cout << numberList[idx][j] << ' ';
		}
		std::cout << '\n';
	}
}

 

---

실행 결과 Success(100)

---

 

NadanKim/CodingTest_JUNGOL: JUNGOL 코딩 테스트를 위한 저장소 (github.com)

NadanKim/CodingTest_JUNGOL

 

문제출처

Intermediate_Coder/그래프탐색-DFS/Tutorial: STL vector 1-JUNGOL