해나의 컴공생존기

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

1. Merge Algorithm sorting된 두개의 배열을 앞에서부터 각각 하나씩 비교하며 한 배열에 순서대로 합치는 알고리즘. 이 알고리즘의 단점은 하나의 배열을 새로 만들어야한다는 것이다 2. Recursive Merge Sort 위 코드를 간단히 설명해보자면 먼저 a[]와 똑같은 b[]를 만든다. h는 배열 전체 길이의 절반이다. b[0]부터 b[h-1] 까지 sort하는 함수를 한번 호출하고 b[h]부터 b[n-h-1]까지 sort하는 함수 하나를 호출한다. 끝까지 한 다음에는 마지막에 a로 sorting되며 합쳐진다. 증명 (proof by Invariant) invariant : 조건1 . a 배열이 입력이라고 가정하고 b배열이 sorting된 후 배열이라고 하면, a와 b의 값이 같아야..