[바킹독의 실전 알고리즘] 0x03 배열 복습 -C++

앞으로 작성할 내용들은 유튜브에서 바킹독님의 알고리즘 강의를 들은 내용을 토대로 하여,

필요할 경우 전공으로 배운 내용을 조금씩 엮어 복습한 내용입니다.

(이것은 다 ~ 개강 전까지 그동안 굳어있던 머리를 활성화 시키기 위한 발악인 것입니다...)

바킹독의 실전 알고리즘 0x03강 링크

 

강의내용 복습

배열의 정의와 성질

*프로그래밍 언어의 관점에서의 배열과 달리, 바킹독님 강의의 자료구조로써의 배열에서는 길이를 마음대로 늘리거나 줄일 수 있다고 생각한다.

 

배열 : 메모리 상에 원소를 연속하게 배치한 자료구조

 

배열의 성질

1. O(1)에 k번째 원소를 확인/변경 가능

    메모리 상에 원소를 연속하게 배치한 자료구조이기 때문에 시작주소에서 k칸 만큼 오른쪽으로 갈 수 있다.

2. 추가적으로 소모되는 메모리의 양(=overhead)가 거의 없음

    다른 자료구조를 배우고 나서 비교해보기

3. Cache hit rate가 높음

    캐시 메모리 적중률 = 적중 횟수 / 총 접근 횟수

4. 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림

 

배열의 기능과 구현

O(1)

배열의 임의의 위치에 있는 원소를 확인/변경

배열의 끝에 원소를 추가(끝자리에 값을 쓰고 길이를 1 증가)

배열의 마지막 원소를 제거(길이를 1 줄이면 됨)

 

O(N)

임의의 위치에 있는 원소를 추가/제거

ex. 2번 원소를 지우고 그 이후 모든 원소를 한칸씩 땡김 -> 배열의 정의 '연속' 생각 !

#include <bits/stdc++.h>
using namespace std;

void insert_test();
void erase_test();
void insert(int idx, int num, int arr[], int& len);
void erase(int idx ,int arr[], int& len);
void printArr(int arr[], int& len);


int main(void) {
  insert_test();
  erase_test();
}

void insert_test(){
  cout << "***** insert_test *****\n";
  int arr[10] = {10, 20, 30};
  int len = 3;
  insert(3, 40, arr, len); // 10 20 30 40
  printArr(arr, len);
  insert(1, 50, arr, len); // 10 50 20 30 40
  printArr(arr, len);
  insert(0, 15, arr, len); // 15 10 50 20 30 40
  printArr(arr, len);
}

void erase_test(){
  cout << "***** erase_test *****\n";
  int arr[10] = {10, 50, 40, 30, 70, 20};
  int len = 6;
  erase(4, arr, len); // 10 50 40 30 20
  printArr(arr, len);
  erase(1, arr, len); // 10 40 30 20
  printArr(arr, len);
  erase(3, arr, len); // 10 40 30
  printArr(arr, len);
}

void insert(int idx, int num, int arr[], int& len){
    len++;
    for(int i = len-1; i > idx; i--)
    {
        arr[i] = arr[i-1];
    }
    arr[idx] = num;
}

void erase(int idx, int arr[], int& len){
    for(int i = idx; i < len-1; i++)
    {
        arr[i] = arr[i+1];
    }
    len--;
}

void printArr(int arr[], int& len){
  for(int i = 0; i < len; i++) cout << arr[i] << ' ';
  cout << "\n\n";
}

출력 결과

 

전체를 특정 값으로 초기화 시킬 때, 효율적으로 초기화 시키는 방법

1. for문을 돌면서 값을 하나하나 다 바꾸는 방식 -> 내가 기존에 쓰던 방법

2. algorithm 헤더의 fill 함수를 이용 -> 가장 추천 !!

     first는 초기화 하고 싶은 부분의 시작 주소, last는 끝 주소, val은 초기화할 값이다.     

     first는 포함하고, last는 포함하지 않음을 주의한다. [first, last)

