[알고리즘] 알고리즘을 시작하기 위한 기초 지식 - 정렬 알고리즘(sorting algorithm) 맛보기

 컴퓨터 공학의 꽃이자 많은 사람들이 어려워하는 CS 과목 중 하나인 '알고리즘'.

대부분의 기업에서도 서류 전형 다음으로 라이브 코팅 테스트를 진행할만큼 중요도도 올라갔으며 사람들의 관심도 또한 높아지고 있다.

 

 아무런 알고리즘, 자료 구조에 대한 배경지식 없이 학부 1학년 때, 백준 온라인 저지를 통하여 알고리즘 문제를 접하게 되면서 자주 벽에 부딪히게 되었는데 시간 복잡도, 공간 복잡도, 빅오 표기법 등에 대한 이해가 많이 부족했던 것 같다.

 

 정렬 알고리즘을 통한 예제들이 앞서 말했던 시간 복잡도, 공간 복잡도, 빅오 표기법에 대한 이해를 돕기 수월하며 동시에 알고리즘 문제에 대한 접근법을 배우기도 좋다고 느껴서 간단하게 정리하는 포스트를 작성하려고 한다.

 

 

정렬 문제(Sotring Problem)

 알고리즘 문제에 입문할 때, 가장 많이 나오는 유형 중 하나는 '주어진 숫자를 크기 순서대로 정렬하세요' 등의 정렬 문제이다. 또한, 많은 다른 유형의 알고리즘 문제들도 데이터의 정렬이 선행되어야 하는 경우가 많다.

 

우리는 간단하게 정렬 문제를 '모든 데이터 처리의 기본이 되는 문제'라고 말할 수 있다.

 

 

정렬 알고리즘(Sotring Algorithms)

 정렬 알고리즘(sorting algorithms)이란 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다.

 위에서 언급한 정렬 문제를 해결하기 위한 수많은 정렬 알고리즘들이 존재한다. 주어진 상황들(한정된 메모리, 제한 시간 등)에 맞추어 알맞은 정렬 알고리즘들을 사용하는 것도 중요하다.

백준 1517번 문항: 버블 소트

 이를테면 백준 1517번 문항인 버블 소트는 가장 basic한 버블 소트를 이용한 풀이로는 풀리지 않는다. 그 이유로는 입력 데이터의 수가 최대 500,000개인 것에 반하여 주어진 시간은 1초밖에 없기 때문이다. 이 문항을 풀기 위해서는 우리에게 주어진 조건들, 그리고 사용하려는 알고리즘의 효율이 그 바운더리 안에 들어가는 지를 파악해야 한다.

 

위키백과 - 정렬 알고리즘 중 비교 정렬의 일부

 Bubble Sort, Quick Sort, Merge Sort 등 수많은 정렬 알고리즘들이 존재하며 위 사진에 있는 정렬 알고리즘들은 모두 비교 정렬 알고리즘이다.

 비교 정렬(Comparsion-based sorting)은 정렬 알고리즘의 일종으로 두 개의 값을 비교(comparsion)하는 것에 기반(based)하여 정렬하는 것을 말한다. 비교 정렬이 올바르게 작동하기 위해서는 아래 2가지 원리가 필요하며 만족되어야 한다.

 

1. a <= b이고 b <= c이면 a <= c이다. (타동성)
2. a와 b 모두 a <= b 또는 b <= a이다. (완전성 또는 3분법)

앞서 원리라고 거창하게 표현했지만, 간단히 말하여 정렬하고자 하는 대상이 서로 비교가 가능해야 한다는 것이다.

 

정렬 알고리즘의 특징 1 : Stable과 Not Stable

 입력값으로 동일한 값이 2개 이상이 들어오는 경우도  존재하는데, 이때 입력된 순서가 정렬 이후에도 유지된다면 해당 정렬은 Stable(안정적)이라고 말하며, 순서가 달라질 수 있다면 불안정(Not Stable)하다고 말한다.

 

 stable 유무는 정렬 알고리즘에서 굉장히 큰 특징이므로 앞으로 알게 될 정렬 알고리즘들이 stable, not stable 중 어느 유형에 해당하는 지 살펴보는 것도 중요하다.

 

