DS, Algorithms (2) 썸네일형 리스트형 k-way Merge Sort(합병 정렬)의 시간복잡도 계산하기 이번 포스트에서는 분할 정복 알고리즘(Divide and Conquer Algorithm)중 하나인 합병 정렬(Merge Sort)의 개념과 시간 복잡도 계산 과정 등에 대해 정리하고자 한다. 여기서 분할 정복이란 입력 사례를 두 개 이상의 작은 입력사례로 바로 답을 구할 수 있을 만큼 충분히 작아질 때 까지 분할하고, 작은 입력사례에 대해 각각 답을 구한 후(정복 한 후), 각각을 결합하여 문제를 해결하는 방법이다. 1. 2-way 합병 정렬(2-way Merge Sort) 앞에서 설명한 것과 같이 분할 정복 알고리즘은 분할(Divide), 정복(Conquer), 결합(Combine) 크게 세가지 과정으로 이루어 진다, 가장 일반적인 합병 정렬 방식은 분할 단계에서 입력 사례를 두 개의 작은 입력 사례.. 두개의 스택(Stack)으로 큐(Queue) 구현하기 이번 포스트에서는 어떠한 별도의 변수를 사용하지 않고 오로지 스택(Stack) 2개로 큐(Queue)의 기능을 구현하는 방법을 정리하고자 한다. 먼저, 두 개의 Data Structure에 대한 간단한 설명부터 하겠다. 1. 스택(Stack), 큐(Queue) 스택(Stack)은 top이라 불리는 한쪽 끝에서만 자료를 넣거나 뺄 수 있는 Data Structure이다. 자료를 넣는 것을 push, 꺼내는 것을 pop이라 하며 가장 마지막에 넣은 자료가 먼저 나오는 Last-In-First-Out(LIFO) 구조이다. 큐는(Queue)는 rear라 불리는 한 쪽 끝에서만 자료를 넣고 front라 불리는 반대쪽 한쪽 끝에서만 자료를 뺄 수 있는 Data Structure이다. 자료를 넣는 것을 자료를 넣는 .. 이전 1 다음
