[ComputerScience] 알고리즘의 시간복잡도와 탐색, 정렬 (Binary Search, 깊이우선탐색, 넓이우선탐색, Selection Sort, QuickSort, Merge Sort)

이 게시글은

서울대학교 데이터사이언스대학원

조요한 교수님의

데이터사이언스 응용을 위한 컴퓨팅 강의를

학습을 위해 재구성하였습니다.

---

Time Complexity

 

알고리즘의 성능을 측정할 때는 흔히

time complexity(시간 복잡도)와 space complexity(공간 복잡도)로

측정을 많이 한다

 

이 중에서 이번에 알아볼 것은 시간복잡도

보통 흔히 우리들이 아는 알고리즘의 성능을 평가할 때 자주 사용된다

 

단순하게 어떤 알고리즘의 시간 복잡도를 측정하려면

어떤 방법이 있을까?

 

첫 번째는 실제로 알고리즘을 돌려서

시작 시점과 종료된 시점의 시각을 구해

그 차이를 구하는 방법이다

 

이러한 방법의 차이는 real-world performance를 측정할 수 있다

즉, 실제로 알고리즘이 사용될 때 어느정도의 시간이 걸리는지를

측정할 수 있다는 뜻이다

 

하지만 이러한 측정방식의 단점은

단순 알고리즘 자체보다, 컴퓨터의 컴파일러, 하드웨어 등

다른 프로세스들의 영향을 받기 때문에 정확한

알고리즘의 시간 측정이 어렵다

또한 데이터의 Input 사이즈가 커지면

알고리즘을 돌리는 것 자체가 오래걸리기 때문에

시간 측정이 어려워진다

 

두 번째 방법은 input size에 따라서 operation을

얼마나 수행하는지를 측정하는 방법이다

이 방법은 알고리즘의 실제 작동 시간을 정확하게

측정한다기보다는 데이터의 input size에 따라

abstract하게 시간을 측정하는 방법이다

 

이러한 방법의 장점은

하드웨어 independent하며

정말 알고리즘의 순수한 시간을 알 수 있고

input size에 따라 알고리즘이 얼마나 느려지는지 예측 가능하다

 

하지만 단점은

위에서 말했듯이 정확한 시간 측정이 아닌

계산에 따른 추정 시간이며

알고리즘이 복잡해지면 operation의 개수를 세기가 힘들어진다

 

이러한 단점으로 인해 이러한 방식은

주로 worst case를 측정할 때 사용한다

가장 최악의 경우에 시간이 어느 정도

걸리는지를 측정하는 것이다

 

이렇게 worst scenario를 측정해서 표현하는 것이

우리가 흔히 알고리즘공부를 하면 볼 수 있는

빅오(BigO) 표기법이다

 

 

Asymptotic Analysis

 

알고리즘을 여러 개의 클래스로 나누어서

알고리즘이 돌아가는 시간이 어떻게 변하느냐에 따라서 나누는 방식이다

 

위 ppt에 있는 예시와 같이

O(1), O(logN) 등등

이렇게 알고리즘이 작동하는 시간에 따라

나누는 방식을 이야기한다

 

위와 같이 2개의 알고리즘을 비교를 했을 때

input N의 사이즈가 커질 때

수행 시간이 얼마나 빠르게 증가하는지를 비교한 것이다

 

이러한 방식의

수행시간 분류법(?)을

Asymptotic Analysis라고 한다

 

 

Recursion

정렬, 탐색 알고리즘에 대해 제대로 이해하기 위해서

반드시 알아야하는 개념이

시간복잡도와 Recursion이다

 

시간복잡도는 위에서 정리했으니

recursion에 대해 정리해보겠다

 

main 문제를 풀기 위해서 sub 문제를 푸는데

이 sub문제와 Main 문제가 동일한 것

 

recursion은 영어 단어 그대로

재귀라는 뜻이다

한 마디로 같은 알고리즘을

계속해서 끝까지 반복하는 방식이다

 

정렬이나 탐색 알고리즘이 결국

동일한 방식을

원하는 결과가 나올 때까지

반복하고 반복하는 방식이 대부분이라

재귀의 개념을 이해하고있으면 좋다

 

 

Binary Search

시간복잡도와 재귀의 개념에 대해 배웠으니

탐색 알고리즘에 대해 배워보기로 한다

 

첫 번째는 가장

단순+유명+자주 쓰이는 이진탐색

 

 

