알고리즘

---

선형 및 이진 탐색

선형 탐색

탐색은 알고리즘에서 중요한 역할을 담당하며, 많은 알고리즘이 다양한 데이터 구조에 대해 가능한 한 빠른 검색을 지향하도록 설계되어 있다. 선형 탐색은 이런 탐색 알고리즘의 하나이다.

수학에서의 선형성은 그래프에서 직선으로 나타낼 수 있다는 의미다. 여기서 중요한 것은 그래프에 있는 직선을 축 2개의 숫자쌍으로 나타낼 수 있다는 것이고, 이는 선형 탐색의 기반이 된다.

선형 알고리즘은 실행 시간이 요소 개수 증가에 정비례한다. 따라서 시간복잡도는 O(n)이다. 시간복잡도의 원리와 선형성을 고려하면 선형 알고리즘은 데이터쌍(인덱스와 매칭되는 값)을 이용해 선형석으로 요소를 탐색하는 방법임을 알 수 있다.

배열이 과도하게 커지고 찾는 요소가 배열에 뒤쪽에 있으면 탐색이 무의미할 정도로 시간이 소요될 수 있다. 선형 탐색은 모든 유형의 데이터에 적용할 수 있지만, 비효율적이라는 단점이 있다.

이진 탐색

이진 탐색은 선형 탐색의 단점을 보완하는 로그형 탐색 알고리즘이다. 이진 탐색의 원리는 다음과 같다.

• 1부터 9까지의 숫자로 구성된 배열이 있고, 숫자 6을 찾는다.

  • [1,2,3,4,5,6,7,8,9]

• 배열의 중간 요소인 숫자5를 기준으로 삼고 찾는 숫자보다 작은 숫자를 삭제한다.

  • [1,2,3,4,<5>,6,7,8,9] => [6,7,8,9]

• 남긴 배열에서 다시 앞의 과정을 반복한다. 숫자7을 기준으로 했을 때 6은 7보다 작으므로 숫자7부터 숫자9를 제거한다

  • [6,<7>,8,9] => [6]

• 원하는 숫자만 남았으므로 인덱스를 확인하고 반환한다.

이진 탐색은 중간 요소와 찾으려는 값을 비교할 때마다 탐색 범위가 1/2이 된다. 시간 복잡도는 O(log n)이기 때문에 요소가 기하급수적으로 증가하더라도 시간은 같은 비율로 증가하지 않는다. 요소가 많을 수록 하나당 탐색에 걸리는 시간이 짧아진다.

주의점은 배열이 정리된 상태에서만 올바르게 동작한다는 점이다.

정렬 알고리즘

정렬 알고리즘의 특징

데이터 사이에는 유사한 속성이나 일련의 순서가 있다. 그래서 많은 알고리즘에서 처리중인 데이터를 특정 형태로 정렬 할 때가 있다.

가령 이진 탐색은 알고리즘을 수행하기 전에 데이터를 비교할 수 있도록 특정 순서로 데이터를 정렬하고, 데이터베이스도 쿼리를 실행하여 특정 속성에 따라 항목을 정렬 한다.

즉, 데이터를 정렬하면 알고리즘이 중복 데이터를 빠르게 식별하거나 필요한 데이터를 빠르게 찾을 수 있다.

버블 정렬

• 배열 오른쪽 끝에 있는 두 숫자를 비교해 더 큰 숫자가 맨 끝이 아니라면 두 숫자의 위치를 바꾼다.

• 왼쪽으로 한자리 이동한 후 다시 두 숫자를 비교한다. 이런 식으로 배열 왼쪽 끝에 도달할 때까지 반복한다.

• 결국 배열에서 가장 작은 숫자가 맨 왼쪽에 위치한다. 알고리즘은 다시 오른쪽 끝에서부터 두 숫자를 비교한다.

• 배열이 모두 정렬될 때까지 반복한다.

버블 정렬은 시간복잡도가 O(n^2)으로 비효율적인 알고리즘이다. 너무 느려서 응용 프로그램에 적용할 수 없다.

선택 정렬

• 선형 탐색을 통해 배열에서 가장 작은 숫자를 찾는다.

• 가장 작은 숫자와 배열에서 가장 왼쪽에 위치한 숫자의 위치를 바꾼다. 가장 작은 숫자가 왼쪽 끝에 위치했기에 가장 작은 숫자는 정렬이 완료되었다.

• 이러한 동작을 정렬이 완료될 때까지 반복한다.

선택 정렬은 반복문 2개를 중첩해서 구현하므로 시간 복잡도가 O(n^2)이다. 요소의 개수가 많다면 버블 정렬보다 조금 더 나은 성능을 제공할 뿐이다.

삽입 정렬

• 배열의 왼쪽 끝에서 두번째에 있는 숫자부터 차례로 앞의 숫자들과 비교한다. 숫자의 크기에 따라 숫자의 위치를 바꾼다.

• 다음에는 왼쪽 끝에서 세번째에 있는 숫자와 바로 앞인 두번째 숫자를 비교한다. 서로 위치를 바꾸거나 놔두었으면 다시 그 앞의 숫자와 비교한다. 이를 왼쪽 끝까지 반복한다.

• 이러한 동작을 배열의 모든 숫자가 정렬될 때까지 반복한다.

삽입 정렬은 선택 정렬처럼 가장 작은 숫자를 찾기 위해 배열의 모든 숫자를 확인할 필요가 없다. 시간 복잡도가 최악의 경우 O(n^2)이며 선택 정렬보다 효율적이다.

셸 정렬

셸 정렬은 삽입 정렬을 더 효율적으로 실행하는 알고리즘이며, 다음과 같이 동작한다.

