들어가며

지난 글에서 알고리즘을 이해하기 위한 빌드업으로 데이터구조에 대해서 넓고 얕게 알아보았습니다. 오늘은 본격적으로 알고리즘에 대해 넓고 얕게 알아보도록 하겠습니다.

알고리즘

알고리즘하면 '알고리즘 문제를 푼다'라는 문장이 같이 떠오르는데요, 알고리즘은 문제 자체를 나타내기보다는 문제를 해결하기위해 사용하는 일련의 단계 혹은 절차를 뜻하는 것입니다. 이번 글에서는 문제를 해결하기 위한 가장 기본적인 알고리즘인 탐색 알고리즘, 정렬 알고리즘, 경로 탐색 알고리즘, 군집화 알고리즘에 대해 알아 보도록 하겠습니다.

1. 탐색 알고리즘

탐색 알고리즘은 이름에서 알 수 있듯, 데이터 구조에서 원하는 데이터를 검색(탐색)하는 알고리즘 입니다. 탐색 알고리즘의 유형인 선형 탐색 알고리즘과 이진 탐색 알고리즘에 대해서 알아보겠습니다.

1-1. 선형 탐색 알고리즘

선형 탐색 알고리즘은 인덱스와 이에 매칭되는 값을 이용해 선형적으로 요소를 탐색하는 방법입니다.
탐색 실행 시간은 요소 개수 증가에 정비례하여 증가하므로 시간 복잡도는 O(n)입니다.
ex) 숫자, 이름, 이미지, 오디오 클립 등 모든 유형에 적용 가능

예를들어, 선형 탐색으로 숫자 7을 찾기위해서는 인덱스는 0이며 값은 1인 첫 요소부터 하나씩 비교해 7번째에 숫자 7을 찾을 것이며 인덱스 6을 반환할 것입니다.

그러나, 요소 개수가 증가하면 탐색시간도 증가하므로 비효율적인 단점이 있습니다. 이를 보완하기 위한 로그형 탐색 기술인 이진 탐색 알고리즘에 대해서 알아봅시다.

1-2. 이진 탐색 알고리즘

이진 탐색 알고리즘은 배열의 중간 요소를 기준으로 찾고자 하는 요소보다 작은 요소는 삭제하며, 찾는 요소만 남을 때까지 이를 반복합니다.
이진 탐색을 위해서는 배열이 정렬된 상태여야합니다.
시간 복잡도는 O(logn)로 요소가 많을 수록 요소 하나당 탐색에 걸리는 시간이 짧아집니다. 즉, 복잡한 탐색을 수행할 때 수행 속도를 크게 향상 시킬 수 있습니다.

2. 정렬 알고리즘

정렬 알고리즘은 데이터를 특정한 형태로 정렬하기 위해 사용합니다.

2-1. 버블 정렬

버블 정렬은 배열 가장 오른쪽에 있는 요소와 그 전 요소를 비교하여 정렬하고, 자리를 하나씩 앞으로 이동해 비교를 계속합니다. 가장 오른쪽에 있던 요소가 가장 왼쪽으로 오면, 다시 가장 오른쪽에 있는 요소부터 비교 정렬을 시작합니다.
시간 복잡도가 O(n²)으로 비효율적입니다. 따라서 실제 응용 프로그램에서 사용하지 않습니다.

2-2. 선택 정렬

선택 정렬은 선형 탐색으로 가장 작은 수를 먼저 찾습니다. 그리고 찾은 가장 작은 수와 가장 왼쪽에 있는 요소와 자리를 바꿉니다. 이를 반복합니다.
시간 복잡도는 O(n²)으로 역시나 입력 데이터 개수가 증가할수록 실행 속도는 느려집니다.

2-3. 삽입 정렬

삽입 정렬은 배열의 가장 왼쪽 요소와 그 다음 요소를 비교하며, 한 자리씩 오른쪽을 이동해 정렬을 계속합니다.
시간 복잡도는 최악의 경우 O(n²)로, 선택 정렬보다 더 효율적인 알고리즘 입니다.

2-4. 셸 정렬

