1. Array(배열) - 기본 개념

1. Array(배열)

- 배열은 가장 기본적이면서, 많이 사용되는 자료구조다.

 

a) 배열의 형태

- 배열은 동일한 자료형을 가진 데이터의 연속적인 나열로 이루어져 있다. 

- 배열의 요소는 연속적인 메모리 주소를 할당받는다.

- 배열은 index를 사용하여 해당 요소의 메모리에 직접 접근이 가능하다.  

 

b) 배열은 정렬(Sorting)과 이어진다. 

- 정렬에는 다양한 알고리즘이 있는데, 배열을 효율적으로 사용하기 위함이다. 

- 대부분의 정렬 알고리즘은 O(n log n)의 시간복잡도를 갖는다.

- 정렬 알고리즘은 안정적(stable)인가, 불안정적(unstable)인가로 분류된다. 

 

c) 배열은 탐색(Search)과 이어진다. 

- 배열을 이용한 알고리즘 문제를 풀다보면, 배열의 특정 요소를 찾는 경우가 있다.

- 이처럼, 배열의 특정 요소를 찾는 문제에서 사용하는 알고리즘이 탐색이다. 

- 탐색의 경우, 2가지 케이스로 분류될 수 있다. 

 

▶ 배열이 정렬되지 않은 경우 → 모든 요소를 검색해야 한다. → O(n)의 시간복잡도 

▶ 배열이 정렬되어 있는 경우 → 이진탐색(binary search) 사용 가능 → O(log n)의 시간복잡도 

 

- 더 나아가, 다차원 배열의 검색은 Graph(그래프) 알고리즘을 이용하게 된다. 

- 우선 Sorting부터 하나씩 점령해나가자. 

---

2. Sorting의 종류 

- Bubble Sort (버블 정렬)

- Insertion Sort (삽입 정렬)

- Selection Sort (선택 정렬)

- Merge Sort (병합 정렬)

- Quick Sort (퀵 정렬)

- Heap Sort (힙 정렬)

- Counting Sort (계수 정렬)

- Radix Sort (기수 정렬)

 

a) stable/unstable sorting의 의미