• 요소를 몇개 단위로 묶은 후 단위마다 삽입 정렬을 실행한다.

• 이후 단위 요소 수를 줄여 묶은 후 삽입 정렬을 실행한다.

• 단위 요소 수가 1이 될 때까지 실행하면 정렬이 완료된다.

병합 정렬

병합 정렬은 데이터를 반으로 나누어 정렬을 수행한다. 이러한 방식을 분할 정복이라 한다.

• 첫번째 과정은 배열을 반으로 나눈다. 그리고 반으로 나눈 배열을 다시 반으로 나누는 식으로 모든 배열에 숫자가 하나만 남을 때까지 반복한다.

• 두 배열씩 결합하여 작은 숫자에서 큰 숫자 순으로 정렬한다. 결합을 반복해 배열의 크기를 늘려나간다.

• 이런 식으로 배열을 결합하고 정렬한다.

병합 정렬은 흔히 재귀함수를 사용하여 입력 데이터를 나누므로 시간복잡도가 재귀 횟수에 따라 달라진다. 일반적인 시간복잡도는 O(n log n)이다.

퀵 정렬

퀵 정렬도 분할 정복 방식을 이용한다.

• 배열의 맨 왼쪽 요소를 미커 이동의 기준이 되는 피벗(pivot)으로 정한다. 피벗은 무작위로 정해도 되지만 프로그래밍을 쉽게 하려면 배열 맨 왼쪽 또는 맨 오른쪽을 선택한다. 이하는 피벗이 맨 왼쪽인 경우이다.

• 피벗을 정하고 나면 피벗 바로 오른쪽에 위치한 요소와 맨 오른쪽에 위치한 요소를 각각 왼쪽 마커와 오른쪽 마커로 정한다.

• 왼쪽 마커는 오른쪽으로 이동하며 피벗보다 크거나 같은 첫번째 숫자를 선택한다. 오른쪽 마커는 왼쪽으로 이동하며 피벗보다 작은 첫번째 숫자를 선택한다.

• 각 마커가 숫자를 선택하면 왼쪽 마커와 오른쪽 마커의 숫자 위치를 바꾼다. 이런 식으로 두 마커가 접촉할 때까지 반복한다.

• 두 마커가 교차하면 오른쪽 마커에 해당하는 숫자와 피벗에 해당하는 숫자를 바꾼다. 이렇게 되면 피벗이었던 숫자의 정렬은 끝난다.

• 마커를 통해 숫자를 선택하고 위치를 바꾸는 동작을 반복하면 피벗보다 작은 숫자는 배열의 왼쪽에 피벗보다 큰 숫자는 배열의 오른쪽에 모인다.

• 정렬이 끝난 피벗의 왼쪽 배열과 오른쪽 배열을 나눠 각각 같은 동작을 수행한다. 알고리즘은 배열이 완전히 정렬될 때까지 배열을 작게 나눠가며 반복된다.

힙 정렬

힙 정렬은 힙 데이터 구조의 각 노드를 최대 힙 또는 최소 힙 상태로 정렬하는 방법이다.

• 최대 힙이 되도록 정렬할 경우, 먼저 값이 최대인 노드를 바로 위 노드값과 비교하여 자식 노드값이 부모 노드값보다 크면 위치를 바꾼다.

• 다시 최대 값이 있는 노드와 그 위의 노드를 비교하여 위치를 바꾼다. 이를 루트노드까지 반복한다.

• 이런 원리에 따라 모든 노드를 정렬한다.

최소 힙 정렬의 경우 반대로 하면 된다. 자식 노드와 부모 노드의 값을 비교하여 더 작은 쪽을 루트노드에 가깝도록 위치시킨다.

힙 정렬은 시간복잡도가 최선, 평균, 최악에 관계 없이 항상 O(n log n)이다. 이는 전체 값을 대상으로 하는 것이 아니라 가장 크거나 가장 작은 값 기준으로 바로 옆에 있는 노드를 상대 비교하기 때문이다.

버킷 정렬

버킷 정렬은 요소들을 어떤 기준이 있는 버킷에 나눠 넣은 후 이하의 정렬을 수행한다.

• 어떤 순서가 있는 버킷으로 사용할 기억공간을 준비한다.

• 버킷을 만들 때의 기준에 따라 요소들을 분류해 넣는다.

• 버킷별로 요소를 정렬한다.

• 버킷 안에서 정렬한 요소를 버킷의 순서에 따라 나열해서 정렬을 완료한다.

버킷 정렬의 시간 복잡도는 보통 버킷 내에서 요소를 정렬할 때의 시간 복잡도를 따른다. 최악의 경우는 O(n^2)이다.

기수 정렬

기수 정렬은 버킷 정렬과 기본 원리는 같으나 특정 기준이 정해져 있다. 기준은 자릿수끼리 비교해서 정렬한다.

• 숫자 0~9에 해당하는 버킷 9개를 만든다.

• 1의 자릿수를 기준으로 요소들을 버킷에 나누어 넣는다.

• 다음으로는 10의 자릿수를 기준으로 버킷 내의 요소들을 다시 나누어 넣는다. 이 때, 요소가 1의 자리 숫자라면 그 앞에 0이 붙어있다고 간주해 요소를 나눈다.(1 -> 01)

• 다음은 100의 자리수를 기준으로 한다. 이때도 요소가 1의 자릿수나 10의 자릿수인 경우 그 앞에 자릿수가 모자란 만큼 0이 붙는다.(1 -> 001, 15 -> 015)

• 이런식으로 요소를 계속 나누면 순서대로 정렬하게 된다.

기수 정렬의 시간 복잡도는 최악의 경우 O(mn)이다.(m은 요소의 자릿수)