Krafton_jungle 5기 5일차 TIL - 자료구조, 정렬

비선형 자료구조

 

1. 트리

트리란?	트리란 뱡향성이 있는 비순환 그래프이다. 뒤집었을 때 뻗어나가는 나무의 형상을 해서 트리라고 한다.
트리의 구성 요소	가장 상위의 노드는 root 라고 하고, 가장 바깥 노드는 leaf, 그 외 노드는 branch 라고 한다. 사실상 명칭의 차이만 있을 뿐 모든 노드의 구성 요소는 일치한다.
트리의 특징	계층적 속성을 갖는 자료를 선형 구조로 표현하기 어렵다는 한계를 극복하기 위해 고안되었다. 모든 노드들은 하나의 루트 노트에서 시작한다. 뱡향성은 부모에서 자식으로만 연결, 같은 계층에 노드끼리는 연결하지 않는다. 임의의 노드에서 출발하여 자기 자신으로 되돌아올 수 없다. 간선의 갯수는 노드의 갯수 -1 이다.
이진트리란?	트리와 거의 동일한 구조로 이루어져 있으며, 크게 다른 부분으로는 하나의 부모노드에 최대 2개의 자식 노드를 가진다.
이진트리의 종류	이진 트리는 종류도 다양한데, 첫번째로 모든 노드가 2개의 자식노드를 가지고 있거나 자식이 없는 경우에는 정 이진트리, 이보다 더 엄격하게 모든 2진트리가 2개의 자식을 가지고 leaf 노드가 모두 같은 레벨일때는 포화 이진트리라고 한다. 마지막으로 최대, 최소 힙, 우선순위 큐를 구성할때 사용되는 완전 이진트리가 있다.
완전 이진트리	마지막 레벨을 제외하고 모든 노드가 채워져 있어야 한다. 마지막 레벨의 노드는 다 채워져 있을수도 있고 아닐수도 있음 노드는 왼쪽에서 오른 방향으로 채워져야 한다. (그래야 1차원 배열로 표현이 가능)

 

 

2.그래프

그래프란?	그래프란 정점(node)과 간선(edge)으로 이루어진 자료구조이다. 트리와 다르게 부모, 자식 노드의 개념이 없으며, 노드마다 간선이 있을수도, 없을수도 있다.
어디에 쓰일까	그래프는 주로 탐색에 사용되는 자료구조로, DFS, BFS나 지하철 노선도, 네비게이션 등에 사용된다.
그래프의 종류	종류로는 무방향 그래프, 간선이 가르키는 방향으로만 이동할 수 있는 방향 그래프, 간선을 이용할 때 비용이 드는 가중치 그래프, 모든 정점이 간선으로 연결된 그래프인 완전 그래프가 있다.

 

 

3. 힙

힙 이란?	힙이란 기본적으로 완전 이진트리로 구성되어 있으며, 자식 노드가 부모 노드보다 값이 작아야 한다는 제약이 걸려있는 최대힙과, 그 반대의 개념인 최소 힙이 있다.
어디에 쓰일까	정렬 알고리즘인 힙 정렬에 사용되며 시간 복잡도는 O(n log n)으로 준수한 성능을 보장한다. 시뮬레이션 시스템, 네이퉈크 트래픽 제어, 운영체제에서의 작업 스케쥴링, 수치 해석적인 계산에 사용된다.

 

배열

 

1. 삽입정렬

정렬 방식	삽입 정렬은 배열을 순회하며 현재 내가 선택한 값이 앞의 값보다 클때까지 탐색하며, 선택한 값보다 작은 값이 나오면 뒤의 배열을 한칸씩 뒤로 밀고 그 자리에 내가 선택한 값을 삽입한다.
시간 복잡도	최악의 경우엔 O(n^2)이다. 하지만 모두 정렬되어 있다면 한번씩밖에 비교를 안하기 때문에 O(n)의 시간 복잡도를 제공한다.
장점	구현이 간단하고, 이미 정렬되어 있는 배열에 매우 효율적이다. 추가 메모리를 사용하지 않는다. 안정 정렬이다. (중복된 요소가 입력될 경우 기존의 정렬 형태를 유지)
단점	평균과 최악의 시간복잡도가 O(n^2)로 비효율적인 편 배열의 길이가 길어질수록 비효율적

 

 

2. 버블정렬

정렬 방식	마치 가벼운 비눗방울이 떠오르듯 배열을 순회하며 현제 내가 가르키고 있는 값이 다음 값보다 클 경우 서로 위치를 바꿔주는 방법을 사용한다. 배열의 뒷쪽부터 정렬하는 방식
시간 복잡도	정렬이 되어있던 안되어있던 동일하게 O(n^2)
장점	구현이 아주 간단하다. 추가 메모리를 사용하지 않음. 안정정렬.
단점	인접한 요소를 모두 반복하기 때문에 시간 복잡도가 O(n^2) 이다 자료의 교환 작업이 자료의 이동 작업보다 더 복잡하기 때문에 버블 정렬은 단순하지만 거의 쓰이지 않는다.

 

 

3. 선택정렬

정렬 방식	배열을 전부 순회하고 가장 작은 수를 맨 앞으로 보내는 형식으로 정렬한다.
시간복잡도	O(n^2)
장점	버블정렬에 비해 교환하는 횟수가 적어 그나마 효율적임 추가 메모리 공간을 필요로 하지 않는다. 구현이 간단함
단점	시간복잡도가 O(n^2)로 비효율적 불안정 정렬임.

 

 

4. 합병정렬

정렬 방식	본격적으로 재귀를 사용하는 정렬법으로, 배열을 최소단위로 분할한 뒤 다시 병합하며 정렬한다.
시간복잡도	O(n log n)
장점	안정 정렬. O(n log n)의 시간 복잡도를 보장한다.
단점	임시 배열을 선언해야 함으로 추가 공간이 필요하다. (제자리 정렬이 아님) 데이터의 크기가 큰 경우 시간적으로 낭비가 발생한다.

 

파이썬 병합정렬 코드

 

 

5. 힙정렬

 

 

정렬 방식	기본적으로 힙 자료구조를 사용해 최대, 최소 힙 트리를 작성한다. 그렇게 트리가 작성되면 최상위 노드를 제거하며 정렬을 반복정렬하는 법
시간복잡도	O(n log n)
장점	안정 정렬 시간 복잡도가 빠른편이다
단점	비교연산이 많이 필요하며, O(n)의 추가 공간이 필요하다 원본 배열을 파괴하므로, 정렬되지 않은 배열의 복사본이 필요하다.

힙정렬 코드

 

 

6. 퀵정렬

 

정렬 방법	퀵 정렬은 하나의 기준점(pivot)을 정하고 기준점보다 작은 수는 왼쪽으로, 큰 수는 오른쪽으로 정렬한 뒤 피벗을 제외한 분할된 다른 영역들을 같은 방법으로 정렬한다.
시간 복잡도	O(n log n), 최악의 경우 O(n^2)
장점	난수로 구성된 배열을 정렬할 때 다른 알고리즘 대비 가장 빠른 속도를 제공한다.
단점	불안정 정렬 정렬된 배열에 대해 퀵 정렬을 수행하는 경우 O(n^2)의 시간 복잡도를 제공한다. (이러한 문제점에도 불구하고 퀵 정렬을 차용하는 이유는 완전히 정렬된 배열에 대해 퀵 정렬을 수행할 가능성이 매우 적기 때문이다.)

퀵 정렬 코드