공간복잡도

카운팅 정렬 (Counting Sort)

1. 개념 👑 '계수 정렬'이라고도 불리는 '카운팅 정렬(Counting Sort)'은 각 원소들이 몇 개씩 있는지 나타내는 count배열을 활용하는 정렬 알고리즘이다. 각 원소의 값이 count 배열의 인덱스가 되므로 '정수나 정수로 표현할 수 있는 자료'에 대해서만 적용 가능하다. 2. 동작방식 🎓 동작 방식은 다음과 같다. 원소의 최댓값을 포함할 수 있는 배열 설정 각각의 원소가 몇 번 등장하는지 카운팅 count 배열의 인덱스 = 원소 값 count 배열의 값 = 등장 횟수 count 배열을 누적합으로 만들어주기 정렬되지 않은 배열(초기값)의 뒤에서부터 돌면서, 원소의 값과 동일한 인덱스가 가리키는 곳에 원소 배치해 주기 '0 2 1 1 4 4 4 3 5'가 주어졌을 때 동작방식을 아래의 그림을 ..

병합 정렬(Merge Sort)

합병정렬이라고도 불리는 병합정렬에 대해서 알아보자. 1. 정의 🎃 병합정렬이란 정렬해야 하는 배열을 가장 작을 때까지 나누고, 그 시점부터 인접한 부분배열끼리 비교하며 정렬하는 알고리즘이다. 해당 알고리즘은 분할 정복(Divide and Conquer) 알고리즘을 기반으로 한다. (분할 정복(Divide and Conquer)이란 문제를 분할하고, 분할한 문제를 정복하여 합치는 것이다.) 2. 동작 방식 🎪 주어진 배열을 절반으로 분할하여 부분배열로 나눈다. - 분할(Divide) 해당 부분배열의 길이가 1이 될 때까지 계속해서 1번 과정을 반복한다. 인접한 부분 배열끼리 합친다. - 정복(Conquer) 위의 그림을 통해 알 수 있듯이 크기가 1이 될 때까지 분할이 진행된다. 그리고 인접한 배열끼리 합..

삽입 정렬(Insertion Sort)

1. 정의 🧵 삽입 정렬은 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다. 카드 예시를 살펴보면 쉽게 이해할 수 있을 것이다. '4, 2, 3, 1, 5'라는 숫자 적힌 5장의 카드가 순서대로 있다고 하자. 앞에서부터 순서대로 카드를 뽑으면서 손에 쥔다고 생각하자. 뽑힌 카드는 이미 손에 쥐어진 카드들 사이에 위치를 찾아들어간다. 이미 손에 쥐어져 있는 카드들 뽑은 카드 자신의 위치를 찾아들어간 모습 4 4 4 2 2 4 2 4 3 2 3 4 2 3 4 1 1 2 3 4 1 2 3 4 5 1 2 3 4 5 1번 숫자가 적힌 카드가 자신의 위치를 찾아가는 것을 다시 한번 살펴보자. 1번 카드는 4번과 비교하고, 3번과 비교하고, 2번과 ..

선택 정렬(Selection Sort)

선택 정렬은 여러 가지 면에서 앞에서 살펴본 버블 정렬과 상당히 비슷하다. 두 가지 정렬 방법을 구분하는 게 어렵지는 않으니, 선택 정렬을 공부하는 김에 버블 정렬도 같이 공부하는 것을 추천한다. 1. 정의 🎿 선택 정렬은 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘이다. 2. 동작 방식 🧦 N개의 원소가 있다고 하자. 우선, 배열에서 최솟값을 찾는다. 그리고 첫 번째 원소와 배열에서 찾은 최솟값의 원소를 바꿔준다. 이것이 1회전 수행한 것이다. 이렇게 되면 배열의 첫 번째에 위치한 원소가 가장 작은 값을 가지게 된다. 2회전을 수행할 때는 첫 번째 원소를 제외한 나머지 배열들 중에서 최솟값을 찾는다. 그리고 해당 원소와 배열의 두 번째 원소를 바꿔준다. 이와 같은 방식으..

버블 정렬(Bubble Sort)

거품 정렬이라고도 불리는 버블 정렬에 대해서 알아보자. 1. 정의 👟 버블 정렬은 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘이다. 2. 동작 방식 👞 N개의 원소가 있다고 하자. 첫 번째 원소와 두 번째 원소를 비교하여 만약 첫 번째 원소가 더 크다면 둘의 자리를 바꿔준다. 그리고 두 번째 원소와 세 번째 원소를 비교하여 만약 두 번째 원소가 더 크다면 둘의 자리를 바꿔준다. 이러한 동작을 (마지막 - 1) 번째의 원소와 마지막 원소를 비교할 때까지 수행한다. 이것이 1회전 수행한 것이다. 이렇게 되면 마지막에 위치한 원소가 가장 큰 원소가 된다. 2회전을 수행할 때 마지막 원소를 제외한 나머지들을 정렬해 준다. (N - 1) 회전까지 수행하면 정렬이 마무리된다. 위의 방식은 오름차순으로 정렬을 ..