셸 정렬은 요소를 몇개 단위로 묶은 후 그 단위마다 삽입 정렬을 실행하는 방법입니다.
시간 복잡도는 최선과 최악의 경우 삽입 정렬과 같지만, 평균 값은 O(n^1.5)로 삽입 정렬보다 우수합니다.

2-5. 병합 정렬

병합 정렬은 데이터를 반으로 나누어 정렬을 수행합니다. 모든 배열의 요소가 하나만 남을때 까지 반으로 나누고, 두 배열씩 결합하며 정렬을 진행합니다.
시간 복잡도는 재귀 횟수에 따라 달라지지만, 일반적으로는 O(nlogn)입니다.

2-6. 퀵 정렬

퀵 정렬은 병합 정렬과 같이 데이터를 반으로 나누어 정렬하는 방법을 사용합니다.
피벗을 기준으로 왼쪽에는 피벗보다 작은 숫자, 오른쪽에는 피벗보다 큰 숫자로 배열이 정렬되면 알고리즘은 이를 반씩 나눕니다. 그리고 먼저 피벗의 왼쪽 배열에 대해 같은 동작을 수행한 후, 처음 피벗의 오른쪽 배열에 대해서도 같은 동작을 수행합니다. 알고리즘은 배열이 완전히 정렬될 때까지 배열을 작게 나눠가며 정렬을 수행합니다.
시간 복잡도는 O(nlogn)입니다.

2-7. 힙 정렬

힙 정렬은 힙 데이터 구조의 각 노드를 최대 힙 혹은 최소 힙으로 정렬하는 방법입니다.
시간 복잡도는 항상 O(nlogn)입니다.

2-8. 버킷 정렬

버킷 정렬은 요소들을 어떤 기준이 있는 버킷에 나눠 놓은 후 버킷별로 요소를 정렬합니다.
시간 복잡도는 최악의 경우 O(n²)이며, 평균은 O(n+n²/m+m)입니다. m은 버킷 수 입니다.

2-9. 기수 정렬

기수 정렬은 버킷 정렬과 기본 원리는 같으나, 버킷을 나누는 기준을 요솟값의 자릿수로 삼는 다는 점이 다릅니다.
시간 복잡도는 O(mn)입니다. m은 요소의 자릿수 입니다.

3. 경로 탐색 알고리즘

경로 탐색 알고리즘 또한 이름에서 알 수 있듯, 경로를 탐색하는 여러 방법을 나타내는 알고리즘입니다. 경로 탐색 알고리즘의 유형인 너비 우선 탐색 알고리즘과 깊이 우선 탐색 알고리즘, 데이크스크라 알고리즘, A* 알고리즘에 대해 알아봅시다.

3-1. 너비 우선 탐색 (breadth-first-search) 알고리즘

너비 우선 탐색은 그래프를 탐색하는 알고리즘으로 시작 노드에서 가장 가까운 노드부터 시작하여 모든 노드를 광범위하게 탐색합니다. 두 노드 사이에 경로가 있는지 확인하고, 그 사이의 최단경로를 결정합니다.
그래프를 층별로 탐색합니다.
루트 노드 1에서 시작하여 값이 10인 노드에 도달하기 위해서 가장 가까운 2,3,4를 먼저 탐색한 뒤 2에서 가장 가까운 5,6을 탐색 -> 3에서 가장 가까운 7탐색 -> 4에서 가장 가까운 8,9 탐색 그리고 5에서 가장 가까운 10 노드를 만나며 탐색이 종료됩니다.

3-2. 깊이 우선 탐색 (depth-first-search) 알고리즘

깊이 우선 탐색은 시작 노드와 직접 연관된 하위 노드의 끝까지 모두 탐색한 후 다음 하위노드를 탐색하는 방법입니다.
루트 노드 1에서 시작하여 값이 12인 노드에 도달하기 위해서 아래 화살표와 같이 탐색합니다.

3-3. 데이크스크라 알고리즘

데이크스트라 알고리즘은 가중 그래프를 사용하여 그래프의 노드 하나에서 다른 노드까지의 최단 경로를 찾는 방법입니다.
네비게이션에서 가장 빠른 길을 찾는 방법, 실시간 영상 통화를 위해 네트워크에서 최단 경로를 찾는 방법으로 사용될 수 있습니다.

