1. Sorting (정렬) 이란? Sorting Algorithms의 종류 Bubble sort (버블 정렬) Insertion sort (삽입 정렬) Quick sort (퀵 정렬) Merge sort (병합 정렬) Topological sort (위상 정렬) Sorting이란 크기 순으로 오름차순 정렬된 리스트로 모든 아이템을 배치하는 것을 말합니다. 위 (a) 리스트에는 숫자가 212인 item이 여러개가 있기 때문에 숫자를 key값으로 sorting하게 되면 그들 간의 순서를 정하기가 모호합니다. 이 경우에, 같은 숫자의 key에 대한 item들이 정렬되지 않은 리스트에서 정렬되어있던 순서가 sorted data에 반영되어 정렬되면 Stable sort(안정 정렬)라 하고, 그렇지 않으면 Uns..

이번 시간에는 쉘 정렬(Shell Sort)에 대해서 배워볼 것입니다. 1. 셸 정렬이란? 셸 정렬은 삽입 정렬의 성질을 이용하고 이를 보완한 삽입 정렬의 일반화 버전이라고 볼 수 있습니다. 삽입 정렬의 설명은 이곳을 참조 삽입 정렬의 특징은 다음과 같은 것이 있었습니다. 입력되는 초기 리스트가 거의 정렬되어 있을 경우에만 효율적으로 사용 가능하다. 한 번에 한 요소의 위치만 결정 되기 때문에 비효율적이다. 이러한 삽입 정렬의 장점은 뽑아 먹고 단점은 보완한 것이 셸 정렬입니다. 그래서 셸 정렬은 기존의 삽입 정렬을 수행하기 전에 전체 데이터를 거의 정렬된 상태로 만들면 기존의 삽입 정렬을 그대로 처음부터 사용하는 것보다 더 좋은 성능을 발휘할 수 있다는 점에서 착안된 것입니다. 우선 셸 정렬은 Memo..

이번 시간에는 위상정렬에 대해서 배워 보도록 하겠습니다. 1. 위상 정렬이란? 어떤 일을 하는 순서를 찾는 알고리즘으로 방향 그래프에 존재하는 각 정점들의 선행 순서를 위배하지 않으면서 모든 정점(vertex)을 나열하는 것을 말합니다. 그래프가 DAG가 아닌 경우 그래프에 대한 위상 정렬은 불가능합니다. 비순환 방향 그래프(DAG: Directed Acyclic Graph)에서 정점을 선형으로 정렬하는 것(순서대로 출력) 즉, 순서가 있는 task에서 순서를 찾아주는 알고리즘으로 보시면 됩니다. 그래프 방문 결과가 순서대로 출력 되어야 하기 때문에 그래프의 시작 지점과 방향이 존재해야 하고, 그래프에 cycle이 있으면 위상 정렬로 sorting(정렬)하는 것이 불가능합니다. 리스트와 같은 경우 그 자..

이번시간에는 퀵 정렬에 대해서 배워 보도록 하겠습니다. 저번 포스팅에서 설명했던 정렬 방식들(버블 정렬, 삽입 정렬, 선택 정렬) 은 가장 기본적인 수준의 정렬 방식들입니다. 그러나 이것들은 일반적으로 좋은 성능은 낼 수 없기때문에 실제로 개발 시에는 잘 사용하지 않습니다. 앞으로 배울 Merge / Quick 정렬은 굉장히 중요하기 때문에 자세히 알아보도록 하겠습니다. 1. 퀵 정렬이란? 먼저 퀵정렬의 특징은 다음과 같습니다. 퀵 정렬(Quick Sort)은 합병 정렬(Merge Sort)과 마찬가지로 배열을 둘 씩 분할하며 정렬하는 과정을 거치기 때문에 시간복잡도 O(nlog2n)을 갖습니다. 하지만 같은 시간 복잡도라도 실제 정렬에서는 합병 정렬보다 퀵 정렬이 훨씬 더 빠른 시간 안에 정렬이 가능합..