recursion의 가장 대표적인 예시로

이미 순차적으로 정렬이 되어있는 데이터를

반으로 줄여가며 탐색하는 방법이다

 

가장 간단한 예시를 들면 1부터 1000까지 중

8이라는 숫자를 찾으려고 한다면

1000의 절반인 500에서

8이 500보다 작으니 1~500 사이의 범위를 탐색한다

또다시 1~500의 중간인 250에서 8은 250보다 작으니

1~250의 범위를 탐색한다

 

이러한 방식으로 계속해서

반을 쪼개 recursive하게 탐색하면

8이라는 숫자를 찾을 수 있다

 

이러한 이진탐색의 시간복잡도는

O(logN)인데

반으로 나눠서 탐색하니 당연한 이야기이다

 

1부터 1000까지의 숫자 중

8을 탐색하려고 하면

2의 10제곱은 1024니까

아무리 많이 해도 10번의 재귀 이내에는

8이라는 숫자를 찾을 수 있다

 

이진 탐색 트리에서의 이진탐색을

파이썬으로 구현한 코드이다

 

recursive한 알고리즘을 구현할 경우

예외처리의 개념(?)과 비슷한 Base Case와

계속해서 반복해서 시켜줄 recursive를 제대로

정의해서 구현해주는 것이 중요하다

 

이진 탐색 트리에서 base case는

자식 노드가 null인 경우(leaf 노드)와

찾고자하는 값이 현재 노드값인 경우이다

이런 경우들에서는 다음 과정으로 진행되면 안되므로

base case로 따로 처리해준다

 

그리고 찾고자하는 값이 현재 노드의 값이 아닌 경우

다시 재탐색할 수 있도록 recursive 코드를

구현해주면 된다

 

Selection Sort

선택정렬은 단어 그대로

특정 데이터를 선택해서 바꾸는 방식으로

정렬하는 정렬 알고리즘인데

 

정렬이 되어있지않은 리스트 중

가장 작은 데이터를 가장 앞의 데이터와

바꾸는 방식이다

 

첫 번째 시도를 하면

나머지 값들 중 가장 작은 값을 찾아서

또 제일 앞고 바꾸고

이러한 방식을 계속해서 반복한다

 

 

Quicksort

 

퀵 정렬의 정렬 방식은 다음과 같다

 

pivot element를 한개 정한 다음

그것을 기준으로 array를 2개로 나눈다

양쪽으로 나눠진 array를

왼쪽은 pivot보다 작은 원소들, 오른쪽은 큰 원소들로

정렬하는 방식으로 정렬한다

 

따라서 퀵정렬은 정렬이 되어있으면

오히려 그 속도가 느려질 수 있다

 

위 ppt 사진을 참고하면

pivot element를 3으로 설정한뒤

3을 기준으로 왼쪽, 오른쪽 array를 나누며

정렬하는 과정을 확인할 수 있다

 

 

Merge Sort

합병 정렬은 array를 반으로 자른다음

각각 잘라진 array를 독립적으로 정렬을 한다음

sorted 된 array를 다시 합쳐 정렬하는 방식이다

 

제일 마지막까지 쪼개서 합치고 -> 합친 것들을 또 합치고 -> 쭈우욱 합쳐서

완성하는 방식의 정렬 알고리즘이다

 

 

 

Breadth-First Traversal

트리를 탐색할 때 탐색하는 방식에 대한 알고리즘이고

한국어로는 넓이 우선 탐색이라고 부른다

 

같은 깊이에 있는 노드들 전체를 탐색한 뒤에

다음 깊이로 넘어가는 방식이다

 

위 ppt 사진을 예시로 들자면

맨 처음 4를 방문한 다음

2와 6을 방문한다

 

그다음 해당 깊이에 있는 모든 노드들을 방문했으므로

다음으로 넘어가서

1과 3을 방문하고 그 다음 다시 5와 7을 방문한다

 

이러한 넓이 우선탐색에서는

방문한 노드를 담는 자료구조로

Queue를 사용한다

 

 

Depth-First Travel

 

한국어로는 깊이 우선 탐색이라고 부른다

깊이 우선 탐색은 해당 노드에 있는

가장 깊은 노드까지 모두 탐색한다음

다음 노드로 넘어가는 탐색 방식이다

 

깊이우선탐색에서는 방문한 노드를

저장하는 자료구조로 Stack을 사용한다