[c++] 알고리즘 개념공부 :: 자료구조 - 배열, 문자열

목차

1. 배열
   1. 선언
   2. 초기화
   3. 접근
   4. 다차원 배열
   5. 희소 행렬 표현
   6. 주소와 포인터
      1. 포인터
   7. 특징
   8. 제약
      1. 동적 메모리 할당
      2. 동적 배열(vector)
2. 문자열
   1. 선언
   2. 초기화
   3. 함수

 

배열 / 문자열

배열

배열이란 단일 식별자로 _같은 자료형_의 여러 변수를 접근할 수 있게 해주는 자료구조이다.

선언

c++에서는 int arr[3];와 같이 자료형 배열이름[배열 길이];로 변수를 선언한다. 이 때, 대괄호 내의 요소의 갯수는 '컴파일 타임 상수'여야한다. 소스코드를 컴파일할 때, 고정 배열의 길이를 알아야하기 때문이다. 따라서 매크로 기호 상수 (ex_ #define ARRAY_LEN 5)나 열거자(ex_enum A{ARRAY_LEN = 5})는 배열의 길이로 사용할 수 있다. const 또한 컴파일 시 고정되는 상수이므로 사용가능하다.

c#에서는 readonly와 const가 구분되어 실행시간 / 컴파일 시간에 고정되는 상수를 만들지만 c++에서는 const만 존재한다.

원래 선언되어 있던 변수를 const 변수로 다시 받는다면, c++에서는 실행시간 상수로 처리된다. 따라서 이 경우에는 배열의 길이로 사용할 수 없다.

ex_ int tmp = 5; const int len = tmp; // len이 런타임 상수

 

초기화

배열은 선언과 동시에 초기화해줄 수도 있고, 따로 진행할 수도 있다. 선언과 동시에 초기화를 해준다면, 배열의 길이를 입력할 필요 없이 초기화된 요소의 갯수로 길이가 결정된다.

ex_int arr[]={1,2,3}; // 길이 3

 

배열의 요소들은 초기화에 대한 별다른 코드가 없으면 쓰레기값으로, 초기화해준 요소가 하나라도 있다면 나머지 요소들은 0으로 초기화된다.

ex_

int arr[5]={1,2,3}; // 1,2,3,0,0
int arr[5]; // 쓰레기 값
int arr[5]={0}; // 0,0,0,0,0

 

배열에 기본값을 채우는 여러 방식은 아래의 글에 정리해두었다.

기본값 채우기

 

접근

각 요소들은 0부터 시작하는 offset을 이용하여 arr[0],arr[1]과 같이 접근한다.

 

다차원 배열

배열은 차원을 늘려가며 사용할 수 있다. 선언은 int arr[2][5]와 같이 n차원의 경우 n개의 대괄호를 사용하여 나타내며, 맨 앞의 대괄호 속의 길이 제외 모든 길이를 표시해두어야한다.

ex_ int arr[][5]; // 생략된 길이는 초기화 시 결정된다.

 

실제 메모리에 저장될 때는 1차원 배열과 마찬가지로 메모리 상에서 연속해서 저장되는데, 이 때 뒤에 있는 대괄호를 우선적으로 배치된다. 위의 예제에서는 행 우선순위 방식으로 메모리에 배치되었다.

초기화 시 1차원 배열과 마찬가지로 int arr[2][3]={1,2,3,4,5,6}; 순차적으로 들어갈 데이터를 적어줄 수도 있고, 논리적인 구조로도 가능하다.

int arr[2][3]={
    {1,2,3},
    {4,5,6}
}

배정되는 배열의 요소 값도 1차원 배열과 같은 로직이다.

 

희소 행렬 표현

1. 모든 요소를 저장하는 방법
   • -) 공간이 낭비된다.
   • +) 행렬의 연산들을 간단하게 구현할 수 있다.
2. 0이 아닌 요소만 저장하는 방법 (행, 열, 값 을 저장)
   • -) 행렬 연산들의 구현이 복잡해진다.
   • +) 공간이 절약된다.

 

주소와 포인터

배열의 이름은 해당 배열 자료구조가 할당된 메모리의 시작주소를 의미한다. 이 주소를 이용하여 증가 감소 연산자로 배열의 전후 요소를 받아올 수 있다. 즉, 증감 연산자가 배열의 기초 자료형을 단위로 작용한다. 이는 요소들이 메모리 상에 연속하게 할당되기 때문에 가능하며, 증감 연산자는 반복문과 함께 유용하게 쓰인다. 아래는 배열의 모든 요소를 출력하는 코드이다.

int arr[5] = { 1,2,3,4,5 };
for (int i = 0; i < sizeof(arr)/sizeof(int); i++) {
    cout << *(arr)+i; // 12345
}

메모리 상 주소를 더 폭넓게 활용하려면 포인터를 사용하면 된다.

(포인터 정리)

 

특징

연결 리스트와는 달리 offset을 통해 임의접근할 수 있다.

 

제약

지금까지 살펴본 array, 즉 고정 배열은 컴파일시간에 메모리에 할당되기 때문에 실행시간에 배열의 길이를 결정할 수 없다. 따라서 기존에는 _동적 메모리 할당_을 사용해서 배열의 길이를 실행시간에 결정했는데, 현재 c++은 _동적 배열_이라는 개념 또한 지원한다.

 

