CH04 : Sorting 2 - Merge Sort

Merge sort는 sorting(정렬) 문제의 optimal 알고리즘으로, $O \left(n \log n\right)$ time을 필요로 한다.Merge에 대하여 - 정렬된 sequences의 mergeMerge 문제 오름차순으로 정렬된 sequence A, B에 대하여, A, B를 합하여 하나의 정렬된 sequence C를 만들어라. 전략 A의 첫 원소와 B의 첫 원소 중 최솟값으로 C의 첫 원소를 구한다. 이가 A의 원소였다고 가정하자. 그럼 문제는 A의 나머지 원소와 B의 원소를 merge하는 것으로 재정의된다.  만약 A 혹은 B가 empty하다면, 남은 배열의 원소들을 C의 뒷부분에 붙인다. Algorithm & Analysis Algorithmmerge(A, B, C)//A or B가 e..

정렬 문제에서의 Optimal SolutionUnsorted data에서 key를 비교해 탐색하는 경우, optimal solution은 $\theta \left( n \right) $를 필요로 한다. Sorted data에서 key를 비교해 탐색하는 경우, optimal solution은 $\theta \left( \log n \right) $를 필요로 한다. 즉, input의 형태에 따라 문제의 복잡도는 변화한다.Insertion Sort (삽입정렬)Strategy n개의 원소를 가진 배열에 대하여 index 1부터 n-1의 원소까지가 삽입되듯이 동작한다. 삽입된 해당 원소가 swap을 이용해 적절한 위치로 이동한다. Example회색 영역은 정렬된 원소들, 검은색 영역은 현재 삽입되어 정렬될 원소,..

Abstract Data Type (ADT)ADT란 추상자료형으로, C++의 class와 비슷한 개념이다. ADT 동작과 그 설명을 기반으로 알고리즘을 설계하고, 정확성을 증명한다.ADT를 정의하기 위해선 다음의 것들을 명시해야 한다.자료구조가 저장할 데이터 명시ex. queue면 front, near 등지원하는 함수 명시ex. insert, delete 등동작 설명what은 설명하고, how는 설명하지 않는다. 즉 무엇을 수행하는지는 설명하지만, 어떻게 수행되는지는 설명하지 않는다.error 처리 명시TreeTree 용어root [루트] : 트리의 최상위 노드. 부모가 없는 노드라고도 한다.node의 degree [차수] : 자식의 수. 비어있지 않은 subtree의 수라고도 한다.external no..

문제 정의1. input : 오름차순으로 정렬된 n개의 원소를 가진 배열 E, 값 K2. output : E에 K가 존재할 경우 K의 index, 그 외의 경우 -1해결책 AStrategy A모든 원소를 순차적으로 확인한다.Algorithm Aint seqSearch(int[] E, int n, int K)int ans, idx;ans = -1; //Assume Failurefor (idx = 0; idx Analysis AWorst Case$W(n) = n$ 발생조건 : 배열의 마지막 원소만 K이거나, K가 배열에 없는 경우Average Case$A(n) = q\cdot \frac {n+1}{2} + (1-q)n$ $A(n) = Pr(succ)A_{succ}(n) + Pr(fail)A_{fail}(n)..

필자는 대학교 1~2학년 동안 총 네 번의 스터디를 스터디장으로서 진행했으며, 현재 24-1에 열 스터디 준비 및 여러 스터디의 컨설팅을 하고 있다. 이 글에선 네 번의 스터디를 진행하면서 실패했던 점과 그 이유 위주로 적어보려 한다.사실 스터디에 정답은 없다고 생각하며, 스터디의 성공은 스터디원의 영향을 많이 받는다. 따라서 정답 보단 오답을 피해가기 위해 이 글을 적는다.22-1 일반수학1 스터디 (인하동동)👤인원 5명 / 🖥️ 온라인(1주에 1번, 약 30분) / 📆1학기(3~6월) / ☑️ 일반수학1 (교양 과목) 공부대학교에 들어와 처음 열었던 스터디로, 진행 방식은 다음과 같았다.1. 교양 수업에서 한 주 동안 배웠던 내용을 자유롭게 복습한다.2. 다섯 명이서 한 주씩 돌아가면서 주간 학..

1. Pandas란 무엇인가? Pandas란 무엇인가? 판다스는 빠르고 쉽게 데이터를 cleaning(청소)하고, 분석할 수 있게 돕는 데이터 구조와 도구들을 가지고 있다. NumPy, SciPy와 같은 수치 계산 도구들이나, statsmodels, scikit-learn 같은 분석적 라이브러리, matplotlib과 같은 데이터 시각화 라이브러리 등과 함께 쓰인다. NumPy와 마찬가지로, 배열 기반이며 for loop 사용 없이 데이터를 가공할 수 있다. 한편 NumPy와는 달리 표 형식의 데이터, 이종의 데이터를 다룰 수 있게 설계되어 있다. (NumPy는 동종의 데이터만 다룰 수 있다.) Pandas의 데이터 구조 크게 두 가지가 있다. : Series, DataFrame 2. Series Ser..