void fill (ForwardIterator first, ForwardIterator last, const T& val)

#include <algorithm>

int main(void){
	int a[21];
	int b[21][21];
	
	//fill 함수 사용
	std::fill(a, a+21, 0); //1차원 배열 
	for(int i = 0; i < 21; i++) //2차원 배열 
	{
		std::fill(b[i], b[i]+21, 0);
	}
}

검색해보니 2차원 배열의 경우 다음처럼 사용할 수도 있다.

fill(&arr[0][0], &arr[ROW -1][COL], value)

fill(&arr[0][0], &arr[0][0] + ROW*COL, value)

 

STL vector

vector는 배열과 거의 동일한 기능을 수행하는 자료구조이다.

배열과 마찬가지로 원소가 메모리에 연속하게 저장되어 있기 때문에 O(1)이며, 인덱스를 가지고 각 원소로 접근 가능하다.

크기를 자유자재로 늘이거나 줄일 수 있다는 점에서 배열과 차이가 있다.

#include <vector> 헤더파일 포함해야한다.

 

*자세히 알고 싶으면 참고

http://www.cplusplus.com/reference/vector/vector/

vector - C++ Reference

 

vector 사용예시

#include <bits/stdc++.h>
using namespace std;

int main(void) {
  vector<int> v1(3, 5); // {5,5,5}, 3개의 원소를 가지는 int형 vector v1 생성 후 5로 초기화
  cout << v1.size() << '\n'; // 3, vector v1의 원소 갯수
  v1.push_back(7); // {5,5,5,7}, vector v1의 끝에 7 추가

  vector<int> v2(2); // {0,0}, 2개의 원소를 가지는 int형 vector v2 생성, 기본값(0)으로 초기화
  v2.insert(v2.begin()+1, 3); // {0,3,0}, vector v2의 인덱스 1에 3 삽입

  vector<int> v3 = {1,2,3,4}; // {1,2,3,4}, int형 vector v3 생성, 1,2,3,4로 초기화
  v3.erase(v3.begin()+2); // {1,2,4}, vector v3의 인덱스 2 제거

  vector<int> v4; // {}, int형 vector v 생성
  v4 = v3; // {1,2,4}
  cout << v4[0] << v4[1] << v4[2] << '\n';//124
  v4.pop_back(); // {1,2}, vector v4의 끝에 있는 값 삭제
  v4.clear(); // {}, vector v4의 모든 값 삭제
}

v.begin() : vector v 시작점 주소

v.begin()+x : vector v의 인덱스 x 주소

v.end() : vector v의 끝+1 주소

*STL의 iterator 개념 추가 공부 필요, vector<int>::iterator 타입

 

vector에서 =를 사용하면 deepcopy 발생. v4=v3; 이후 v4를 바꿔도 v3에는 영향없음.

 

insert, erase는 배열과 비슷하게 시간복잡도 O(N)

push_back, pop_back는 O(1)

 

range-based for loop : vector에 있는 모든 원소를 순회하는 방법

c++11부터 지원하며, vector 외에도 list, map, set등에서도 사용 가능하다.

vector<int> v1 = {1,2,3,4,5,6};

//1. range-based for loop (c++11부터 지원)
for(int e : v1) //e에 v1의 원소들이 하나씩 들어가는 for문
	cout << e << ' ';

//2. not bad
for(int i = 0; i < v1.size(); i++)
	cout << v1[i] <<' ';

//3. WRONG
for(int i = 0; i <= v1.size()-1 ; i++)
	cout << v1[i] << ' ';

range-based for loop를 쓸 때 주의점

1.

int e : v1이라 하면 v1에서 복사된 값이 e로 들어감

int& e : v1이라 하면 v1의 원본이 e로 들어가기 때문에 e를 바꾸면 원본인 v1에서도 해당 원소의 값이 바뀜

2.

기본적으로 vector의 size 메소드는 시스템에 따라 unsigned int 혹은 unsigned long long을 반환한다.