동적 메모리 할당

일반적으로 변수는 컴파일 단계에서 변수의 크기가 전해진다. 이 후, 실행시간에 변수의 크기를 정하기 위해 동적 메모리 할당이 등장했다. 뒤에 등장할 동적 배열은 실행시간에 정적으로 변수의 크기를 정해서 메모리를 할당하는 '동적 메모리 할당'과 달리 변수의 크기 자체도 계속해서 변화할 수 있는 구조라는 점에서 구분된다. 메모리 동적 할당 시 heap 영역에 변수가 할당된다.

대부분 malloc 함수를 이용해서 heap 영역에 메모리를 할당받은 후, free 명령어로 메모리를 해제해준다.

int* a = (int*)malloc(sizeof(int) * 5);
cout << _msize(a); // 20
free(a);
cout << _msize(a); // error

sizeof로 a의 크기를 측정하려 하면 int* 형인 주소의 크기가 나오기 때문에, 실제 heap에서 사용한 메모리 크기를 측정하려면 _msize를 이용해야한다.

 

자세한 설명은 따로 포스팅하겠다.

(동적 메모리 할당 정리)

(메모리 영역 정리 필요)

(가비지 콜렉션 / 힙 메모리 관리 정리 필요)

 

동적 배열 (vector)

vector는 길이가 변할 수 있는 동적인 배열로써 별도의 라이브러리를 포함한 후 사용할 수 있다. 배열과 같이 메모리에 연속적으로 저장되기 때문에, offset을 이용하여 임의접근할 수 있다. 따라서 vector는 순차적 동적 컨테이너이다.

실행시간 중 요소를 추가하여 사이즈가 늘어나면 새로운 배열을 할당한 후 모든 요소를 이동시키는 방법을 기본적으로 사용하지만, 이로 인해 발생하는 오버헤드를 줄이기 위해 할당 시 여유공간을 둔다.

다른 동적/순차 컨테이너인 deque, list, forward-list와 비교하면, 컨테이너 end에서의 삽입 / 삭제 연산은 효율적이지만 다른 위치에서의 연산은 비효율적이다.

 

<생성>

import <vector>; 로 c++ STL인 vector를 불러온 후, vector<int> vec;과 같이 vector<자료형> 벡터이름으로 변수를 생성한다.

STL : Standard Template Library (표준 템플릿 라이브러리)

 

<초기화>

vector에 기본값을 채우는 여러 방식은 아래의 글에 정리해두었다.

(기본값 채우기 링크)

자세한 설명은 STL을 따로 정리해서 올리겠다.

(STL 정리)

 

문자열

문자열은 char 자료형의 배열이다. 정확히 말하자면 bytes의 배열인 basic_string의 한 예로 char형을 사용하는 string class가 있고 이것이 문자열이다. UTF-8과 같은 multi-byte나 여러 길이의 char 자료형을 다루더라도, string class의 멤버 함수들은 byte단위로 동작하기 때문에 인코딩에는 제약이 없다.

(인코딩 종류 정리)

C++에서는 주로 import <string>;으로 string 라이브러리를 불러와서 사용한다.

 

선언

string 변수이름;과 같이 선언한다.

 

초기화

초기화는 선언과 동시에 constructor에게 초기화할 문자열을 넘겨줄 수도 있고, 따로 초기화할 수도 있다. constructor에는 대괄호("")로 묶인 문자열 뿐만 아니라 다른 string 객체도 전달될 수 있다.

ex_ string s = "hi"; string s("hi"); string s1(s);

constructor에 (숫자, 문자)을 넘기면 해당 문자열을 숫자만큼 반복해서 저장하며, (문자열, 숫자1, 숫자2)를 넘기면 해당 문자열을 offset이 숫자1인 곳부터 숫자2 만큼 저장한다. 전자(前者)의 상황에서 문자에는 숫자가 들어가도 되지만, 이는 아스키코드에 의해 변환되어 저장된다.

ex_ string s1(10,'x'); // xxxxxxxxxx

string s1(10,42); // **********

 

함수

• size : 문자열의 크기를 byte 단위로 return
• length : size 함수와 같음
• [] : 각 요소에 접근
• at : [] 연산자와 같음
• back / front : 마지막, 처음 문자에 접근
• append : 기존 문자열에 더하기
• += : append 함수와 같음
• push_back /pop_back : 문자 하나를 기존 문자열에 더하기
• assign : 넘겨준 매개변수를 string화 하여 변수에 넣기string str; str.assign("heeeun is cool",6); // heeeun
• string str; str.assign(10,*); // **********
• insert : 넘겨받은 위치에 넘겨받은 문자열 삽입
• erase : 넘겨받은 위치부터 넘겨받은 문자갯수만큼 삭제
• find : 넘겨받은 문자열에 시작하는 위치 반환, 없다면 npos 반환
• compare : 넘겨받은 문자열과 기존의 문자열 비교
• 0: 같음
• substr : 넘겨받은 위치에서 넘겨받은 문자갯수만큼 잘라서 반환

참고 ) http://www.cplusplus.com/reference/string/string/