[바킹독의 실전 알고리즘] 0x03강 ~ 0x04강

https://www.youtube.com/playlist?list=PLtqbFd2VIQv4O6D6l9HcD732hdrnYb6CY 

바킹독의 실전 알고리즘 강의

---

1. 배열

1) 성질

• O(1)에 k번째 원소 확인, 변경 가능
• 추가적으로 소모되는 메모리의 양이 거의 없음 
• 데이터들이 붙어있으므로 캐시지역성(cache hit rate)이 좋음
• 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림
• 임의의 위치에 원소에 삽입/삭제하기 위해서는 O(N) 시간이 걸림

insert, erase 함수 구현하기

#include <iostream>
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 = len + 1;
}

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

}

int main(void) {
	int arr[10] = { 10, 20, 30 };
	int len = 3;
	insert(3, 40, arr, len); // 10 20 30 40
    	erase(3, arr, len); // 10 20 30
}

 

2) 배열 초기화 방식

ⓐ memset : 비추천 (실수할 가능성이 큼)

ⓑ for문 

ⓒ fill : algorithm 헤더 이용

int a[21];
fill(a, a+21, 0);

 

2. 벡터

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

for(int e: v1) cout << e << " ";

for(int i=0;i<v1.size();i++) cout << e << " ";

for(int i=0;i<=v1.size()-1;i++) cout << e << " " ;
// 위 방식은 v1의 크기가 0일 때 문제가 됨. 
// 벡터의 size는 unsigned int 형식을 반환하기 때문에 0-1이 4294... 숫자가 됨

 

 

3. 연결 리스트

1) 성질

- k번째 원소를 확인/변경 하기 위해 O(k)가 필요함

- 임의의 위치에 원소를 추가/임의 위치에 원소 제거는 O(1)

- 원소들이 메모리상에 연속되어 있지 않아 캐시지역성이 낮지만 할당이 쉬움

 

2) 종류

- 단일 연결 리스트 : 다음 원소의 주소 들고있음

- 이중 연결 리스트 : 각 원소가 이전 원소, 다음 원소 주소 둘 다 들고 있음

- 원형 연결 리스트 : 맨 마지막 원소가 처음 원소로 연결

 

* 연결리스트는 추가적으로 필요한공간(overhead)가 O(n)만큼 비례하는 메모리를 필요로 함

 

+ insert, erase함수 구현하기

void insert(int addr, int num) {
    pre[unused] = addr;
    dat[unused] = num;
    nxt[unused] = nxt[addr];

    if(nxt[addr] != -1 ) pre[nxt[addr]] = unused;
    nxt[addr] = unused;   
    unused++;
}

void erase(int addr) {
    nxt[pre[addr]] = nxt[addr];
    if (nxt[addr] != -1)  pre[nxt[addr]] = pre[addr];   
}