이번 시간에는 merge sorting에 대해서 배워보도록 하겠습니다. 저번 포스팅에서 설명했던 정렬 방식들(버블 정렬, 삽입 정렬, 선택 정렬) 은 가장 기본적인 수준의 정렬 방식들입니다. 그러나 이것들은 일반적으로 좋은 성능은 낼 수 없기 때문에 실제로 개발 시에는 잘 사용하지 않습니다. 앞으로 배울 Merge / Quick 정렬은 굉장히 중요하기 때문에 자세히 알아보도록 합시다. 1. Merge Sort(합병 정렬) 이란? merge sort와 다음 시간에 배울 quick sort가 정렬 알고리즘의 핵심이라고 할 수 있습니다. 하지만 중요한 만큼 이전에 배웠던 것들과는 다르게 매우 복잡하게 진행이 됩니다. 하나의 리스트를 두 개의 균등한 크기의 리스트로 분할하고 부분 리스트를 합치면서 정렬하여 최종..

이번 시간에는 삽입 정렬(Insertion Sorting)에 대해 배워 보도록 하겠습니다. 1. 삽입 정렬이란? 삽입 정렬은 특정 데이터를 리스트의 앞에서부터 이미 정렬된 서브 리스트의 값들과 비교하여 자신의 위치에 삽입하는 방식입니다. 이때 서브 리스트는 이미 정렬이 되어있기 때문에 서브 리스트 안에서도 자신이 삽입이 되어야 할 위치가 정해져 있을 것입니다. 그 위치에 데이터를 삽입하는 것이 바로 삽입 정렬입니다. 예를 들어, 손안의 카드를 정렬하는 방법과 유사하다고 생각할 수 있습니다. 새로운 카드를 기존의 정렬된 카드 더미(Deque) 속에서 올바른 자리를 찾아 삽입하고 새로 삽입될 카드의 수만큼 계속 반복해 가면서 전체 카드가 정렬되는 것입니다. 그렇다면 이런 의문을 가질 수 있으실 겁니다. 정렬..

이번 시간에는 정렬의 종류 중 버블 정렬에 대해서 배워보도록 하겠습니다. 1. Bubble Sort란? 그렇다면 첫 번째 정렬 방식인 Bubble Sort(버블 정렬)에 대해서 배워보도록 하겠습니다. 버블 정렬을 간략히 말하자면 다음과 같습니다. 서로 인접한 두 원소를 순회하며 검사하여 정렬하는 알고리즘 다음과 같은 예시를 통해 이해를 해 보도록 합시다. 아래에 정렬되지 않은 리스트가 있습니다. 우선 가장 앞에 위치한 두 개의 값을 비교하게 됩니다. 그래서 만약 정렬되어 있지 않다면, 즉 다시 말해서 왼쪽의 값이 오른쪽의 값보다 크다면 두 숫자를 바꿔주게 됩니다. 위 그림에서는 첫 비교가 5와 4이기 때문에 5와 4를 비교했을 때 왼쪽 값이 더 크기 때문에 두 값의 위치를 바꾸어 줍니다. 그 다음 5와 ..

그 동안 배운 자료구조를 통해 데이터를 다루는 방법에 대해 알아 보도록 하겠습니다. 이번 시간에는 정렬이란 무엇인가에 대해서 먼저 설명하겠습니다. 1. 정렬 알고리즘이란? 가장 기본적으로 자료 구조에 정의된 데이터들을 어떻게 정렬할 수 있는지에 대해서 알아봅시다. 정렬 알고리즘은 다양하게 존재하는데 우선 기본적인 종류는 다음과 같습니다. 1) 간단하지만(simple) 느린(slow) 방식 Bubble Sort Selection Sort Insertion Sort 2) 약간 복잡하지만 빠른 방식 Shell Sort Merge Sort Quick Sort Heap Sort 3) 아주 빠르지만 제한적으로만 사용 가능한 방식 Counting Sort Radix Sort Bucket Sort 4) 기타 필요에 따..