해나의 컴공생존기

1. STL이란? Standard Template Library 의 약자 반복자, 컨테이너, 알고리즘 함수객체 등의 라이브러리로 구성 2. 컨테이너 기본 자료형과 유저가 정의한 자료형을 담는 일종의 자료구조 2.1 시퀀스 컨테이너 일반적인 자료구조와 동일한 형태 (vector / list / string / deque ...) 자료를 입력한 순서대로 저장하기 때문에 저장, 검색, 알고리즘에 불리하다. 적은 양의 자료나 검색 속도가 중요하지 않은 경우에 사용한다. 2. 연관 컨테이너 일정한 규칙에 따라 자료를 조직화하여 저장 (set / map / multiset / multimap ...) 자료를 정렬하여 저장하기 때문에 검색에 유리하다. 많은 양의 자료나 검색 속도가 중요한 경우에 사용한다. 3. 어댑..

앞으로 자주 쓰일 자료구조들을 한번 복습해볼 것이다. 1. Array 동일한 type의 데이터를 연속된 주소에 저장하는 자료구조이다. 갯수를 미리 정해야하고 중간에 용량을 늘리기는 불가하다. 인덱스만 알면 데이터에 접근하기 슂다는 장점을 가지고있다. ex) A[7] = 400 + 7*4 = 428 Search, Delete, Insert 입장에서 효율이 좋지 않다. sorting이 되어있다면 Binary Search O(log N)가능하다. 2. Stack insertO(1) / DeleteO(1)만 제공한다. Search x Last in, First out 수식 계산에 사용 ex (3+7)*2 + (6-3)/5 3. Queue insert O(1) / Delete O(1)만 제공한다. Search x..

Stack Insert/Delete만 제공 Push/Pop이라고 부름 Last in, First out(나중에 들어오는게, 먼저 나가는 것) 성능: Push: O(1), Pop: O(1)(넣는것을 push, 빼는것을 pop) Stack 구현 Stack Pointer는 값이 다음에 들어올 자리를 뜻한다. Stack Code int Stack[N]; int SP; int init() {SP = 0} int isEmpty() {return SP == 0;} int Push() { Stack[SP] = x; SP++; } int Pop() { SP--; return Stack[SP]; }​ # 미로찾기 이런 미로 문제를 해결하는 알고리즘 중에 DFS 와 BFS가 있다. 오늘은 DFS로 미로를 찾는 과정을 알아볼..