정렬 알고리즘의 특징 2 : In-place와 Not In-place

 정렬 알고리즘의 또 다른 주요 특징으로는 In-place(제자리)알고리즘과 Not In-place(비제자리) 알고리즘이다.

In-place(제자리) 알고리즘이란 입력 데이터를 저장하는 메모리 이외는 상수 크기의 메모리만 필요한 알고리즘을 의미한다.

 위 정의에서 상수 크기의 메모리가 필요하다고 말하였는데 상수는 무엇을 의미하는 것일까? 정의에서 말한 상수는 입력 데이터의 크기인 n과 무관한 수를 의미한다. 주로 알고리즘 중간 계산에 필요한 변수 등을 할당하기 위하여 필요한 메모리인 경우가 많다.

 

ex) 두 원소를 swap하는 과정에서 필요한 임시 변수 tmp를 할당하기 위한 메모리 등.

 위와 같은 알고리즘 표에서는 1로 표기된 것이 정의에서 말한 상수만큼의 메모리를 의미한다. 위는 정확이 1만큼의 추가 메모리가 필요한 것이 아닌 단순히 n과 관계 없는 상수를 모두 1로 지칭하고 있는 것이다.

 

 반대로 Not In-place 알고리즘은 Quick Sort와 같이 알고리즘 수행 과정에서 n에 비례한 만큼의 추가 메모리(이 경우에는 log n)가 필요한 알고리즘을 의미한다.

 

 

토끼와 거북이 데이터

 듣기에는 조금 생소한 개념일 수 있으나 Bubble Sort를 개선하는 과정에서 파생된 Comb Sort와 Insertion Sort를 개선하는 과정에서 파생된 Shell Sort가 어떠한 문제점을 해결하고자 하였는지 이해를 돕기 위하여 추가하여 작성하려고 한다.

 

Bubble Sort에서 더 자세히 다루도록 하고, Bubble Sort를 기준으로 토끼 데이터와 거북이 데이터는 아래와 같다.

 

토끼 데이터(rabbit data)는 왼쪽에 있는 큰 데이터들, 몇 번의 pass를 통하여 오른쪽 제 위치로 이동하는 데이터를 의미한다.

거북이 데이터(turtle data)는 오른쪽에 있는 작은 데이터들, pass 과정에서 느리게 왼쪽 제 위치로 이동하는 데이터를 의미한다.

 

 Bubble Sort는 왼쪽에서부터 오른쪽으로 인접한 모든 원소에 대하여 크기 비교를 하여 작은 원소는 왼쪽, 큰 원소는 오른쪽으로 swap하는 과정을 여러 번 거친다. 이를 한 번의 pass라고 하며 토끼 데이터는 1번의 pass에도 여러 번 swap 되기 때문에 금방 제 자리를 찾을 수 있다.

 하지만 반대로 이러한 특징 때문에 거북이 데이터는 1번의 pass에 거의 1칸씩만 이동할 정도로 느리게 본인의 자리를 찾아간다.

 

 

---

 

 오늘은 정렬 알고리즘 공부에 앞서서 필요한 주요 개념들을 몇 가지 선정하여 포스팅하였다. 간단히 요약하자면 아래와 같다.

 

Summary

- 정렬 문제: 모든 데이터 처리의 기본이 되는 문제

- 정렬 알고리즘: 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘

- 비교 정렬 알고리즘: 두 개의 값을 비교(comparsion)하는 것에 기반(based)한 정렬 알고리즘

- 정렬 알고리즘의 특징  

    - Stable 와 Not Stable

    - In-place 와 Not In-place

- 토끼 데이터와 거북이 데이터

 

 

다음으로는 각 정렬 알고리즘을 하나하나 다뤄보는 포스팅을 할 것이다.