[바킹독 실전 알고리즘] 강의 노트 _ 0x03강 배열~0x04강 연결 리스트

바킹독 실전 알고리즘 강의를 듣게 되어서 강의 필기를 할겸 정리용으로 글 씁니다. 문제시 삭제 하겠습니다.

 

0x03강 배열

=> 배열은 데이터를 자주 바꾸지 않고 쌓아두고 싶을 때 사용함.

 

1. 연속적인 자료구조 -> k번재째 원소를 확인/변경할때 O(1)만에 가능.

2. 추가적으로 소모되는 메모리 양이 거의 없음

3. 메모리가 붙어 있어서-> Cache hit rate가 높음.

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

 

 

• 임의의 위치에 있는 원소를 확인 변경: O(1)
• 원소를 끝에 추가 :O(1)
• 마지막 원소를 삭제 : O(1)

• 임의의 위치에 원소를 추가: O(n)
• 임의의 위치에 원소를 삭제 : O(n)

추가/삭제 함수 직접 구현

#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 = len; i > idx; 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();
}

😀그림을 그려보면서 구현하는게 좋다.

 

 

vector

그래프 인접 리스트 문제에서는 vector사용하는 것이 편함.

그전까지는 쓸일 거의 없음. 

 

• for(int e: v) :e는 복사본이기 때문에 변경해도 원본에 영향이 없음.
• for(int &e: v): e가 원본을 참조 했기 때문에 변경하면 원본이 같이 변함. 

---

0x04강 연결 리스트

: 텍스트 에디터에 사용됨.

 

 

1. n번째 원소를 확인/변경하기 위해 O(n)의 시간이 사용됨.

2. 임의의 원소를 추가,저거 할때 O(1)의 시간이 사용됨.

3. 원소들이 메모리 상에 연속해있지 않아 Cache hit rate가 낮지만 할당이 쉬움.

 

• 단일 연결리스트: 자신의 다음원소의 들고 있음.
• 이중 연결리스트 : 자신의 이전과 다음 원소 둘다의 주소를 들고 있음.
• 원형 연결리스트: 자신의 이전과 다음 원소 둘다를 들고 있어도 상관 없음.

배열 vs 리스트 

 

야매 연결 리스트 _ 코테에서 STL을 허용하지 않는 경우.

 

=> 원소를 배열로 관리하고  pre,nxt 대신 배열의 index로 관리함.

const int Mx =1000005;
int dat[MX],pre[MX],nxt[MX];
int unused=1;

file(pre, pre+MX, -1);
file(nxt, pre+MX, -1);

-> 실무에서는 메모리 누수때문에 사용 안함. 

 

 

 

 

더미 노드를 두는 이유는  원소가 아예 없는 경우에 예외처리가  편하기 때문이다. 

 

모든 원소의 값을 출력하는 함수 구현 

void traverse(){

	int cur =nxt[0];
    while(cur!=-1){
    	cout<<dat[cur]<<' ';
        cur=nxt[cur];
   	 }
   	cout<<"\n\n";
   }

 

 

야매 연결 리스트 추가/ 삭제 함수 직접 구현. 

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

const int MX = 1000005;
int dat[MX], pre[MX], nxt[MX];
int unused = 1;

void insert(int addr, int num){
  dat[unused] = num;
  pre[unused] = addr;
  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];
}

void traverse(){
  int cur = nxt[0];
  while(cur != -1){
    cout << dat[cur] << ' ';
    cur = nxt[cur];
  }
  cout << "\n\n";
}

void insert_test(){
  cout << "****** insert_test *****\n";
  insert(0, 10); // 10(address=1)
  traverse();
  insert(0, 30); // 30(address=2) 10
  traverse();
  insert(2, 40); // 30 40(address=3) 10
  traverse();
  insert(1, 20); // 30 40 10 20(address=4)
  traverse();
  insert(4, 70); // 30 40 10 20 70(address=5)
  traverse();
}

void erase_test(){
  cout << "****** erase_test *****\n";
  erase(1); // 30 40 20 70
  traverse();
  erase(2); // 40 20 70
  traverse();
  erase(4); // 40 70
  traverse();
  erase(5); // 40
  traverse();
}

int main(void) {
  fill(pre, pre+MX, -1);
  fill(nxt, nxt+MX, -1);
  insert_test();
  erase_test();
}