stay the course

바킹독 실전 알고리즘 강의를 듣게 되어서 강의 필기를 할겸 정리용으로 글 씁니다. 문제시 삭제 하겠습니다.   제한된 자료구조 : 스택, 큐, 덱 0x05강 스택스택: FILO(first in last out) ex) 엘리베이터  스택의 성질1. 원소의 추가가 O(1)2. 원소의 제거가  O(1)3. 제일 상단의 원소 확인이 O(1)4. 제일 상단이 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능. -> 만들 수는 있음.  1. 배열을 이용해 구현하는 것이 편함. const int MX= 100005;int dat[MX];int pos=0;  push,pop 함수  값 추가 (push) : pos++값 삭제 (pop) : pos--  2.STL stack ⚠️스택이 비어 있을 때 pop(), top(..

바킹독 실전 알고리즘 강의를 듣게 되어서 강의 필기를 할겸 정리용으로 글 씁니다. 문제시 삭제 하겠습니다. 0x03강 배열=> 배열은 데이터를 자주 바꾸지 않고 쌓아두고 싶을 때 사용함. 1. 연속적인 자료구조 -> k번재째 원소를 확인/변경할때 O(1)만에 가능.2. 추가적으로 소모되는 메모리 양이 거의 없음3. 메모리가 붙어 있어서-> Cache hit rate가 높음.4.메모리 상에 연속한 구간을 잡아야 해서  ->할당에 제약이 걸림.   임의의 위치에 있는 원소를 확인 변경: O(1)원소를 끝에 추가 :O(1)마지막 원소를 삭제 : O(1)임의의 위치에 원소를 추가: O(n)임의의 위치에 원소를 삭제 : O(n)추가/삭제 함수 직접 구현#include using namespace std;void ..