[바킹독] 0x03강 - 배열 메모

들어가며

뒤에 메모가 붙은 포스팅의 경우,

공부한 모든 것들을 정리하지 않고 내가 몰랐던 것, 체크하고 다시 보고 싶은 것만 적어 두고 있습니다.

 

+ 딱 20000점인 게 신기해서 넣어 봄

 

++ 나중에 다시 정리를 할지는 모르겠는데 적어도 처음 들을 때는 그냥 강의 듣기랑 문제 풀이만 하기로 했다.

이유: 블로그 작성보다 알고리즘 문제 하나 더 푸는 게 당장 도움이 더 될 것 같음.

 

 

강의

블로그

[실전 알고리즘] 0x03강 - 배열

유튜브

 

 

문제집

깃 헙

basic-algo-lecture/workbook/0x03.md at master · encrypted-def/basic-algo-lecture

백준

 

 

배열의 성질

1. O(1)에 k번째 원소를 확인/변경 가능
2. 추가적으로 소모되는 메모리의 양(=overhead)가 거의 없음
3. Cache hit rate가 높음
4. 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림

 

 

경우 별 시간 복잡도

O(1)

• 임의의 위치에 있는 원소를 확인/변경
• 원소를 끝에 추가
• 마지막 원소를 제거

O(N)

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

 

 

array_test

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

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

	arr[idx] = num;

	len++;
}

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";
}

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);
}

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

 

핵심

insert는 뒤에서부터

erase는 앞에서부터

 

 

O(n^2)을 O(n)으로 줄이기

 

알파벳, 1부터 100까지의 숫자 등, 한정된 작은 범위 내의 입력만 들어올 경우

배열에 등장 횟수, 등장 여부를 담아 놓는 방법을 생각해 보자.