3번 WRONG case에서 v1이 빈 vector일 경우 v1.size()-1은 (unsigned int)0 - (int)1이고, unsigned int와 int를 연산하면 unsigned int로 자동 형변환이 발생하기 때문에 연산 결과는 -1이 아니라 4294967295가 된다. (unsigned int overflow!)

연습문제 복습(C++)

강의 후반부 및 아래 링크로 들어가면 나오는 문제들 중 해당 강의에 맞는 연습문제들을 풀고

정답코드와 비교하며 얻은 내용들을 간단히 정리한 내용입니다.

연습문제 링크

 

1. 범위기반 for문 (range based for)에서 auto keyword 사용가능

#include <bits/stdc++.h>
using namespace std;

int main(void){
    string word;
    cin >> word;
    int a[26] = {0,};
   // for(int i = 0; i < word.length(); i++)
   // {
   //     a[word.at(i) - 'a']++;
   // }
    for(auto c : word) //auto를 적으면 굳이 자료형을 적어주지 않아도 됨
    {
        a[c-'a']++;
    }

    for(int i = 0; i< 26; i++)
    {
        cout << a[i] << " ";
    }
}

 

2. 시간복잡도 O(N)인(이중반복문 사용X), int 배열 arr에서 합이 100인 서로 다른 위치의 두 원소가 존재하면 1을, 아니면 0을 반환하는 함수

     arr[i] 이전의 원소에 i와 합이 100이 나왔는지 체크할 배열을 만들어서 해결!

int func2(int arr[], int N){   
    int check[101] = {0, }; // arr[i] 이전의 원소에 arr[i]와 합이 100이 나왔는지 체크할 배열
    				// int count[101] = { }; 0으로 초기화하는법
    for(int i = 0 ; i < N; i++)
    {
        int m = arr[i];
        if(check[100-m] == 1) // if(count[100-m])이라고만 써도 동작함
        {
            return 1;
        }
        check[m] = 1;
    }
    return 0;
}

 

3. <algorithm> 헤더의 max, min 함수

min(a, b); //a와 b중 작은값 반환
max(a, b); //a와 b중 큰값 반환

#include <bits/stdc++.h>
using namespace std;

int main(void){
    cout << min(1, 5) <<"\n"; //1 출력
    cout << min('A', 'B') <<"\n"; //A 출력

    cout << max(1.234, 5.6789) <<"\n"; //5.6789 출력
    cout << max(5, 5) <<"\n"; //5 출력
}

 

4. int a[1000001] = {};과 같이 main 함수 안에 선언된 배열의 크기가 매우 클 경우, 프로그램이 자꾸 입력을 받기도 전에 꺼지는 문제가 있었다. 구글링좀 해보다가 배열은 전역변수로 바꿔 선언하니 매우 잘 돌아가더라...

 

5. 배열 두개 선언할 필요없이 하나로도 가능한 상황

	//A와 B를 이루는 문자의 종류와 각 문자의 갯수가 같은지 비교하고자 할 때
	//수정 전 : a, b 두 배열을 선언해서 두 배열의 원소가 같은지 비교
	string A, B;
	int a[26]={}, b[26]={};
	cin >> A >> B;
	for(auto c : A) a[c - 'a']++;
	for(auto c : B) b[c - 'a']++;
    
	//수정 후 : a배열 하나만 선언해서 최종적으로 a배열의 모든 원소가 0인지 확인
	string A, B;
	int a[26]={};
	cin >> A >> B;
	for(auto c : A) a[c - 'a']++;
	for(auto c : B) a[c - 'a']--;

 

6. cin

cin은 표준 입력 버퍼에서 개행문자를 제외한 값을 가져온다.(개행문자는 입력 버퍼에 남아있음)

cin은 공백이나 개행 입력 시 공백 이전까지의 값만 결과로 받아들인다.

cin은 처음 입력된 white space는 무시한다. (엔터, 탭, 띄어쓰기)

만약 개행문자와 공백을 모두 저장하고 싶다면 getline을 사용한다.

string s;
getline(cin, s);