3-4. A* 알고리즘

A*(에이스타) 알고리즘은 *휴리스틱 알고리즘 범주에 속하며, 탐색할때마다 최선의 휴리스틱을 찾아서 그에 따라 노드를 탐색하는 최선 우선 탐색이라는 알고리즘의 요소를 결합하여 해결책을 제공합니다. 그 결과 전체 순회 비용이 가장 낮은 경로를 선택할 수 있습니다.
데이크스트라 알고리즘은 그래프에서 가능한 모든 경로를 탐색하는데 비해 A*(에이스타) 알고리즘은 어림짐작한 최단 경로의 비용이 실제 최단 경로의 비용에 가까울 수 있어 더 효율적입니다. 비용 계산에 실패할 수도 있지만, 적어도 최단 경로를 찾을 수는 있습니다.

*휴리스틱 알고리즘 : 확률론을 토대로 문제의 대략적인 해결책을 제공하는 알고리즘입니다. 함께 알아두면 좋은 알고리즘으로는 탐욕 알고리즘이 있으며 이는 항상 현재의 관점에서 적합한 경로를 선택하는 알고리즘 입니다.

4. 군집화 알고리즘

군집화는 데이터를 분류하여 관련된 요소끼리 묶는 동작을 뜻하며, 군집화 알고리즘은 이러한 특성을 이용하여 분류 시스템과 머신러닝 시스템에서 널리 사용되는 알고리즘 입니다.

데이터 군집의 유형을 나누는 방법으로는 계층형 군집화와 분할형 군집화가 있습니다.

4-1. K-평균 알고리즘

K-평균 알고리즘은 분할형 군집화에 속하며, n차원 좌표계에서 *유클리드 거리를 기반으로 'K'개의 '평균'을 찾는 알고리즘 입니다.
ex) 분류 시스템, 머신러닝의 비지도 학습 시스템

*유클리드 거리 : 비슷한 데이터끼리 얼마나 가까이 있는지를 판단하는 개념입니다.

아래 그림에는 2개의 센트로이드(centroid)라는 분할형 군집의 중심점 있으며, 삼각형과 사각형으로 표시되어있습니다. 유클리드 거리 계산을 통해 삼각형 센트로이드와 사각형 센트로이드 각각에 더 가까운 데이터 요소를 결정합니다. 센트로이드에 데이터 요소를 할당하고 나면 할당된 데이터 요소를 중심으로 센트로이드 위치를 다시 계산합니다. 결과적으로 센트로이드는 각 군집에 속한 모든 데이터 요소의 '평균'위치로 재설정 됩니다.

4-2. K-최근접 이웃 알고리즘

K-최근접 이웃 알고리즘은 머신러닝에서 중요하게 사용되는 알고리즘으로 비슷한 특성을 가진 데이터를 비슷한 범주로 분류하는 알고리즘 입니다.

아래 그림을 확인해 봅시다. 원형 혹은 사각형으로 분류하는 분류 시스템이 있습니다. 그리고 새로운 도형(파란색 원)을 그래프에 추가했습니다. 최근접 이웃 갯수(K)가 5일경우, 새로운 도형은 원형 2개, 사각형 3개의 이웃을 가지므로 사각형으로 분류됩니다.

마치며

주요 알고리즘 개념인 탐색 알고리즘, 정렬 알고리즘, 경로 탐색 알고리즘, 군집화 알고리즘에 대해 간략하게 알아보았습니다. 다음번에는 배운 알고리즘 개념을 통해 어떤 문제를 해결해 줄 수 있을지 자세하게 알아보도록 하겠습니다.

참고

코드 없는 알고리즘과 데이터 구조(암스트롱 수베로 지음/류태호 옮김/동양북스) 책을 읽고 일부 내용을 보강하여 작성한 글입니다.
데이터 구조와 알고리즘에 대해 가볍게 맛보고자 하신다면 위 책을 추천합니다!
본문에 있는 그림은 모두 책을 보고 제가 직접 그린것이라 그림의 크기가 일정치 않을 수 있으나, 이것이 특정한 의미를 갖는것은 아닙니다.

알고리즘 훑어보기